OFFSET
1,3
LINKS
Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
FORMULA
a(n) = Sum_{k = 2..n} A242114(n,k). - Reinhard Zumkeller, May 04 2014
a(n) ~ kn^2, where k = 1 - 6/Pi^2 = 0.39207... (A229099). - Charles R Greathouse IV, Mar 29 2024
MATHEMATICA
f[n_] := Table[ #^2 &[m], {m, 1, n + 1}] - FoldList[Plus, 1, 2 Array[EulerPhi, n, 2]] (* _Gregg K. Whisler_, Jun 25 2008 *)
PROG
(Haskell)
a100613 n = length [()| x <- [1..n], y <- [1..n], gcd x y > 1]
-- Reinhard Zumkeller, Jan 21 2013
(PARI) a(n) = sum(i=1, n, sum(j=1, n, gcd(i, j)>1)); \\ Michel Marcus, Jan 30 2017
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
if n == 0:
return 0
c, j = 1, 2
k1 = n//j
while k1 > 1:
j2 = n//k1 + 1
c += (j2-j)*(k1**2-A100613(k1))
j, k1 = j2, n//j2
return n+c-j # Chai Wah Wu, Mar 24 2021
CROSSREFS
KEYWORD
nonn
AUTHOR
Douglas Stones (dssto1(AT)student.monash.edu.au), Dec 02 2004
STATUS
approved