A296261 - OEIS

%I #40 May 04 2023 01:54:52

%S 2,3,5,10,26,178,7391,6550891

%N Least non-constructible integer after addition or multiplication.

%C Starting with C(1)={0,1}, C(n)={x+y| x, y in C(n-1)} union {x*y, x,y in C(n-1)}. Then a(n) is the least integer not in C(n).

%H Mathematics Stack Exchange, <a href="https://math.stackexchange.com/questions/2557856/growth-rate-of-the-nth-natural-number-not-constructable-with-n-steps-of-addition">Growth rate of the nth natural number not constructable with n steps of addition and multiplication</a>, December 2017.

%e For example, C(1)={0,1}, C(2)={0,1,2}, C(3)={0,1,2,3,4}, C(4)={0,1,2,3,4,5,6,7,8,9,12,16}.

%e So a(1)=2, a(2)=3, a(3)=5, and a(4)=10.

%o (Python)

%o from itertools import filterfalse, count, combinations_with_replacement as cwr

%o n = 6

%o x = set([0,1])

%o for i in range(n):

%o     x = set([a[0] + a[1] for a in cwr(x,2)]).union(set([a[0]*a[1] for a in cwr(x,2)]))

%o     print(next(filterfalse(lambda b: b in x, count())))

%K nonn,more

%O 1,1

%A _Laurence P. Bordowitz_, Dec 13 2017

%E a(8) from _Rémy Sigrist_, Dec 19 2017