A346114 a(n+1) = 1 + Sum_{k=1..n} a(gcd(n,k)).

1, 2, 4, 7, 12, 17, 28, 35, 51, 66, 91, 102, 150, 163, 210, 259, 325, 342, 454, 473, 608, 701, 823, 846, 1099, 1168, 1355, 1500, 1786, 1815, 2290, 2321, 2711, 2954, 3328, 3537, 4302, 4339, 4848, 5221, 6075, 6116, 7269, 7312, 8306, 9059, 9949, 9996, 11795, 12006

Offset

1,2

Links

Table of n, a(n) for n=1..50.

Formula

G.f. A(x) satisfies: A(x) = x * (1 / (1 - x) + Sum_{k>=1} phi(k) * A(x^k)).

a(1) = 1; a(n+1) = 1 + Sum_{d|n} phi(n/d) * a(d).

Mathematica

a[n_] := a[n] = 1 + Sum[a[GCD[n - 1, k]], {k, 1, n - 1}]; Table[a[n], {n, 1, 50}]
nmax = 50; A[_] = 0; Do[A[x_] = x (1/(1 - x) + Sum[EulerPhi[k] A[x^k], {k, 1, nmax}]) + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x] // Rest

Crossrefs

Cf. A000010, A006874, A038045, A338750.

Sequence in context: A181020 A049631 A239955 * A332744 A345731 A084672

Adjacent sequences: A346111 A346112 A346113 * A346115 A346116 A346117

Keyword

nonn

Author

Ilya Gutkovskiy, Jul 05 2021

Status

approved