login
A348396
Number of ways to reach n by starting with 1 and repeatedly adding any positive integer or multiplying by any integer greater than 1.
2
1, 2, 4, 10, 18, 42, 78, 168, 328, 672, 1324, 2706, 5354, 10788, 21518, 43194, 86208, 172792, 345208, 691118, 1381616, 2764476, 5527626, 11058184, 22113454, 44232246, 88459468, 176929482, 353848086, 707718428, 1415414600, 2830872574, 5661703102, 11323491086
OFFSET
1,2
LINKS
EXAMPLE
For n = 3 the a(3) = 4 solutions are 1 + 2, (1 + 1) + 1, (1*2) + 1, 1*3.
MAPLE
a:= proc(n) option remember; uses numtheory; `if`(n=1, 1,
add(a(n-j), j=1..n-1)+add(a(n/d), d=divisors(n) minus {1}))
end:
seq(a(n), n=1..34); # Alois P. Heinz, Jan 25 2022
MATHEMATICA
a[n_] := a[n] = If[n == 1, 1, Sum[a[n - j], {j, 1, n - 1}] +
Sum[a[n/d], {d, Divisors[n] ~Complement~ {1}}]];
Table[a[n], {n, 1, 34}] (* Jean-François Alcover, May 14 2022, after Alois P. Heinz *)
PROG
(MATLAB) a(1)=1; for n=2:20, a(n)=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 1 + 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, 34)]) # Michael S. Branicky, Jan 25 2022
(PARI) seq(n)={my(a=vector(n), s=1); a[1]=s; for(n=2, n, a[n] = s + sumdiv(n, d, a[d]); s += a[n]); a} \\ Andrew Howroyd, Jan 25 2022
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Michael R Peake, Jan 25 2022
STATUS
approved