

A265262


The tree of hemitropic sequences read by rows, arising from an ErdősTurán conjecture.


2



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 socalled hemitropic sequences. The ErdősTurán conjecture would not hold if (and only if) the tree contained an infinite bounded branch with no 0's.
The length of the nth row is 2^n. The right leaf of a node is equal to the left leaf + 1.


LINKS

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), 212215.
Labib Haddad, Some peculiarities of order 2 bases of N and the ErdosTuran conjecture, arXiv:1507.05849 [math.NT], 2015 (see The binary tree of hemitropic sequences chapter).
Wikipedia, ErdősTurán conjecture on additive bases


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(nk). 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 hth 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

Cf. A004137, A066062, A217793.
Sequence in context: A280596 A112345 A336469 * A124763 A029372 A029377
Adjacent sequences: A265259 A265260 A265261 * A265263 A265264 A265265


KEYWORD

nonn,tabf


AUTHOR

Labib Haddad and Michel Marcus, Dec 06 2015


STATUS

approved



