A000630 Number of ways to represent n using the binary operator a * b = 2^a + b.

1, 1, 2, 3, 7, 12, 23, 41, 81, 149, 282, 522, 987, 1843, 3463, 6473, 12160, 22773, 42719, 80025, 150074, 281258, 527320, 988334, 1852849, 3473061, 6510681, 12204139, 22877649, 42884585, 80389797, 150692973, 282481747, 529522496, 992614937, 1860696007

Offset

0,3

References

D. E. Knuth, personal communication.

Links

Table of n, a(n) for n=0..35.

D. E. Knuth, Letter to N. J. A. Sloane, Jan. 1995

Formula

Sum_{n>=0} a(n)*q^n = 1/(1 - Sum_{n>=0} a(n)*q^(2^n) ).

As n increases, a(n+1)/a(n) approaches the value x = 1.874542... satisfying 1 = Sum_{j>=0} a(j)/x^(2^j). [David W. Wilson]

Example

E.g. 4 = 1+1+1+1 = 2^1 + 1+1 = 2^1 + 2^1 = 2^2 = 2^1+1 = 1+2^1 + 1 = 1+1+2^1.

Maple

N:= 100: # to get all terms up to a(N)
F:= add(a[i]*q^i, i=0..N) - 1/(1 - add(a[i]*q^(2^i), i=0..ilog2(N))):
S:= series(F, q, N+1);
sol:= {}:
for i from 0 to N do
  eq:= subs(sol, coeff(S, q, i));
  sol:= sol union {a[i]=solve(eq, a[i])};
od:
subs(sol, [seq(a[i], i=0..N)]); # Robert Israel, Dec 12 2014

Crossrefs

Sequence in context: A054176 A396470 A289977 * A036538 A341407 A108742

Adjacent sequences: A000627 A000628 A000629 * A000631 A000632 A000633

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

More terms from David W. Wilson

Status

approved