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, 801235247145, 8059220936672, 84463182889321

Offset: 0

Author

Mauro Torelli (torelli(AT)hermes.mc.dsi.unimi.it)

Keywords

• nonn
• more

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

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? (End)

The answer is a(n-1), or a(n) if "length n" ignores the initial zero. A Goldbach sequence is then an increasing basis with each element increased by 1. - [Corrected by Martin Fuller, Apr 28 2025]

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

• 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

Crossrefs

Cf. A123509.

Programs

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

Extensions

a(9)-a(14) from Martin Fuller, Feb 18 2009

Edited by N. J. A. Sloane, Mar 12 2009

a(15)-a(16) from Sean A. Irvine, Apr 19 2018

a(17)-a(19) from Martin Fuller, Apr 30 2025