login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A265262
The tree of hemitropic sequences read by rows, arising from an Erdős-Turán conjecture.
3
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,3
COMMENTS
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.
LINKS
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).
FORMULA
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.
EXAMPLE
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;
...
MAPLE
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
PROG
(PARI) 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());
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Labib Haddad and Michel Marcus, Dec 06 2015
STATUS
approved