OFFSET
1,4
COMMENTS
a(n) is half the number of fractions reduced to lowest terms with numerator and denominator in {2, 3,..., n}. a(5) = 5 = (1/2) * |{2/3, 2/5, 3/2, 3/4, 3/5, 4/3, 4/5, 5/2, 5/3, 5/4}|. -Stefano Spezia,Aug 11 2019
LINKS
Alois P. Heinz,Table of n, a(n) for n = 1..10000
FORMULA
a(n) = sum of phi(e) where e ranges over all nondivisors of n that are between 1 and n. -Joseph L. Pe,Oct 24 2002
a(n) =A002088(n) - n.
MAPLE
a:= proc(n) option remember; `if`(n=0, 0,
numtheory[phi](n)-1+a(n-1))
end:
seq(a(n), n=1..100); #Alois P. Heinz,Aug 11 2019
MATHEMATICA
f[n_]:= Module[{s, i}, s = 0; For[i = 1, i < n, i++, If[Mod[n, i]!= 0, s = s + EulerPhi[i]]]; s]; Table[f[i], {i, 1, 100}]
PROG
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
if n == 0:
return 0
c, j = 0, 2
k1 = n//j
while k1 > 1:
j2 = n//k1 + 1
c += (j2-j)*(2*(A015613(k1)+k1)-1)
j, k1 = j2, n//j2
return (n*(n-3)-c+j)//2 #Chai Wah Wu,Mar 25 2021
CROSSREFS
KEYWORD
nonn
AUTHOR
Joseph L. Pe,Oct 24 2002
EXTENSIONS
Edited byVladeta Jovovic,Mar 23 2003
STATUS
approved