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

Author

Ilya Gutkovskiy, Jun 10 2021

Keywords

• nonn

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

Crossrefs

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

Programs

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

PARI

memoA345182 = Map();
A345182(n) = if(n<=2, n%2, my(v); if(mapisdefined(memoA345182,n,&v), v, v = sumdiv(n,d,if(dA345182(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,(dA345182list(up_to);
A345182(n) = v345182[n]; \\ Antti Karttunen, Nov 25 2024

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