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

%I #36 Jul 19 2017 20:10:05

%S 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,

%T 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,

%U 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

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

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

%H Antti Karttunen and Giovanni Resta, <a href="/A103840/b103840.txt">Table of n, a(n) for n = 0..10000</a> (first 1501 terms from Antti Karttunen)

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

%e a(0)=1 from the empty sum.

%e 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.

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

%o (Scheme)

%o (define (A103840 n) (A103840auxbi n 2))

%o (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))))))))))))))

%o ;; _Antti Karttunen_, Jul 18 2017

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

%K nonn,look

%O 0,17

%A _Gordon Hamilton_, Mar 29 2005

%E More terms from _David W. Wilson_, Mar 30 2005

%E More terms from _David Wasserman_, Apr 24 2008