cp's OEIS Frontend

A317925 Numerators of rational valued sequence whose Dirichlet convolution with itself yields Euler's phi (A000010).

%I A317925 #17 May 10 2025 04:39:59
%S A317925 1,1,1,7,2,1,3,25,5,1,5,7,6,3,2,363,8,5,9,7,3,5,11,25,8,3,13,21,14,1,
%T A317925 15,1335,5,4,6,35,18,9,6,25,20,3,21,35,5,11,23,363,33,4,8,21,26,13,10,
%U A317925 75,9,7,29,7,30,15,15,9923,12,5,33,7,11,3,35,125,36,9,8,63,15,3,39,363,139,10,41,21,16,21,14,125,44,5,18,77,15,23
%N A317925 Numerators of rational valued sequence whose Dirichlet convolution with itself yields Euler's phi (A000010).
%H A317925 Antti Karttunen, <a href="/A317925/b317925.txt">Table of n, a(n) for n = 1..16384</a>
%H A317925 Vaclav Kotesovec, <a href="/A317925/a317925.jpg">Graph - the asymptotic ratio (10000 terms)</a>
%F A317925 a(n) = numerator of f(n), where f(1) = 1, f(n) = (1/2) * (A000010(n) - Sum_{d|n, d>1, d<n} f(d) * f(n/d)) for n > 1.
%F A317925 Sum_{k=1..n} A317925(k) / A317926(k) ~ Pi^(-3/2) * n^2 * sqrt(3/(2*log(n))) * (1 + (1/2 - gamma/2 + 3*zeta'(2)/Pi^2) / (2*log(n))), where gamma is the Euler-Mascheroni constant A001620. - _Vaclav Kotesovec_, May 10 2025
%t A317925 f[1] = 1; f[n_] := f[n] = (EulerPhi[n] - DivisorSum[n, f[#]*f[n/#] &, 1 < # < n &])/2; Numerator @ Array[f, 100] (* _Amiram Eldar_, Dec 12 2022 *)
%o A317925 (PARI)
%o A317925 A317925perA317926(n) = if(1==n,n,(eulerphi(n)-sumdiv(n,d,if((d>1)&&(d<n),A317925perA317926(d)*A317925perA317926(n/d),0)))/2);
%o A317925 A317925(n) = numerator(A317925perA317926(n));
%o A317925 (PARI)
%o A317925 \\ Memoized implementation:
%o A317925 memo = Map();
%o A317925 A317925perA317926(n) = if(1==n,n,if(mapisdefined(memo,n),mapget(memo,n),my(v = (eulerphi(n)-sumdiv(n,d,if((d>1)&&(d<n),A317925perA317926(d)*A317925perA317926(n/d),0)))/2); mapput(memo,n,v); (v)));
%o A317925 (PARI) for(n=1, 100, print1(numerator(direuler(p=2, n, ((1-X)/(1-p*X))^(1/2))[n]), ", ")) \\ _Vaclav Kotesovec_, May 09 2025
%Y A317925 Cf. A000010, A317926 (denominators).
%Y A317925 Cf. also A046643, A317831.
%K A317925 nonn,frac
%O A317925 1,4
%A A317925 _Antti Karttunen_, Aug 11 2018