# Segmented numbers

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

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


## Haskell, 62 58 bytes

-4 bytes thanks to @xnor!

(x:y)#z=x:filter(notElemscanl(+)x z)y#(x:z)
([1..]#[]!!)


Sequence is 0-indexed.

• I think you need two more bytes and surround the last line with () to make it a proper function. The partial applied !! is an operator section and must be enclosed in () to make it a function. Without it's just a snippet that only becomes a function (or "value" to use strict Haskell terms) with the missing argument.
– nimi
Sep 5 '16 at 19:25
• Beautiful method! The import seems like overkill though; filter(notElemscanl(+)x z)y should do.
– xnor
Sep 5 '16 at 19:49

# 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

# Jelly, 1413 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.  # 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 • Does $ instead of Xs work? Sep 5 '16 at 20:12
• @Adnan: Yes of course. Silly of me. Thanks! Sep 5 '16 at 20:15

# 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

• Using reduce saves (only) one byte. Expected more... eu+Gf!}TsM.:G))hQY Sep 5 '16 at 19:53
• @Jakube map is usually shorter for self referential sequences like these Sep 5 '16 at 20:01

## Javascript, 125112 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)}


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)}

• For b.every(c=>c-i), I'd try !b.includes(i) or possibly !a.some(b=>b.includes(i)) works, while [0,...a[k]||[]].map(v=>i+v) might replace [i].concat((a[k]||[]).map(v=>i+v)). Also do you really need k?
– Neil
Sep 5 '16 at 21:18
• Now that your if(!...){...} is only one statement, you could probably replace it with ...||(...) or ...?0:....
– Neil
Sep 6 '16 at 7:57

# Husk, 12 11 bytes

!¡ö←-NmΣQø


Try it online!

returns nth term, 1-indexed.

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

## Explanation

!¡ö←-NmΣQø
¡ö         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

• You can start with the empty list, instead of 1, for 11 bytes Dec 10 '20 at 0:11

# Python, 11310592 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 %::.

## 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.

# 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