cp's OEIS Frontend

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.

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