A103840 Number of ways to represent n as a sum of b^e with b >= 2, e >= 2, e distinct.

1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 1, 0, 0, 0, 2, 2, 0, 1, 1, 0, 0, 1, 2, 2, 0, 0, 3, 0, 0, 0, 2, 2, 0, 2, 2, 0, 0, 1, 2, 3, 0, 0, 4, 0, 0, 0, 2, 3, 0, 2, 2, 0, 0, 2, 4, 3, 0, 0, 5, 0, 0, 0, 3, 4, 0, 2, 3, 0, 0, 2, 5, 5, 0, 0, 5, 1, 0, 0, 3, 7, 1, 3, 3, 1, 0, 2, 5, 5, 1, 0, 7, 0, 0, 0, 3

Offset

0,17

Comments

291 is the largest integer for which this function is zero.

Links

Antti Karttunen and Giovanni Resta, Table of n, a(n) for n = 0..10000 (first 1501 terms from Antti Karttunen)

Formula

G.f.: Prod(e >= 2, 1 + Sum(b >= 2, x^(b^e))).

Example

a(0)=1 from the empty sum.
68 = 2^2+4^3 = 2^2+2^6 = 3^2+3^3+2^5 = 5^2+3^3+2^4 = 6^2+2^5 so a(68) = 5. Note that although 4^3 = 2^6, the exponents are different and so 2^2+4^3 and 2^2+2^6 are counted as distinct.

Mathematica

b[n_, k_] := b[n, k] = If[n < 2, 0, If[k == 2, Boole@ IntegerQ@ Sqrt@n, Block[{e}, b[n, k-1] + Sum[ b[n-e^k, k-1], {e, 2, n^(1/k)}] + Boole@ IntegerQ[n^(1/k)]]]]; a[0] = 1; a[n_] := b[n, Max[2, Floor@ Log2@ n]]; Array[a, 105, 0] (* Giovanni Resta, Jul 18 2017 *)

Prog

(Scheme)
(define (A103840 n) (A103840auxbi n 2))
(define (A103840auxbi n start_e) (cond ((zero? n) 1) ((negative? n) 0) (else (let ((ue (A000523 n))) (let outloop ((e start_e) (s 0)) (cond ((> e ue) s) (else (let ((ub (floor->exact (+ 1 (expt n (/ 1 e)))))) (let inloop ((b 2) (s s)) (if (> b ub) (outloop (+ 1 e) s) (inloop (+ 1 b) (+ s (A103840auxbi (- n (expt b e)) (+ 1 e))))))))))))))
;; Antti Karttunen, Jul 18 2017

Crossrefs

Cf. A103841 (where a(n) = 0), A103843 (positions of records).

Sequence in context: A081221 A366988 A280827 * A066301 A046660 A368251

Adjacent sequences: A103837 A103838 A103839 * A103841 A103842 A103843

Keyword

nonn,look

Author

Gordon Hamilton, Mar 29 2005

Extensions

More terms from David W. Wilson, Mar 30 2005

More terms from David Wasserman, Apr 24 2008

Status

approved