15
\$\begingroup\$

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
\$\endgroup\$
12
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – nimi Sep 5 '16 at 19:25
  • 1
    \$\begingroup\$ Beautiful method! The import seems like overkill though; filter(`notElem`scanl(+)x z)y should do. \$\endgroup\$ – xnor Sep 5 '16 at 19:49
7
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Does $ instead of Xs work? \$\endgroup\$ – Adnan Sep 5 '16 at 20:12
  • \$\begingroup\$ @Adnan: Yes of course. Silly of me. Thanks! \$\endgroup\$ – Emigna Sep 5 '16 at 20:15
4
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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.

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

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)}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – Neil Sep 5 '16 at 21:18
  • 1
    \$\begingroup\$ Now that your if(!...){...} is only one statement, you could probably replace it with ...||(...) or ...?0:.... \$\endgroup\$ – Neil Sep 6 '16 at 7:57
1
\$\begingroup\$

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 %::.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.