A086449 -id:A086449 - cp's OEIS frontend

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

Peter Luschny, Apr 03 2010

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

			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]]

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.

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

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);

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 *)

# 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

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

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.

A086450 a(0) = 1, a(2n+1) = a(n), a(2n) = a(n) + a(n-1) + ... + a(n-m) + ... where a(n<0) = 0.

Original entry on oeis.org

1, 1, 2, 1, 4, 2, 5, 1, 9, 4, 11, 2, 16, 5, 17, 1, 26, 9, 30, 4, 41, 11, 43, 2, 59, 16, 64, 5, 81, 17, 82, 1, 108, 26, 117, 9, 147, 30, 151, 4, 192, 41, 203, 11, 246, 43, 248, 2, 307, 59, 323, 16, 387, 64, 392, 5, 473, 81, 490, 17, 572, 82, 573, 1, 681, 108, 707

Offset: 0

Ralf Stephan, Jul 20 2003

Sequence has itself and its partial sums as bisections.
Setting m=1 gives Stern-Brocot sequence (A002487).
Conjecture: a(n) mod 2 repeats the 7-pattern 1,1,0,1,0,0,1 (A011657).
The conjecture is easily proved by induction: a(0) to a(14) = 1, 1, 2, 1, 4, 2, 5, 1, 9, 4, 11, 2, 16, 5 read mod 2 gives 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1. Assume the conjecture is true up to n = 14k. Then the next 7 odd entries a(14k+1), a(14k+3), ..., a(14k+13) are read from a(7k) to a(7k+6), which follow the correct mod 2 pattern by assumption. For the even entries a(14k), a(14k+10)... a(14k+12), the sum over the first 7k-1 addends is even, simply because of each consecutive 7 addends exactly 4 are odd. So again a(7k) to a(7k+6) determines the outcome and again gives the desired pattern. a(14k) is odd, since a(7k) is odd, a(14k+2) is even, since a(7k) and a(7k+1) are odd and so on ... - Lambert Herrgesell (zero815(AT)googlemail.com), May 08 2007

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Cf. A086449.

Partial sums are in A085765.

a:= proc(n) local m; a(n):= `if`(n=0, 1,
      `if`(irem(n, 2, 'm')=1, a(m), s(m)))
    end:
s:= proc(n) s(n):= a(n) +`if`(n=0, 0, s(n-1)) end:
seq(a(n), n=0..100);  # Alois P. Heinz, Sep 26 2013

a[0] = 1; a[n_] := a[n] = If[EvenQ[n], Sum[a[n/2-k], {k, 0, n/2}], a[(n-1)/2]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jun 16 2015 *)

a(n)=if(n<2,n>=0,if(n%2==0,sum(k=0,n/2,a(n/2-k)),a((n-1)/2)))

A339479 Number of partitions consisting of n parts, each of which is a power of 2, where one part is 1 and no part is more than twice the sum of all smaller parts.

Original entry on oeis.org

1, 2, 5, 13, 35, 95, 259, 708, 1938, 5308, 14543, 39852, 109216, 299326, 820378, 2248484, 6162671, 16890790, 46294769, 126886206, 347774063, 953191416, 2612541157, 7160547089, 19625887013, 53791344195, 147433273080, 404090482159, 1107545909953, 3035602173663

Offset: 1

Victor S. Miller, Apr 24 2021

nonn

a(n) is the number of n-tuples of nondecreasing integers, which are the exponents of 2 in the partition, the first of which is 0 and which are "reduced". The 1-tuple (0) is reduced. If the tuple is (x(1), ..., x(n)), then it is reduced if (x(1), ..., x(n-1)) is reduced and x(n) <= ceiling(log_2(1 + Sum_{i=1..n-1} 2^x(i))). This sequence arose in analyzing the types of partitions of a positive integer into parts which are powers of 2.

			The a(2) = 2 partitions are {1,1} and {1,2}.
The a(3) = 5 partitions are {1,1,1}, {1,1,2}, {1,1,4}, {1,2,2}, {1,2,4}.
The a(4) = 13 partitions are {1,1,1,1}, {1,1,1,2}, {1,1,1,4}, {1,1,2,2}, {1,1,2,4}, {1,1,2,8}, {1,1,4,4}, {1,1,4,8}, {1,2,2,2}, {1,2,2,4}, {1,2,2,8}, {1,2,4,4}, {1,2,4,8}.

Alois P. Heinz, Table of n, a(n) for n = 1..2285

Cf. A002572, A018819, A086449, A174980, A343801.

b:= proc(n, t) option remember; `if`(n=0, 1,
     `if`(t=0, 0, b(n, iquo(t, 2))+b(n-1, t+2)))
    end:
a:= n-> b(n, 1):
seq(a(n), n=1..30);  # Alois P. Heinz, Apr 27 2021

b[n_, t_] := b[n, t] = If[n == 0, 1, If[t == 0, 0, b[n, Quotient[t, 2]] + b[n - 1, t + 2]]];
a[n_] := b[n, 1];
Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Jul 07 2021, after Alois P. Heinz *)

seq(n)={my(v=vector(n), a=vector(n)); a[1]=v[1]=1; for(n=2, n, for(j=1, n-1, v[n-(n-j)\2] += v[j]); a[n]=vecsum(v)); a} \\ Andrew Howroyd, Apr 25 2021

from functools import cache
@cache
def r339479(n, k):
    if n == 0:
        return 1
    elif k == 0:
        return r339479(n - 1, 1)
    else:
        return r339479(n - 1, k + 1) + r339479(n, k // 2)
def a339479(n): return r339479(n,0)
print([a339479(n) for n in range(1, 100)])

G.f.: x/(1 - x - B(x)) where B(x) is the g.f. of A002572.

a(n) = F(n,0) where F(0,k) = 1, F(n,0) = F(n-1,1) for n > 0 and F(n,k) = F(n-1,k+1) + F(n, floor(k/2)) for n,k > 0. In this recursion, F(n,k) gives the number of partitions with n parts where the sum of all parts smaller than the current part size being considered is between k and k+1 multiples of the part size. This function is independent of the current part size. In the case that k is zero, the only choice is to add a part of the current part size, otherwise parts of double the size are also a possibility. - Andrew Howroyd, Apr 24 2021

Terms a(19) and beyond from Andrew Howroyd, Apr 24 2021

A288310 a(0) = a(1) = 1; a(2n) = a(n) - a(n-1), a(2n+1) = Sum_{k=0..n} a(n-k).

Original entry on oeis.org

1, 1, 0, 2, -1, 2, 2, 4, -3, 3, 3, 5, 0, 7, 2, 11, -7, 8, 6, 11, 0, 14, 2, 19, -5, 19, 7, 26, -5, 28, 9, 39, -18, 32, 15, 40, -2, 46, 5, 57, -11, 57, 14, 71, -12, 73, 17, 92, -24, 87, 24, 106, -12, 113, 19, 139, -31, 134, 33, 162, -19, 171, 30, 210, -57, 192, 50, 224, -17, 239, 25

Offset: 0

Ilya Gutkovskiy, Jun 07 2017

sign

Sequence has its first differences and its partial sums as bisections.

			a(0) = a(1) = 1 by definition;
a(2) = a(2*1) = a(1) - a(0) = 0;
a(3) = a(2*1+1) = a(0) + a(1) = 2;
a(4) = a(2*2) = a(2) - a(1) = -1;
a(5) = a(2*2+1) = a(0) + a(1) + a(2) = 2;
a(6) = a(2*3) = a(3) - a(2) = 2, etc.

Michael Gilleland, Some Self-Similar Integer Sequences

Cf. A030067, A086449, A086450, A109671.

a[0] = 1; a[1] = 1; a[n_] := a[n] = If[EvenQ[n], a[n/2] - a[(n - 2)/2], Sum[a[(n - 1)/2 - k], {k, 0, (n - 1)/2}]]; Table[a[n], {n, 0, 70}]

def a(n): return 1 if n<2 else a(n/2) - a(n/2 - 1) if n%2==0 else sum([a((n - 1)/2 - k) for k in range((n + 1)/2)]) # Indranil Ghosh, Jun 08 2017

a(n) = Sum_{k=0..n} a(2*k).
a(n) = a(2*n+1) - a(2*n-1).
a(2*n+1) = Sum_{k=0..n} Sum_{m=0..k} a(2*m).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

SageMath

Formula

A086450 a(0) = 1, a(2n+1) = a(n), a(2n) = a(n) + a(n-1) + ... + a(n-m) + ... where a(n<0) = 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A339479 Number of partitions consisting of n parts, each of which is a power of 2, where one part is 1 and no part is more than twice the sum of all smaller parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A288310 a(0) = a(1) = 1; a(2*n) = a(n) - a(n-1), a(2*n+1) = Sum_{k=0..n} a(n-k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A288310 a(0) = a(1) = 1; a(2n) = a(n) - a(n-1), a(2n+1) = Sum_{k=0..n} a(n-k).