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.

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

Author

Michael R Peake, Jan 25 2022

Keywords

• nonn
• easy

Examples

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..3322

Crossrefs

Cf. A074206, A166444, A348378.

Programs

MATLAB

a(1)=1; for n=2:20, a(n)=sum(a(1:n-1))+sum(a(find(~rem(n,1:n-1)))); end;

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

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

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