A174980 Stern's diatomic series type ([0,1], 1).

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, 0, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 4, 3, 5, 2, 5, 3, 4, 1, 3, 2, 3, 1, 2, 1, 1, 0, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9, 7, 12, 5, 13, 8, 11, 3, 10, 7, 11, 4, 9, 5, 6, 1, 5, 4, 7, 3, 8

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

Cf. A002487, A070879, A047679, A007306, A174981, A140429 (row sums), A086449.

Sequence in context: A308067 A124748 A161225 * A277488 A325794 A119513

Adjacent sequences: A174977 A174978 A174979 * A174981 A174982 A174983

Keyword

easy,nonn,tabf,look

Author

Peter Luschny, Apr 03 2010

Status

approved