OFFSET
0,5
COMMENTS
A variant of Stern's diatomic series A002487. See the link [Luschny] and the Maple function below for the classification by types which is based on a generalization of Dijkstra's fusc function.
a(n) is also the number of superduperbinary integer partitions of n.
It appears that a(n) is equal to the multiplicative inverse of A002487(n+2) mod A002487(n+1). - Gary W. Adamson, Dec 23 2023
LINKS
Peter Luschny, row(n) for n = 0..12
Edsger Dijkstra, EWD 578: More about the function 'fusc', Selected Writings on Computing, Springer, 1982, p. 232.
Peter Luschny, Rational Trees and Binary Partitions.
Moritz A. Stern, Über eine zahlentheoretische Funktion, J. Reine Angew. Math., 55 (1858), 193-220.
FORMULA
Recursion: a(2n + 1) = a(n) and a(2n) = a(n - 1) + a(n) + [n = 2^k] for n = 1, a(0) = 0. [n = 2^k] is 1 if n is a power of 2, 0 otherwise.
EXAMPLE
The sequence splits into rows of length 2^k:
0,
0, 1,
0, 2, 1, 1,
0, 3, 2, 3, 1, 2, 1, 1,
0, 4, 3, 5, 2, 5, 3, 4, 1, 3, 2, 3, 1, 2, 1, 1,
...
.
The first few partitions counted are:
[ 0], []
[ 1], []
[ 2], [[2]]
[ 3], []
[ 4], [[4], [2, 2]]
[ 5], [[4, 1]]
[ 6], [[4, 1, 1]]
[ 7], []
[ 8], [[8], [4, 4], [2, 2, 2, 2]]
[ 9], [[8, 1], [4, 4, 1]]
[10], [[8, 2], [8, 1, 1], [4, 4, 1, 1]]
[11], [[8, 2, 1]]
[12], [[8, 2, 2], [8, 2, 1, 1]]
[13], [[8, 2, 2, 1]]
[14], [[8, 2, 2, 1, 1]]
[15], []
[16], [[16], [8, 8], [4, 4, 4, 4], [2, 2, 2, 2, 2, 2, 2, 2]]
[17], [[16, 1], [8, 8, 1], [4, 4, 4, 4, 1]]
[18], [[16, 2], [8, 8, 2], [16, 1, 1], [8, 8, 1, 1], [4, 4, 4, 4, 1, 1]]
[19], [[16, 2, 1], [8, 8, 2, 1]]
[20], [[16, 4], [16, 2, 2], [8, 8, 2, 2], [16, 2, 1, 1], [8, 8, 2, 1, 1]]
[21], [[16, 4, 1], [16, 2, 2, 1], [8, 8, 2, 2, 1]]
[22], [[16, 4, 2], [16, 4, 1, 1], [16, 2, 2, 1, 1], [8, 8, 2, 2, 1, 1]]
[23], [[16, 4, 2, 1]]
[24], [[16, 4, 4], [16, 4, 2, 2], [16, 4, 2, 1, 1]]
MAPLE
SternDijkstra := proc(L, p, n) local k, i, len, M; len := nops(L); M := L; k := n; while k > 0 do M[1+(k mod len)] := add(M[i], i=1..len); k := iquo(k, len); od; op(p, M) end:
a := n -> SternDijkstra([0, 1], 1, n);
MATHEMATICA
a[0] = 0; a[n_?OddQ] := a[n] = a[(n-1)/2]; a[n_?EvenQ] := a[n] = a[n/2 - 1] + a[n/2] + Boole[ IntegerQ[ Log[2, n/2]]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jul 26 2013 *)
PROG
(SageMath)
def A174980(n):
M = [0, 1]
for b in n.bits():
M[b] = M[0] + M[1]
return M[0]
print([A174980(n) for n in (0..100)]) # Peter Luschny, Nov 28 2017
(Python) # Generating the partitions.
def SDBinaryPartition(n):
def Double(W, T):
B = []
for L in W:
A = [a*2 for a in L]
if T > 0: A += [1]*T
B.append(A)
return B
if n == 2: return [[2]]
if n < 4: return []
h = n // 2
H = SDBinaryPartition(h)
B = Double(H, n % 2)
if n % 2 == 0:
H = SDBinaryPartition(h - 1)
if H != []: B += Double(H, 2)
if (n & (n - 1)) == 0: B.append([2]*h)
return B
for n in range(25): print([n], SDBinaryPartition(n)) # Peter Luschny, Sep 02 2019
CROSSREFS
KEYWORD
AUTHOR
Peter Luschny, Apr 03 2010
STATUS
approved