A168043 Let S(1)={1} and, for n>1 let S(n) be the smallest set containing x+1, x+2, and 2*x for each element x in S(n-1). a(n) is the number of elements in S(n).

1, 2, 4, 7, 13, 23, 40, 68, 114, 189, 311, 509, 830, 1350, 2192, 3555, 5761, 9331, 15108, 24456, 39582, 64057, 103659, 167737, 271418, 439178, 710620, 1149823, 1860469, 3010319, 4870816, 7881164, 12752010, 20633205, 33385247, 54018485, 87403766, 141422286

Offset: 1

Author

John W. Layman, Nov 17 2009

Keywords

• nonn

Examples

			Under the indicated set mapping we have {1} -> {2,3} -> {3,4,5,6} -> {4,5,6,7,8,10,12}, ..., so a(2)=2, a(3)=4, a(4)=7, etc.
		

Crossrefs

Cf. A000032, A122554.

Programs

Python

from itertools import chain, islice
def agen(): # generator of terms
    s = {1}
    while True:
        yield len(s)
        s = set(chain.from_iterable((x+1, x+2, 2*x) for x in s))
print(list(islice(agen(), 30))) # Michael S. Branicky, Jan 13 2022 after Chai Wah Wu in A123247

Formula

It appears that a(n) = a(n-1) + a(n-2) + n - 3, for n>3.

From R. J. Mathar, Nov 18 2009: (Start)

Apparently: a(n) = 3*a(n-1) - 2*a(n-2) - a(n-3) + a(n-4) for n>5;

and a(n) = A000032(n+1) - n for n>1. (End)

From Ilya Gutkovskiy, Jul 07 2016: (Start)

It appears that the g.f. is x*(1 - x + x^4)/((1 - x)^2*(1 - x - x^2)); and the e.g.f. is phi*exp(phi*x) - exp(-x/phi)/phi - x*(1 + exp(x)) - 1, where phi is the golden ratio. (End)

It would be nice to have a proof for any one of these formulas. The others would then presumably follow easily. - N. J. A. Sloane, Jul 11 2016

Extensions

a(17)-a(22) from R. J. Mathar, Nov 18 2009

a(23)-a(35) from Jinyuan Wang, Apr 14 2020

a(36)-a(38) from Michael S. Branicky, Jan 13 2022