OFFSET
0,5
COMMENTS
A variant of Stern's diatomic seriesA002487.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 ofA002487(n+2) modA002487(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)
defA174980(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