cp's OEIS Frontend

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

%I A345182 #27 Nov 25 2024 16:29:01
%S A345182 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 A345182 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 A345182 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 A345182 a(1) = 1, a(2) = 0; a(n) = Sum_{d|n, d < n} a(d).
%C A345182 From _Antti Karttunen_, Nov 25 2024: (Start)
%C A345182 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 A345182   1 (none) 4/1    6/1     8/1     12/1      30/1
%C A345182                   6/3/1   8/4/1   12/3/1    30/3/1
%C A345182                                   12/4/1    30/5/1
%C A345182                                   12/6/1    30/6/1
%C A345182                                   12/6/3/1  30/10/1
%C A345182                                             30/15/1
%C A345182                                             30/6/3/1
%C A345182                                             30/10/5/1
%C A345182                                             30/15/3/1
%C A345182                                             30/15/5/1
%C A345182 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 A345182 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 A345182 (End)
%H A345182 Antti Karttunen, <a href="/A345182/b345182.txt">Table of n, a(n) for n = 1..20000</a>
%F A345182 G.f. A(x) satisfies: A(x) = x - x^2 + A(x^2) + A(x^3) + A(x^4) + ...
%F A345182 a(n) = A074206(n) if n is odd, otherwise a(n) = A074206(n) - A074206(n/2).
%t A345182 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 A345182 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 A345182 (PARI)
%o A345182 memoA345182 = Map();
%o A345182 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 A345182 (PARI)
%o A345182 up_to = 20000;
%o A345182 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 A345182 v345182 = A345182list(up_to);
%o A345182 A345182(n) = v345182[n]; \\ _Antti Karttunen_, Nov 25 2024
%Y A345182 Cf. A022825 (partial sums), A074206, A167865, A320224, A345138, A345141, A378218 (Dirichlet inverse), A378223 (inverse Möbius transform).
%K A345182 nonn
%O A345182 1,6
%A A345182 _Ilya Gutkovskiy_, Jun 10 2021