Segmented numbers

Question

The sequence of segmented numbers or prime numbers of measurement (OEIS A002048) is the sequence of numbers such that each member is the smallest positive (greater than zero) number that can't be made of a sum of earlier consecutive numbers, with a(0) = 1.

Example

To calculate a(7) we first calculate a(0->6) = [1, 2, 4, 5, 8, 10, 14]. we then start from zero and go through numbers until we find one that is not the sum of one or more consecutive numbers in the sequence.

1  = 1
2  = 2
3  = 1 + 2
4  = 4
5  = 5
6  = 2 + 4
7  = 1 + 2 + 4
8  = 8
9  = 4 + 5
10 = 10
11 = 2 + 4 + 5
12 = 1 + 2 + 4 + 5
13 = 5 + 8
14 = 14
15 = ????

Since fifteen cannot be made by summing any consecutive subsequence and every number smaller can be fifteen is the next number in the sequence. a(7) = 15

Task

Your task is to take a number (via standard methods) and output the nth term in this sequence (via standard output methods). This is code-golf and you will be scored as such.

Test Cases

0 -> 1
1 -> 2
2 -> 4
3 -> 5
4 -> 8
5 -> 10
6 -> 14
7 -> 15
8 -> 16
9 -> 21

Answer 1

Haskell, 62 58 bytes

-4 bytes thanks to @xnor!

(x:y)#z=x:filter(`notElem`scanl(+)x z)y#(x:z)
([1..]#[]!!)

Sequence is 0-indexed.

Answer 2

Perl, 50 49 bytes

Includes +1 for -p

Run with input on STDIN:

segmented.pl <<< 7

segmented.pl:

#!/usr/bin/perl -p
${$_-=$\}++for@F;1while${-++$\};++$#F<$_&&redo}{

Explanation

@F contains the list of (negative) sums of consecutive numbers that end with the current last number. When a new number is discovered the list is extended with 0 and then all values are decreased by the new number maintaining the invariant.

Global %:: is used as a hash mapping all (negative) numbers that have been seen (through @F) to a non-zero value.

$\ is the current number and gets increased until it reaches a value not yet in %::.

By being a bit careful about the order in which everything happens no initialization is needed, 1 will automatically become the first number.

Since the size of @F is how many numbers have been generated it can be used as a halting condition

Answer 3

Jelly, 14 13 11 bytes

Ḷ߀Ẇ;ḅ1‘ḟ$Ṃ

Try it online!

How it works

Ḷ߀Ẇ;ḅ1‘ḟ$Ṃ  Main link. Argument: n

Ḷ            Unlength; yield [0, ..., n - 1].
 ߀          Recursively map the main link over the range.
   Ẇ         Window; yield all subarrays of consecutive elements of the result.
    ;        Append n to the array of subarrays.
     ḅ1      Convert all subarrays from base 1 to integer.
             This is equivalent to S€ (sum each), but it allows ; to hook.
         $   Combine the previous two links into a monadic chain.
       ‘       Increment all sums.
        ḟ      Filter; remove the original sums from the incremented ones.
          Ṃ  Compute the minimum.

Answer 4

05AB1E, 17 16 bytes

Xˆ$µ>D¯ŒOså_i¼Dˆ

Explanation

Xˆ                # initialize global array to [1]
  $               # push 1 and input to stack
   µ              # while counter != input
    >             # increase variable on stack
      ¯ŒO         # list of all sums of consecutive number in global array
     D   så_i     # if current stack value is not in the list
             ¼    # increase counter
              Dˆ  # add current stack value to global array

Try it online!

Saved 1 byte thanks to Adnan

Answer 5

Pyth - 19 17 bytes

Damn off-by one ruining all my implicits. (Same bytes count, literaly incrementing Q: =hQesmaYf!}TsM.:Y)

esmaYf!}TsM.:Y)1h

Test Suite.

Answer 6

Javascript, 125 112 110 bytes

Saved 2 bytes thanks to @Neil

f=n=>{a=[[]];for(i=1,z=0;z<=n;i++)a.some(b=>b.includes(i))||(a[z+1]=[0,...a[z++]||[]].map(v=>i+v));alert(i-1)}

Previous answers

112 bytes thanks to @Neil:

f=n=>{a=[[]];for(i=1,z=0;z<=n;i++)if(!a.some(b=>b.includes(i))){a[z+1]=[0,...a[z++]||[]].map(v=>i+v)}alert(i-1)}

125 bytes:

f=n=>{a=[[]];for(i=1,k=z=0;z<=n;i++)if(a.every(b=>b.every(c=>c-i))){a[i]=[i].concat((a[k]||[]).map(v=>i+v));k=i,z++}alert(k)}

Answer 7

Husk, ¹² 11 bytes

!¡ö←`-NmΣQø

Try it online!

returns nth term, 1-indexed.

-1 byte from Dominic Van Essen, using empty list.

Explanation

!¡ö←`-NmΣQø
          ø start with the empty list:
 ¡ö         apply the following infinitely:
         Q  get all subsequences
       mΣ   sum each of them
    `-N     remove the sums from natural numbers
   ←        take the first one
!           get the nth element from this list

Answer 8

Python, 113 105 92 80 bytes

s=F={1}
x=1
exec"while{x}<=s:x+=1\nF={x+j for j in{0}|F};s|=F\n"*input()
print x

The final bytes I saved were inspired by Ton’s Perl answer: my F does the same thing as his @F; my s does essentially the same thing as his %::.

Answer 9

JavaScript (ES6), 77 bytes

(n,a=[],s=a,i=1)=>s[i]?f(n,a,s,i+1):--n?f(n,[0,...a].map(j=>s[j+=i]=j),s,i):i

Basically a recursive port of the algorithm of @TonHospel's Perl answer.

Answer 10

Scala, 97 bytes

n=>{var(r,i)=Seq(1)->1;while(r.size<n+1){i+=1;r++=Set(i)--r.tails.flatMap(_.inits).map(_.sum)};i}

Try it online