A345182 - OEIS

%I #27 Nov 25 2024 16:29:01

%S 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,

%T 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,

%U 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

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

%C From _Antti Karttunen_, Nov 25 2024: (Start)

%C 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:

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

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

%C                                   12/4/1    30/5/1

%C                                   12/6/1    30/6/1

%C                                   12/6/3/1  30/10/1

%C                                             30/15/1

%C                                             30/6/3/1

%C                                             30/10/5/1

%C                                             30/15/3/1

%C                                             30/15/5/1

%C 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.

%C 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.

%C (End)

%H Antti Karttunen, <a href="/A345182/b345182.txt">Table of n, a(n) for n = 1..20000</a>

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

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

%t 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}]

%t 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

%o (PARI)

%o memoA345182 = Map();

%o 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

%o (PARI)

%o up_to = 20000;

%o 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); };

%o v345182 = A345182list(up_to);

%o A345182(n) = v345182[n]; \\ _Antti Karttunen_, Nov 25 2024

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

%K nonn

%O 1,6

%A _Ilya Gutkovskiy_, Jun 10 2021