login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A265262 The tree of hemitropic sequences read by rows, arising from an Erdős-Turá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 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

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

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 20 06:59 EDT 2021. Contains 343125 sequences. (Running on oeis4.)