cp's OEIS Frontend

A372866 a(n) is the sum, over all positive integers x, y such that x*y <= n, of phi(gcd(x,y)).

%I A372866 #34 Jul 07 2024 18:16:02
%S A372866 1,3,5,8,10,14,16,20,24,28,30,36,38,42,46,52,54,62,64,70,74,78,80,88,
%T A372866 94,98,104,110,112,120,122,130,134,138,142,154,156,160,164,172,174,
%U A372866 182,184,190,198,202,204,216,224,236,240,246,248,260,264,272,276,280
%N A372866 a(n) is the sum, over all positive integers x, y such that x*y <= n, of phi(gcd(x,y)).
%C A372866 A number-theoretic sum involving the Euler phi function and gcd's.
%C A372866 Theorem 1.1 of Kiuchi and Tsuruta (2024) gives an estimate for a(n).
%H A372866 Alois P. Heinz, <a href="/A372866/b372866.txt">Table of n, a(n) for n = 1..10000</a>
%H A372866 I. Kiuchi and Y. Tsuruta, <a href="https://doi.org/10.1017/S0004972723000825">On sums involving the Euler totient function</a>, Bull. Aust. Math. Soc. 109 (2024), 486-497.
%e A372866 For n = 3, the (a,b) pairs that appear in the sum are (1,1), (1,2), (1,3), (2,1), (3,1); the gcd of all is 1, and the sum of the phi-function at these 5 values of 1 is 5.
%p A372866 a:= proc(n) option remember; uses numtheory; `if`(n<1, 0,
%p A372866       a(n-1)+add(phi(igcd(d, n/d)), d=divisors(n)))
%p A372866     end:
%p A372866 seq(a(n), n=1..58);  # _Alois P. Heinz_, Jul 04 2024
%t A372866 a[n_] := a[n] = DivisorSum[n, EulerPhi[GCD[#, n/#]] &] + a[n - 1]; a[1] = 1; Array[a, 120] (* _Michael De Vlieger_, Jul 04 2024 *)
%o A372866 (Python)
%o A372866 from math import gcd
%o A372866 from functools import cache
%o A372866 from sympy import divisors, totient as phi
%o A372866 @cache
%o A372866 def a(n):
%o A372866     if n == 1: return 1
%o A372866     return a(n-1) + sum(phi(gcd(a, (b:=n//a))) for a in divisors(n))
%o A372866 print([a(n) for n in range(1, 61)]) # _Michael S. Branicky_, Jul 04 2024
%o A372866 (Python)
%o A372866 from math import prod
%o A372866 from itertools import count, islice
%o A372866 from sympy import factorint
%o A372866 def A372866_gen(): # generator of terms
%o A372866     c = 0
%o A372866     for n in count(1):
%o A372866         c += prod(p**(e>>1)+p**(e-1>>1) for p, e in factorint(n).items())
%o A372866         yield c
%o A372866 A372866_list = list(islice(A372866_gen(),20)) # _Chai Wah Wu_, Jul 05 2024
%o A372866 (PARI) a(n) = sum(k=1, n, sumdiv(k, d, eulerphi(gcd(d, k/d)))); \\ _Michel Marcus_, Jul 04 2024
%Y A372866 Partial sums of A001616.
%Y A372866 Cf. A000010.
%K A372866 nonn
%O A372866 1,2
%A A372866 _Jeffrey Shallit_, Jul 04 2024