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

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.

Formula

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

Example

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

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

Prog

(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;
(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
(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

Crossrefs

Cf. A067824, A131577, A348396.

Sequence in context: A264686 A337665 A165729 * A000740 A056278 A161625

Adjacent sequences: A348375 A348376 A348377 * A348379 A348380 A348381

Keyword

nonn

Author

Michael R Peake, Jan 25 2022

Status

approved