A380790 Length of the n-th Golomb ruler constructed by the Paul Erdős and Pál Turán formula.

20, 110, 308, 1254, 2106, 4760, 6650, 11822, 23954, 29202, 49950, 68060, 78518, 102460, 147446, 203432, 225090, 298418, 354858, 386316, 489484, 568052, 700964, 907920, 1025150, 1086856, 1218944, 1289034, 1436456, 2039620, 2238790, 2561900, 2675472, 3296774, 3430418

Offset: 2

Author

Darío Clavijo, Feb 03 2025

Keywords

• nonn

Comments

In October of 1941 Paul Erdős and Pál Turán found that a Golomb ruler could be constructed for every odd prime p.

Such a ruler has the property that the mark or notches are defined by: notch(k) = 2pk + (k^2 mod p) for k in {0..p-1}, with p=A000040(n).

Empirical observation: a(n) satisfies p^3-p^2 <= a(n)/p^3 <= 0.9999.

Except for n=2, a(n) is divisible by p.

Also partial sums of A217793.

Examples

			 n | p  | Golomb ruler notches                             | a(n)
---+----+--------------------------------------------------+-------
 2 | 3  | 0, 7,  13                                        | 20
 3 | 5  | 0, 11, 24, 34, 41                                | 110
 4 | 7  | 0, 15, 32, 44, 58, 74,  85                       | 308
 5 | 11 | 0, 23, 48, 75, 93, 113, 135, 159, 185, 202, 221  | 1254
		

Links

• P. Erdös and P. Turán, On a Problem of Sidon in Additive Number Theory, and on some Related Problems, Journal of the London Mathematical Society, Volume s1-16, Issue 4, October 1941, Pages 212-215.
• Wikipedia, Golomb ruler
• Index entries for sequences related to Golomb rulers

Crossrefs

Cf. A000010, A000040, A000330, A048153, A076409, A100104, A127921, A135177, A160378, A217793.

Programs

PARI

a(n)= if(n==2, return(20));  my(p=prime(n)); if(bitand(p, 3)==1, return((p*(p-1)*(2*p+1))/2)); if(bitand(p, 3)==3, return((p*(p-1)*(2*p+1))/2 - p * qfbclassno(-p)));

Python

from sympy import prime
from math import isqrt
def a(n):
  p = prime(n)
  if p & 3 == 1: return (p*(p-1)*(2*p+1))//2
  m = isqrt(p-1)
  return (p-1) * p**2 + (m*(m+1)*(2*m+1))//6 + sum(pow(k,2,p) for k in range(m+1,p))
print([a(n) for n in range(2, 37) ])

Formula

a(n) = Sum_{k=0..p-1} (2*k*p + k^2 mod p), where p is the n-th prime.

a(n) = (p-1)*p^2 + 1 + Sum_{k=2..p-1} (k^2 mod p), where p is the n-th prime.

a(n) = (p-1)*p^2 + A000330(m) + Sum_{k=m+1..p-1} (k^2 mod p), where m = floor(sqrt(p-1)) and p is the n-th prime.

a(n) = (p-1)*p^2 + p*(p-1)*(p+1)/12 - 2*p*(Sum_{k=1..(p-1)/2} floor(k^2/p)), where p is the n-th prime.

a(n) = A100104(A000040(n)) + A048153(A000040(n)) - 1.

a(n) = A100104(A000040(n)) + A076409(n).

a(n) = A160378(A000040(n)), iif A000040(n) = 1 (mod 4).

a(n) = A160378(A000040(n)) - A000040(n)*A355879(n), iif A000040(n) = 3 (mod 4).

a(n) < A000040(n)^3.

a(n) > A000040(n)^3 - A000040(n)^2.

a(n) = 0 mod A000040(n) for n >= 3.

a(n) = Sum_{k=0..A000040(n)-1} A217793(n - 1, k).

a(n) = A135177(n) + A127921(n) - 2*p*(Sum_{k=1..(p-1)/2} floor(k^2/p)), where p = A000040(n).