cp's OEIS Frontend

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.

%I A348378 #39 Dec 09 2023 01:43:40
%S A348378 1,3,6,15,27,63,117,252,492,1008,1986,4059,8031,16182,32277,64791,
%T A348378 129312,259188,517812,1036677,2072424,4146714,8291439,16587276,
%U A348378 33170181,66348369,132689202,265394223,530772129,1061577642,2123121900,4246308861,8492554653
%N 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.
%H A348378 Alois P. Heinz, <a href="/A348378/b348378.txt">Table of n, a(n) for n = 1..3321</a>
%H A348378 Michael R Peake, <a href="https://math.stackexchange.com/questions/4364776/how-many-ways-to-reach-an-integer-by-addition-and-multiplication">How many ways to reach an integer by addition and multiplication</a>, Math StackExchange, 2022.
%F A348378 a(n) = 1 + (Sum_{k=1..n-1} a(k)) + (Sum_{d|n, d<n} a(d)). - _Andrew Howroyd_, Jan 25 2022
%e A348378 For n = 3 the a(3) = 6 solutions are 3 = 1 + 2 = 2 + 1  = (1 + 1) + 1 = (1*2) + 1 = 1*3.
%p A348378 a:= proc(n) option remember; uses numtheory; 1+add(
%p A348378       a(n-j), j=1..n-1)+add(a(n/d), d=divisors(n) minus {1})
%p A348378     end:
%p A348378 seq(a(n), n=1..33);  # _Alois P. Heinz_, Jan 25 2022
%t A348378 a[n_] := a[n] = 1 + Sum[a[n-j], {j, 1, n-1}] +
%t A348378      Sum[a[n/d], {d, Divisors[n] ~Complement~ {1}}];
%t A348378 Table[a[n], {n, 1, 33}] (* _Jean-François Alcover_, May 14 2022, after _Alois P. Heinz_ *)
%o A348378 (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;
%o A348378 (Python)
%o A348378 from functools import cache
%o A348378 @cache
%o A348378 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)
%o A348378 print([a(n) for n in range(1, 35)]) # _Michael S. Branicky_, Jan 25 2022
%o A348378 (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
%Y A348378 Cf. A067824, A131577, A348396.
%K A348378 nonn
%O A348378 1,2
%A A348378 _Michael R Peake_, Jan 25 2022