A084978 Number of ways to represent n as a+b*(c+d*(e+f*(...x+y*(z)...))) in positive integers.

1, 2, 5, 11, 25, 51, 110, 221, 456, 918, 1864, 3729, 7528, 15057, 30227, 60485, 121205, 242411, 485337, 970675, 1942307, 3884730, 7771327, 15542655, 31089330, 62178686, 124364903, 248730268, 497475717, 994951435, 1989934099, 3979868199

Offset: 1

Author

David W. Wilson, Jun 16 2003

Keywords

• nonn
• easy

Examples

			a(3) = 5: 3 = 2+1(1) = 1+2(1) = 1+1(2) = 1+1(1+1(1)).
		

Links

• Robert Israel, Table of n, a(n) for n = 1..3305

Programs

Maple

f:= proc(n) option remember; local d;
   procname(n-1) + add(procname(d), d = numtheory:-divisors(n-1))
end proc:
f(1):=1:
map(f, [$1..40]); # Robert Israel, Dec 25 2023

Mathematica

a[1] = 1; a[n_] := a[n] = a[n-1] + DivisorSum[n-1, a[#] &];
Array[a, 50] (* Paolo Xausa, Aug 24 2024 *)

PARI

first(upto) = {my(a=vector(upto,i,1));for(n=1,upto-1,a[n+1]=a[n]+sumdiv(n,d,a[d]));a} \\ Jason Yuen, Aug 24 2024

Formula

a(n+1) = 1 + Sum_{k=1..n} Sum_{d|k} a(d) or a(n+1) = a(n) + Sum_{d|n} a(d). - Vladeta Jovovic, Aug 08 2004

G.f. A(x) satisfies: A(x) = (x/(1 - x)) * (1 + Sum_{k>=1} A(x^k)). - Ilya Gutkovskiy, Feb 25 2020

a(n) ~ c * 2^n, where c = 0.9266495520163897954172886595779644507444342903568129920731434938761... - Vaclav Kotesovec, Dec 26 2023