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
Keywords
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.
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