A217793 -id:A217793 - cp's OEIS frontend

A265262 The tree of hemitropic sequences read by rows, arising from an Erdős-Turán conjecture.

1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2

Offset: 0

Labib Haddad and Michel Marcus, Dec 06 2015

Let A be a subset of the set N of nonnegative integers. Let pA(n) be the number of pairs (x, y) of elements of A such that n = x + y and x <= y. The sequence pA = [pA(0), pA(1), ... , pA(n), ... ] is called the profile of A. A Sidon set is a subset A whose profile has only 0's and 1's.
An [order 2 additive] basis of N is a subset A whose profile has no 0’s. Erdős and Turán conjectured that the profile of a basis is always unbounded (see the Erdős and Turán link). The conjecture is, up till now, still undecided.
The tree below displays the infinite sequences [1, pA(2), . . . ], associated to the profiles pA = [1, 1, pA(2), . . . ] of all the subsets A of N to which 0 and 1 belong. Those are the so-called hemitropic sequences. The Erdős-Turán conjecture would not hold if (and only if) the tree contained an infinite bounded branch with no 0's.
The length of the n-th row is 2^n. The right leaf of a node is equal to the left leaf + 1.

			First few levels of the tree:
                       1;
           1,                      2;
     0,          1,          1,         2;
  0,    1,    1,    2,    1,    2,    2,   3;
0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3;
...
First few rows of the irregular array:
1;
1, 2;
0, 1, 1, 2;
0, 1, 1, 2, 1, 2, 2, 3;
0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3;
...

Michel Marcus, Table of n, a(n) for n = 0..8190
P. Erdős and P. Turán, On a problem of Sidon in additive number theory, and on some related problems, J. Lond. Math. Soc. 16 (1941), 212-215.
Labib Haddad, Some peculiarities of order 2 bases of N and the Erdos-Turan conjecture, arXiv:1507.05849 [math.NT], 2015 (see The binary tree of hemitropic sequences chapter).
Wikipedia, Erdős-Turán conjecture on additive bases

Cf. A004137, A066062, A217793.

with(ListTools):
v:=n->Reverse( convert(n,base,2)):
m:=n->nops(v(n)):
c:=n-> v(n)[m(n)] + sum(v(n)[k]*v(n)[m(n)-k],k=1..floor(m(n)/2)):
d:= h->[seq(c(n),n=2^h..2^(h+1)-1)]: # the h-th row
f:= p->[seq(c(n),n=1..p)]: # the first p terms

f(t,n,va) = 1+ sum(k=1, n+1, va[k]*t^k);
row(n) = {if (n==0, vc = [1], vc = []; for (ni = 2^n, 2^(n+1)-1, b = binary(ni); ft = f(t, n, b); pt = (f(t, n, b)^2 + f(t^2, n, b))/2; vc = concat(vc, polcoeff(pt, n+1)););); vc;}
tabf(nn) = for (n=0, nn, vrow = row(n); for (k=1, #vrow, print1(vrow[k], ", ")); print());

For each k>=0, let u(k)=1 if k is in A, u(k)=0 is k is not in A. Then pA(n) = Sum_{k=0..floor(n/2)} u(k)*u(n-k). See formula (5) on p. 8 and p. 28 in Haddad link.

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

Original entry on oeis.org

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

Darío Clavijo, Feb 03 2025

nonn

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.

			 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

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

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

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)));

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) ])

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).

cp's OEIS Frontend

A265262 The tree of hemitropic sequences read by rows, arising from an Erdős-Turán conjecture.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula