A345182 a(1) = 1, a(2) = 0; a(n) = Sum_{d|n, d < n} a(d).

1, 0, 1, 1, 1, 2, 1, 2, 2, 2, 1, 5, 1, 2, 3, 4, 1, 6, 1, 5, 3, 2, 1, 12, 2, 2, 4, 5, 1, 10, 1, 8, 3, 2, 3, 18, 1, 2, 3, 12, 1, 10, 1, 5, 8, 2, 1, 28, 2, 6, 3, 5, 1, 16, 3, 12, 3, 2, 1, 31, 1, 2, 8, 16, 3, 10, 1, 5, 3, 10, 1, 50, 1, 2, 8, 5, 3, 10, 1, 28, 8, 2, 1, 31, 3, 2, 3, 12, 1, 36

Offset

1,6

Comments

From Antti Karttunen, Nov 25 2024: (Start)

a(n) is the number of strict chains of divisors from n to 1 that do not end with 2/1. For example, the a(n) such chains for n = 1, 2, 4, 6, 8, 12, 30 are:

1 (none) 4/1 6/1 8/1 12/1 30/1

6/3/1 8/4/1 12/3/1 30/3/1

12/4/1 30/5/1

12/6/1 30/6/1

12/6/3/1 30/10/1

30/15/1

30/6/3/1

30/10/5/1

30/15/3/1

30/15/5/1

leaving 1, 0, 1, 2, 2, 5, 10 chains out of the 1, 1, 2, 3, 4, 8, 13 chains depicted in the illustration of A074206.

Equally, a(n) is the number of strict chains of divisors from n to 1 where n is not followed by n/2 as the second divisor in the chain, which explains nicely the formula a(n) = A074206(n) - A074206(n/2) when n is even.

(End)

Links

Antti Karttunen, Table of n, a(n) for n = 1..20000

Formula

G.f. A(x) satisfies: A(x) = x - x^2 + A(x^2) + A(x^3) + A(x^4) + ...

a(n) = A074206(n) if n is odd, otherwise a(n) = A074206(n) - A074206(n/2).

Mathematica

a[1] = 1; a[2] = 0; a[n_] := a[n] = Sum[If[d < n, a[d], 0], {d, Divisors[n]}]; Table[a[n], {n, 1, 90}]
nmax = 90; A[_] = 0; Do[A[x_] = x - x^2 + Sum[A[x^k], {k, 2, nmax}] + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x] // Rest

Prog

(PARI)
memoA345182 = Map();
A345182(n) = if(n<=2, n%2, my(v); if(mapisdefined(memoA345182, n, &v), v, v = sumdiv(n, d, if(d<n, A345182(d), 0)); mapput(memoA345182, n, v); (v))); \\ Antti Karttunen, Nov 22 2024
(PARI)
up_to = 20000;
A345182list(up_to_n) = { my(v=vector(up_to_n)); v[1] = 1; v[2] = 0; for(n=3, up_to_n, v[n] = sumdiv(n, d, (d<n)*v[d])); (v); };
v345182 = A345182list(up_to);
A345182(n) = v345182[n]; \\ Antti Karttunen, Nov 25 2024

Crossrefs

Cf. A022825 (partial sums), A074206, A167865, A320224, A345138, A345141, A378218 (Dirichlet inverse), A378223 (inverse Möbius transform).

Sequence in context: A324114 A011776 A375624 * A297791 A098965 A290087

Adjacent sequences: A345179 A345180 A345181 * A345183 A345184 A345185

Keyword

nonn

Author

Ilya Gutkovskiy, Jun 10 2021

Status

approved