A343328 a(0) = 0. a(n) = the second smallest number greater than a(n-1) that cannot be written as a sum of any previous distinct terms.

0, 2, 4, 7, 10, 18, 33, 38, 86, 162, 284, 522, 928, 1688, 3022, 5470, 9826, 17744, 31926, 57588, 103696, 186946, 336750, 606946, 1093500, 1970642, 3550696, 6398480, 11529230, 20775494, 37435474, 67457232, 121552686, 219031676, 394679816, 711190482, 1281518438

Offset

0,2

Links

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

Mathematics Stack Exchange, Why a(n+3)=a(n+2)+2a(n+1)-a(n) for n>=8, where a(n+1) is the second smallest number that is not the sum of any earlier terms?

Formula

a(n+3) = a(n+2)+2a(n+1)-a(n) for n=5, n>=8.

Example

For n=4, a(4) = 10, because the numbers which cannot be expressed as a sum of any of 0,2,4,7 are 1,3,5,8,10,12,14,15,...

Prog

(Python)
MAX=10000
dp=[False]*(MAX+2)
an=0
dp[an]=True
while an<MAX:
  print(an)
  while dp[an]:
    an+=1
  an+=1
  while dp[an]:
    an+=1
  for i in reversed(range(an, MAX)):
    dp[i]|=dp[i-an]

Crossrefs

Sequence in context: A332639 A281168 A274352 * A088762 A217385 A138827

Adjacent sequences: A343325 A343326 A343327 * A343329 A343330 A343331

Keyword

easy,nonn

Author

Akihiko Yoshida, Apr 11 2021

Status

approved