A087427 Number of lattice points on or inside the rectangle formed by [1 <= x <= (q-1)/2] and [1 <= y <= (p-1)/2], where p = n-th prime, q = (n-1)-st prime.

2, 6, 15, 30, 48, 72, 99, 154, 210, 270, 360, 420, 483, 598, 754, 870, 990, 1155, 1260, 1404, 1599, 1804, 2112, 2400, 2550, 2703, 2862, 3024, 3528, 4095, 4420, 4692, 5106, 5550, 5850, 6318, 6723, 7138, 7654, 8010, 8550, 9120, 9408, 9702, 10395, 11655

Offset: 3

Author

Gary W. Adamson, Sep 01 2003

Keywords

• nonn

Comments

Koshy, p. 499, states "We now employ this geometric approach to establish the lemma. It is due to the German mathematician Ferdinand Eisenstein, a student of Gauss at Berlin" (where the geometric lemma applies to the Law of Quadratic Reciprocity, Koshy, p. 501): "Let p and q be distinct odd primes. Then (p/q)(q/p) = (-1)^[(p-1)/2 * (q-1)/2]." Here (p/q) denotes the Legendre symbol.

Examples

			Given the line y = (11/7)*x, the number of lattice points on or inside the rectangle formed by (1 <= y <= 5), (1 <= x <= 3), where p = 11, q = 7; 5 = (p-1)/2, 3 = (q-1)/2; 3*5 = 15.
The number of lattice points on or inside the rectangle, (below the line y = (11/7)*x = 8 = Sum_{k=1..(q-1)/2} floor(k*(11/7)) = floor(11*1/7) + floor(11*2/7) + floor(11*3/7) = 1 + 3 + 4 = 8. The number of lattice points on or inside the rectangle above the line y = (11/7)*x = Sum_{k=1..(p-1)/2} floor(k*(7/11)) = floor(7*1/11) + floor(7*2/11) + floor(7*3/11) + floor(7*4/11) + floor(7*5/11) = 0 + 1 + 1 + 2 + 3 = 7.
Total number of lattice points inside or on the rectangle = 8 + 7 = 15.
		

References

• Thomas Koshy, "Elementary Number Theory with Applications", Harcourt Academic Press; 2002; pp. 498-500.

Links

• Ben Lynn, Gauss' Lemma
• Wikipedia, Gauss's lemma

Crossrefs

Cf. A087428.

Formula

a(n) = (prime(n-1) - 1) * (prime(n) - 1) / 4.

a(n) = Sum_{k=1..(p-1)/2} floor(k*q/p) + Sum_{k=1..(q-1)/2} floor(k*p/q).

Extensions

Corrected and extended by Ray Chandler, Sep 16 2003