|
%I #28 Dec 09 2023 01:43:54
%S 1,2,4,10,18,42,78,168,328,672,1324,2706,5354,10788,21518,43194,86208,
%T 172792,345208,691118,1381616,2764476,5527626,11058184,22113454,
%U 44232246,88459468,176929482,353848086,707718428,1415414600,2830872574,5661703102,11323491086
%N Number of ways to reach n by starting with 1 and repeatedly adding any positive integer or multiplying by any integer greater than 1.
%H Alois P. Heinz, <a href="/A348396/b348396.txt">Table of n, a(n) for n = 1..3322</a>
%e For n = 3 the a(3) = 4 solutions are 1 + 2, (1 + 1) + 1, (1*2) + 1, 1*3.
%p a:= proc(n) option remember; uses numtheory; `if`(n=1, 1,
%p add(a(n-j), j=1..n-1)+add(a(n/d), d=divisors(n) minus {1}))
%p end:
%p seq(a(n), n=1..34); # _Alois P. Heinz_, Jan 25 2022
%t a[n_] := a[n] = If[n == 1, 1, Sum[a[n - j], {j, 1, n - 1}] +
%t Sum[a[n/d], {d, Divisors[n] ~Complement~ {1}}]];
%t Table[a[n], {n, 1, 34}] (* _Jean-François Alcover_, May 14 2022, after _Alois P. Heinz_ *)
%o (MATLAB) a(1)=1; for n=2:20, a(n)=sum(a(1:n-1))+sum(a(find(~rem(n,1:n-1)))); end;
%o (Python)
%o from functools import cache
%o @cache
%o 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)
%o print([a(n) for n in range(1, 34)]) # _Michael S. Branicky_, Jan 25 2022
%o (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
%Y Cf. A074206, A166444, A348378.
%K nonn,easy
%O 1,2
%A _Michael R Peake_, Jan 25 2022
|
