cp's OEIS Frontend

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

%I A100449 #50 Mar 29 2021 21:03:34
%S A100449 1,5,9,17,25,41,49,73,89,113,129,169,185,233,257,289,321,385,409,481,
%T A100449 513,561,601,689,721,801,849,921,969,1081,1113,1233,1297,1377,1441,
%U A100449 1537,1585,1729,1801,1897,1961,2121,2169,2337,2417,2513,2601,2785,2849,3017
%N A100449 Number of ordered pairs (i,j) with |i| + |j| <= n and gcd(i,j) <= 1.
%C A100449 Note that gcd(0,m) = m for any m.
%C A100449 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.
%C A100449 From _Robert Price_, May 10 2013: (Start)
%C A100449 List of sequences that address these extensions:
%C A100449 Distinct sums i+j with or without the GCD qualifier results in a(n)=2n+1 (A005408).
%C A100449 Distinct products i*j without the GCD qualifier is given by A225523.
%C A100449 Distinct products i*j with    the GCD qualifier is given by A225526.
%C A100449 With the restriction i,j >= 0 ...
%C A100449 Distinct sums or products equal to n is trivial and always equals one (A000012).
%C A100449 Distinct sums <=n with or without the GCD qualifier results in a(n)=n (A001477).
%C A100449 Distinct products <=n without the GCD qualifier is given by A225527.
%C A100449 Distinct products <=n with    the GCD qualifier is given by A225529.
%C A100449 Ordered pairs with the sum = n without the GCD qualifier is a(n)=n+1.
%C A100449 Ordered pairs with the sum = n with    the GCD qualifier is A225530.
%C A100449 Ordered pairs with the sum <=n without the GCD qualifier is A000217(n+1).
%C A100449 Ordered pairs with the sum <=n with    the GCD qualifier is A225531.
%C A100449 (End)
%C A100449 This sequence (A100449) without the GCD qualifier results in A001844. - _Robert Price_, Jun 04 2013
%H A100449 Alois P. Heinz, <a href="/A100449/b100449.txt">Table of n, a(n) for n = 0..10000</a>
%F A100449 a(n) = 1 + 4*Sum(phi(k), k=1..n) = 1 + 4*A002088(n). - _Vladeta Jovovic_, Nov 25 2004
%p A100449 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;
%p A100449 # second Maple program:
%p A100449 b:= proc(n) b(n):= numtheory[phi](n)+`if`(n=0, 0, b(n-1)) end:
%p A100449 a:= n-> 1+4*b(n):
%p A100449 seq(a(n), n=0..50);  # _Alois P. Heinz_, Mar 01 2013
%t A100449 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 *)
%o A100449 (PARI) a(n) = 1+4*sum(k=1, n, eulerphi(k) ); \\ _Joerg Arndt_, May 10 2013
%o A100449 (Python)
%o A100449 from functools import lru_cache
%o A100449 @lru_cache(maxsize=None)
%o A100449 def A100449(n):
%o A100449     if n == 0:
%o A100449         return 1
%o A100449     c, j = 0, 2
%o A100449     k1 = n//j
%o A100449     while k1 > 1:
%o A100449         j2 = n//k1 + 1
%o A100449         c += (j2-j)*((A100449(k1)-3)//2)
%o A100449         j, k1 = j2, n//j2
%o A100449     return 2*(n*(n-1)-c+j)+1 # _Chai Wah Wu_, Mar 29 2021
%Y A100449 Cf. A018805, A100448, A100450, A027430, etc.
%K A100449 nonn
%O A100449 0,2
%A A100449 _N. J. A. Sloane_, Nov 21 2004
%E A100449 More terms from _Vladeta Jovovic_, Nov 25 2004