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,2

Links

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

Example

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

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

Prog

(MATLAB) a(1)=1; for n=2:20, a(n)=sum(a(1:n-1))+sum(a(find(~rem(n, 1:n-1)))); end;
(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
(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

Crossrefs

Cf. A074206, A166444, A348378.

Sequence in context: A303346 A197049 A303438 * A104723 A206140 A079162

Adjacent sequences: A348393 A348394 A348395 * A348397 A348398 A348399

Keyword

nonn,easy

Author

Michael R Peake, Jan 25 2022

Status

approved