A100449 Number of ordered pairs (i,j) with |i| + |j| <= n and gcd(i,j) <= 1.
1, 5, 9, 17, 25, 41, 49, 73, 89, 113, 129, 169, 185, 233, 257, 289, 321, 385, 409, 481, 513, 561, 601, 689, 721, 801, 849, 921, 969, 1081, 1113, 1233, 1297, 1377, 1441, 1537, 1585, 1729, 1801, 1897, 1961, 2121, 2169, 2337, 2417, 2513, 2601, 2785, 2849, 3017
Offset: 0
Keywords
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..10000
Programs
-
Maple
f:=proc(n) local i,j,k,t1,t2,t3; t1:=0; for i from -n to n do for j from -n to n do if abs(i) + abs(j) <= n then t2:=gcd(i,j); if t2 <= 1 then t1:=t1+1; fi; fi; od: od: t1; end; # second Maple program: b:= proc(n) b(n):= numtheory[phi](n)+`if`(n=0, 0, b(n-1)) end: a:= n-> 1+4*b(n): seq(a(n), n=0..50); # Alois P. Heinz, Mar 01 2013
-
Mathematica
f[n_] := Length[ Union[ Flatten[ Table[ If[ Abs[i] + Abs[j] <= n && GCD[i, j] <= 1, {i, j}, {0, 0}], {i, -n, n}, {j, -n, n}], 1]]]; Table[ f[n], {n, 0, 49}] (* Robert G. Wilson v, Dec 14 2004 *) -
PARI
a(n) = 1+4*sum(k=1, n, eulerphi(k) ); \\ Joerg Arndt, May 10 2013
-
Python
from functools import lru_cache @lru_cache(maxsize=None) def A100449(n): if n == 0: return 1 c, j = 0, 2 k1 = n//j while k1 > 1: j2 = n//k1 + 1 c += (j2-j)*((A100449(k1)-3)//2) j, k1 = j2, n//j2 return 2*(n*(n-1)-c+j)+1 # Chai Wah Wu, Mar 29 2021
Formula
a(n) = 1 + 4*Sum(phi(k), k=1..n) = 1 + 4*A002088(n). - Vladeta Jovovic, Nov 25 2004
Extensions
More terms from Vladeta Jovovic, Nov 25 2004
Comments