OFFSET
1,3
REFERENCES
Umberto Eco, Foucault's Pendulum. San Diego: Harcourt Brace Jovanovich, p. 473, 1989.
Athanasius Kircher (1601-1680). Ars Magna Sciendi, In XII Libros Digesta, qua nova et universali Methodo Per Artificiosum Combinationum contextum de omni re proposita plurimis et prope infinitis rationibus disputari, omniumque summaria quaedam cognitio comparari potest, Amstelodami, Apud Joannem Janssonium a Waesberge, et Viduam Elizei Weyerstraet, 1669, fol., pp. 482 (altra ed.: Amstelodami.(ut supra), 1671).
LINKS
N. J. A. Sloane, Table of n, a(n) for n = 1..1000 [First 500 terms from Indranil Ghosh]
Lars Blomberg, Scott R. Shannon, and N. J. A. Sloane, Graphical Enumeration and Stained Glass Windows, 1: Rectangular Grids, (2020). Also arXiv:2009.07918.
M. Griffiths, Counting the regions in a regular drawing of K_{n,n}, J. Int. Seq. 13 (2010) # 10.8.5, Lemma 2.
S. Legendre, The Number of Crossings in a Regular Drawing of the Complete Bipartite Graph, J. Integer Seqs., Vol. 12, 2009.
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
FORMULA
a(n) = Sum((n-a)*(n-b); 1<=a<n, 1<=b<n, (a,b)=1) - Sum((n-2*a)*(n-2*b); 1<=2*a<n, 1<=2*b<n, (a,b)=1). a(n) = Sum(f(a,b)-g(a,b); 1<=a<n, 1<=b<n,), f(a,b) the number of irreducible fractions p/q with 1<=p<=a,1<=q<=b, g(a,b) the number of rationals admitting at least one reducible form p/q with 1 <= p <= a, 1 <= q <= b (Philippe Paclet).
a(n) = (9/(8*Pi^2))*n^4 + O(n^3 log(n)). Asymptotic to (9/(2*Pi^2))*A000537(n-1).
For n > 2: a(n) = A115004(n-1)-(n-2)^2-2*Sum{n=2..floor((n-1)/2)} (n-2i)*(n-i)*phi(i) = 2n-3+3*Sum{n=2..floor((n-1)/2)}(n-i)*i*phi(i) + Sum_{n=floor((n+1)/2)..n-1} (n-i)*(2n-i)*phi(i). - Chai Wah Wu, Aug 16 2021
EXAMPLE
For n = 3 draw vertically 3 points regularly spaced on the right, and 3 points regularly spaced on the left. Join the left and right points by straight lines. These lines cross at c(3) = 7 points.
MAPLE
A159065 := proc(n)
local a, b, c ;
c := 0 ;
for a from 1 to n-1 do
for b from 1 to n-1 do
if igcd(a, b) = 1 then
c := c+(n-a)*(n-b) ;
if 2*a< n and 2*b < n then
c := c-(n-2*a)*(n-2*b) ;
end if;
end if;
end do:
end do:
c ;
end proc:
seq(A159065(n), n=1..30); # R. J. Mathar, Jul 20 2017
MATHEMATICA
a[n_] := Module[{x, y, s1 = 0, s2 = 0}, For[x = 1, x <= n-1, x++, For[y = 1, y <= n-1, y++, If[GCD[x, y] == 1, s1 += (n-x)*(n-y); If[2*x <= n-1 && 2*y <= n-1, s2 += (n-2*x)*(n-2*y)]]]]; s1-s2]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Jan 10 2014, translated from Joerg Arndt's PARI code *)
PROG
(Pascal)
s1:=0; s2:=0;
for a:=1 to n-1 do
for b:=1 to n-1 do
if gcd(a, b)=1 then
begin
s1:=s1+(n-a)*(n-b);
if (2*a<=n-1) and (2*b<=n-1) then
s2:=s2+(n-2*a)*(n-2*b);
end;
a:=s1-s2;
(PARI)
a(n) = {
my(s1=0, s2=0);
for (x=1, n-1,
for (y=1, n-1,
if ( gcd(x, y)==1,
s1 += (n-x) * (n-y);
if ( ( 2*x<=n-1) && (2*y<=n-1),
s2 += (n-2*x) * (n-2*y); );
);
);
);
return( s1 - s2 );
}
\\ Joerg Arndt, Oct 13 2013
(Python)
from math import gcd
def a159065(n):
c=0
for a in range(1, n):
for b in range(1, n):
if gcd(a, b)==1:
c+=(n - a)*(n - b)
if 2*a<n and 2*b<n:c-=(n - 2*a)*(n - 2*b)
return c
print([a159065(n) for n in range(1, 51)]) # Indranil Ghosh, Jul 20 2017
(Python)
from sympy import totient
def A159065(n): return n-1 if n <= 2 else 2*n-3+3*sum(totient(i)*(n-i)*i for i in range(2, (n+1)//2)) + sum(totient(i)*(n-i)*(2*n-i) for i in range((n+1)//2, n)) # Chai Wah Wu, Aug 16 2021
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Stéphane Legendre, Apr 04 2009, Jul 11 2009
STATUS
approved