A265262 - OEIS

%I #30 Jan 15 2016 08:15:05

%S 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,

%T 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,

%U 1,1,2,0,1,1,2,0,1,1,2,0,1,1,2,0,1,1,2

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

%C 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.

%C 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.

%C 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.

%C The length of the n-th row is 2^n. The right leaf of a node is equal to the left leaf + 1.

%H Michel Marcus, <a href="/A265262/b265262.txt">Table of n, a(n) for n = 0..8190</a>

%H P. Erdős and P. Turán, <a href="http://www.renyi.hu/~p_erdos/1941-01.pdf">On a problem of Sidon in additive number theory, and on some related problems</a>, J. Lond. Math. Soc. 16 (1941), 212-215.

%H Labib Haddad, <a href="http://arxiv.org/abs/1507.05849">Some peculiarities of order 2 bases of N and the Erdos-Turan conjecture</a>, arXiv:1507.05849 [math.NT], 2015 (see The binary tree of hemitropic sequences chapter).

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Tur%C3%A1n_conjecture_on_additive_bases">Erdős-Turán conjecture on additive bases</a>

%F 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.

%e First few levels of the tree:

%e                        1;

%e            1,                      2;

%e      0,          1,          1,         2;

%e   0,    1,    1,    2,    1,    2,    2,   3;

%e 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3;

%e ...

%e First few rows of the irregular array:

%e 1;

%e 1, 2;

%e 0, 1, 1, 2;

%e 0, 1, 1, 2, 1, 2, 2, 3;

%e 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3;

%e ...

%p with(ListTools):

%p v:=n->Reverse( convert(n,base,2)):

%p m:=n->nops(v(n)):

%p c:=n-> v(n)[m(n)] + sum(v(n)[k]*v(n)[m(n)-k],k=1..floor(m(n)/2)):

%p d:= h->[seq(c(n),n=2^h..2^(h+1)-1)]: # the h-th row

%p f:= p->[seq(c(n),n=1..p)]: # the first p terms

%o (PARI) f(t,n,va) = 1+ sum(k=1, n+1, va[k]*t^k);

%o 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;}

%o tabf(nn) = for (n=0, nn, vrow = row(n); for (k=1, #vrow, print1(vrow[k], ", ")); print());

%Y Cf. A004137, A066062, A217793.

%K nonn,tabf

%O 0,3

%A _Labib Haddad_ and _Michel Marcus_, Dec 06 2015