A307856 a(1) = a(2) = 1; a(n) = Sum_{1 < k < n, k not dividing n} a(k).

1, 1, 1, 1, 3, 4, 10, 18, 37, 71, 146, 285, 577, 1143, 2293, 4570, 9160, 18277, 36597, 73118, 146301, 292466, 585079, 1169848, 2340003, 4679431, 9359402, 18717687, 37436529, 74870685, 149743743, 299482896, 598970235, 1197931456, 2395872060, 4791725527, 9583469660, 19166902722

Offset: 1

Author

Ilya Gutkovskiy, May 01 2019

Keywords

• nonn

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A003238, A045545.

Second column of A155033.

Programs

Maple

a := proc(n) local j; option remember;
if n < 3 then 1;
else add(`if`(`mod`(n, j) <> 0, a(j), 0), j = 2 .. n - 1);
end if; end proc;
seq(a(n), n = 1..40); # G. C. Greubel, Mar 08 2021

Mathematica

a[n_] := a[n] = Sum[Boole[Mod[n, k] != 0] a[k], {k,n-1}]; a[1] = a[2] = 1; Table[a[n], {n, 1, 38}]
terms = 38; A[] = 0; Do[A[x] = x (1 + x) + A[x]/(1 - x) - Sum[A[x^k], {k, 1, terms}] + O[x]^(terms + 1) // Normal, terms + 1]; Rest[CoefficientList[A[x], x]]
a[n_] := a[n] = SeriesCoefficient[x (1 + x + 1/(1 - x) Sum[a[k] x^k (1 - x^(k - 1))/(1 - x^k), {k, 1, n - 1}]), {x, 0, n}]; Table[a[n], {n, 1, 38}]

Sage

@CachedFunction
def a(n):
    if n<3: return 1
    else: return sum( a(j) if n%j!=0 else 0 for j in (2..n-1) )
[a(n) for n in (1..40)] # G. C. Greubel, Mar 08 2021

Formula

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

G.f.: A(x) = Sum_{n>=1} a(n)*x^n = x * (1 + x + (1/(1 - x)) * Sum_{n>=1} a(n)*x^n*(1 - x^(n-1))/(1 - x^n)).

a(n) ~ c * 2^n, where c = 0.0697287852138897098746368547699891689134990049613293203832908827967121295... - Vaclav Kotesovec, May 06 2019