login
A348378
Number of ways to reach n by starting with any positive integer, and repeatedly adding any positive integer or multiplying by any integer greater than 1.
2
1, 3, 6, 15, 27, 63, 117, 252, 492, 1008, 1986, 4059, 8031, 16182, 32277, 64791, 129312, 259188, 517812, 1036677, 2072424, 4146714, 8291439, 16587276, 33170181, 66348369, 132689202, 265394223, 530772129, 1061577642, 2123121900, 4246308861, 8492554653
OFFSET
1,2
LINKS
FORMULA
a(n) = 1 + (Sum_{k=1..n-1} a(k)) + (Sum_{d|n, d<n} a(d)). - Andrew Howroyd, Jan 25 2022
EXAMPLE
For n = 3 the a(3) = 6 solutions are 3 = 1 + 2 = 2 + 1 = (1 + 1) + 1 = (1*2) + 1 = 1*3.
MAPLE
a:= proc(n) option remember; uses numtheory; 1+add(
a(n-j), j=1..n-1)+add(a(n/d), d=divisors(n) minus {1})
end:
seq(a(n), n=1..33); # Alois P. Heinz, Jan 25 2022
MATHEMATICA
a[n_] := a[n] = 1 + Sum[a[n-j], {j, 1, n-1}] +
Sum[a[n/d], {d, Divisors[n] ~Complement~ {1}}];
Table[a[n], {n, 1, 33}] (* Jean-François Alcover, May 14 2022, after Alois P. Heinz *)
PROG
(MATLAB) a(1)=1; for n=2:20, a(n)=1+sum(a(1:n-1))+sum(a(find(~rem(n, 1:n-1)))); end;
(Python)
from functools import cache
@cache
def a(n): return 1 if n == 1 else 2 + sum(a(i) for i in range(1, n)) + sum(a(i) for i in range(2, n) if n%i == 0)
print([a(n) for n in range(1, 35)]) # Michael S. Branicky, Jan 25 2022
(PARI) seq(n)={my(a=vector(n), s=0); for(n=1, n, a[n] = 1 + s + sumdiv(n, d, a[d]); s += a[n]); a} \\ Andrew Howroyd, Jan 25 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Michael R Peake, Jan 25 2022
STATUS
approved