cp's OEIS Frontend

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

%I A380790 #55 Apr 01 2025 03:28:09
%S A380790 20,110,308,1254,2106,4760,6650,11822,23954,29202,49950,68060,78518,
%T A380790 102460,147446,203432,225090,298418,354858,386316,489484,568052,
%U A380790 700964,907920,1025150,1086856,1218944,1289034,1436456,2039620,2238790,2561900,2675472,3296774,3430418
%N A380790 Length of the n-th Golomb ruler constructed by the Paul Erdős and Pál Turán formula.
%C A380790 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.
%C A380790 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).
%C A380790 Empirical observation: a(n) satisfies p^3-p^2 <= a(n)/p^3 <= 0.9999.
%C A380790 Except for n=2, a(n) is divisible by p.
%C A380790 Also partial sums of A217793.
%H A380790 P. Erdös and P. Turán, <a href="https://doi.org/10.1112/jlms/s1-16.4.212">On a Problem of Sidon in Additive Number Theory, and on some Related Problems</a>, Journal of the London Mathematical Society, Volume s1-16, Issue 4, October 1941, Pages 212-215.
%H A380790 Wikipedia, <a href="https://en.wikipedia.org/wiki/Golomb_ruler">Golomb ruler</a>
%H A380790 <a href="/index/Go#Golomb">Index entries for sequences related to Golomb rulers</a>
%F A380790 a(n) = Sum_{k=0..p-1} (2*k*p + k^2 mod p), where p is the n-th prime.
%F A380790 a(n) = (p-1)*p^2 + 1 + Sum_{k=2..p-1} (k^2 mod p), where p is the n-th prime.
%F A380790 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.
%F A380790 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.
%F A380790 a(n) = A100104(A000040(n)) + A048153(A000040(n)) - 1.
%F A380790 a(n) = A100104(A000040(n)) + A076409(n).
%F A380790 a(n) = A160378(A000040(n)), iif A000040(n) = 1 (mod 4).
%F A380790 a(n) = A160378(A000040(n)) - A000040(n)*A355879(n), iif A000040(n) = 3 (mod 4).
%F A380790 a(n) < A000040(n)^3.
%F A380790 a(n) > A000040(n)^3 - A000040(n)^2.
%F A380790 a(n) = 0 mod A000040(n) for n >= 3.
%F A380790 a(n) = Sum_{k=0..A000040(n)-1} A217793(n - 1, k).
%F A380790 a(n) = A135177(n) + A127921(n) - 2*p*(Sum_{k=1..(p-1)/2} floor(k^2/p)), where p = A000040(n).
%e A380790  n | p  | Golomb ruler notches                             | a(n)
%e A380790 ---+----+--------------------------------------------------+-------
%e A380790  2 | 3  | 0, 7,  13                                        | 20
%e A380790  3 | 5  | 0, 11, 24, 34, 41                                | 110
%e A380790  4 | 7  | 0, 15, 32, 44, 58, 74,  85                       | 308
%e A380790  5 | 11 | 0, 23, 48, 75, 93, 113, 135, 159, 185, 202, 221  | 1254
%o A380790 (Python)
%o A380790 from sympy import prime
%o A380790 from math import isqrt
%o A380790 def a(n):
%o A380790   p = prime(n)
%o A380790   if p & 3 == 1: return (p*(p-1)*(2*p+1))//2
%o A380790   m = isqrt(p-1)
%o A380790   return (p-1) * p**2 + (m*(m+1)*(2*m+1))//6 + sum(pow(k,2,p) for k in range(m+1,p))
%o A380790 print([a(n) for n in range(2, 37) ])
%o A380790 (PARI)
%o A380790 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)));
%Y A380790 Cf. A000010, A000040, A000330, A048153, A076409, A100104, A127921, A135177, A160378, A217793.
%K A380790 nonn
%O A380790 2,1
%A A380790 _Darío Clavijo_, Feb 03 2025