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.

• nimi: 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.
• xnor: Beautiful method! The import seems like overkill though; filter(`notElem`scanl(+)x z)y should do.

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å_i1⁄4Dˆ

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
 1⁄4 # increase counter
 Dˆ # add current stack value to global array

Try it online!

Saved 1 byte thanks to Adnan

• Adnan: Does $ instead of Xs work?
• Emigna: @Adnan: Yes of course. Silly of me. Thanks!

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.

• Jakube: Using reduce saves (only) one byte. Expected more... eu+Gf!}TsM.:G))hQY
• Maltysen: @Jakube map is usually shorter for self referential sequences like these

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

• Neil: 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: Now that your if(!...){...} is only one statement, you could probably replace it with ...||(...) or ...?0:....

Answer 7

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ø
 ø 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

• Dominic van Essen: You can start with the empty list, instead of 1, for 11 bytes

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