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

1, 3, 5, 8, 10, 14, 16, 20, 24, 28, 30, 36, 38, 42, 46, 52, 54, 62, 64, 70, 74, 78, 80, 88, 94, 98, 104, 110, 112, 120, 122, 130, 134, 138, 142, 154, 156, 160, 164, 172, 174, 182, 184, 190, 198, 202, 204, 216, 224, 236, 240, 246, 248, 260, 264, 272, 276, 280

Offset

1,2

Comments

A number-theoretic sum involving the Euler phi function and gcd's.

Theorem 1.1 of Kiuchi and Tsuruta (2024) gives an estimate for a(n).

Links

Alois P. Heinz, Table of n, a(n) for n = 1..10000

I. Kiuchi and Y. Tsuruta, On sums involving the Euler totient function, Bull. Aust. Math. Soc. 109 (2024), 486-497.

Example

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.

Maple

a:= proc(n) option remember; uses numtheory; `if`(n<1, 0,
      a(n-1)+add(phi(igcd(d, n/d)), d=divisors(n)))
    end:
seq(a(n), n=1..58);  # Alois P. Heinz, Jul 04 2024

Mathematica

a[n_] := a[n] = DivisorSum[n, EulerPhi[GCD[#, n/#]] &] + a[n - 1]; a[1] = 1; Array[a, 120] (* Michael De Vlieger, Jul 04 2024 *)

Prog

(Python)
from math import gcd
from functools import cache
from sympy import divisors, totient as phi
@cache
def a(n):
    if n == 1: return 1
    return a(n-1) + sum(phi(gcd(a, (b:=n//a))) for a in divisors(n))
print([a(n) for n in range(1, 61)]) # Michael S. Branicky, Jul 04 2024
(Python)
from math import prod
from itertools import count, islice
from sympy import factorint
def A372866_gen(): # generator of terms
    c = 0
    for n in count(1):
        c += prod(p**(e>>1)+p**(e-1>>1) for p, e in factorint(n).items())
        yield c
A372866_list = list(islice(A372866_gen(), 20)) # Chai Wah Wu, Jul 05 2024
(PARI) a(n) = sum(k=1, n, sumdiv(k, d, eulerphi(gcd(d, k/d)))); \\ Michel Marcus, Jul 04 2024

Crossrefs

Partial sums of A001616.

Cf. A000010.

Sequence in context: A005004 A006218 A062839 * A253081 A088940 A088937

Adjacent sequences: A372863 A372864 A372865 * A372867 A372868 A372869

Keyword

nonn

Author

Jeffrey Shallit, Jul 04 2024

Status

approved