A008932 - OEIS

A008932

Number of increasing sequences of Goldbach type of length n; a(0) = 1 by convention.

1, 1, 2, 5, 17, 65, 292, 1434, 7875, 47098, 305226, 2122983, 15752080, 124015310, 1031857395, 9041908204, 83186138212

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

From David S. Newman, Feb 17 2009: (Start)

This sequence also arises in the following way.

Call a set A of nonnegative integers a basis if every nonnegative integer can be written as the sum of two (not necessarily distinct) elements of A.

Call a basis an increasing basis if its elements are arranged in increasing order, a0 < a1 < a2 < ...

For example, A126684: 0, 1, 2, 4, 5, 8, 10, 16, 17, 20, 21, 32, 34, 40, ... is an increasing basis.

Now consider the set of all initial subsequences of any length {a0, a1, a2,...,an} of all the increasing bases. These can be arranged in lexicographic order, giving:

0, 1

0, 1, 2

0, 1, 3

0, 1, 2, 3

0, 1, 2, 4

0, 1, 2, 5

0, 1, 3, 4

0, 1, 3, 5

...

How many such subsequences are there of length n? The answer is a(n+1).

A Goldbach sequence is then an increasing basis without the initial zero. (End)

The largest value for each term in any increasing basis is given by A123509. - Martin Fuller, Jun 01 2010

REFERENCES

M. Torelli, Increasing integer sequences and Goldbach's conjecture, preprint, 1996.

LINKS

Table of n, a(n) for n=0..16.

M. Torelli, Increasing integer sequences and Goldbach's conjecture, RAIRO - Theoretical Informatics and Applications, vol.40, no.02 (April 2006), pp.107-121.

Index entries for sequences related to Goldbach conjecture

PROG

(PARI) A008932(n, pol=0)= { local(a=0, i, pol2);

!n && return(1);

i = #pol;

pol2 = pol^2;

for (i=#pol, #pol2+1,

a += A008932(n-1, pol+'x^i);

!polcoeff(pol2, i) && break; );

a } \\ Martin Fuller, Jun 01 2010

CROSSREFS

Cf. A123509.