

A100449


Number of ordered pairs (i,j) with i + j <= n and gcd(i,j) <= 1.


13



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Note that gcd(0,m) = m for any m.
I would also like to get the sequences of the numbers of distinct sums i+j (also distinct products i*j) over all ordered pairs (i,j) with i + j <= n; also over all ordered pairs (i,j) with i + j <= n and gcd(i,j) <= 1.
List of sequences that address these extensions:
Distinct sums i+j with or without the GCD qualifier results in a(n)=2n+1 (A005408).
Distinct products i*j without the GCD qualifier is given by A225523.
Distinct products i*j with the GCD qualifier is given by A225526.
With the restriction i,j >= 0 ...
Distinct sums or products equal to n is trivial and always equals one (A000012).
Distinct sums <=n with or without the GCD qualifier results in a(n)=n (A001477).
Distinct products <=n without the GCD qualifier is given by A225527.
Distinct products <=n with the GCD qualifier is given by A225529.
Ordered pairs with the sum = n without the GCD qualifier is a(n)=n+1.
Ordered pairs with the sum = n with the GCD qualifier is A225530.
Ordered pairs with the sum <=n without the GCD qualifier is A000217(n+1).
Ordered pairs with the sum <=n with the GCD qualifier is A225531.
(End)


LINKS



FORMULA



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(n1)) end:
a:= n> 1+4*b(n):


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 *)


PROG

(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)
if n == 0:
return 1
c, j = 0, 2
k1 = n//j
while k1 > 1:
j2 = n//k1 + 1
j, k1 = j2, n//j2


CROSSREFS



KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



