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.

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

Author

Michael R Peake, Jan 25 2022

Keywords

• nonn

Examples

			For n = 3 the a(3) = 6 solutions are 3 = 1 + 2 = 2 + 1  = (1 + 1) + 1 = (1*2) + 1 = 1*3.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..3321
• Michael R Peake, How many ways to reach an integer by addition and multiplication, Math StackExchange, 2022.

Crossrefs

Cf. A067824, A131577, A348396.

Programs

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;

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 *)

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

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

Formula

a(n) = 1 + (Sum_{k=1..n-1} a(k)) + (Sum_{d|n, dAndrew Howroyd, Jan 25 2022