|
| |
|
|
A159065
|
|
Number of crossings in a regular drawing of the complete bipartite graph K(n,n).
|
|
11
|
|
|
|
0, 1, 7, 27, 65, 147, 261, 461, 737, 1143, 1637, 2349, 3217, 4401, 5769, 7457, 9433, 11945, 14753, 18235, 22173, 26771, 31801, 37813, 44449, 52161, 60489, 69955, 80289, 92203, 104941, 119493, 135261, 152705, 171205, 191649, 213473, 237877
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
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:
|
|
|
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 );
}
(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
|
|
|
|
STATUS
|
approved
|
| |
|
|
