# Generate the Stöhr sequence

I am learning Ruby and wrote my first nontrivial code to solve this problem.

The challenge is to generate the first n elements of the Stöhr sequence, S, which is defined as follows:

S = 1

S[n] is the smallest number that cannot be expressed as the sum of two distinct previous elements in the sequence.

Thus the sequence begins with 1, 2, 4, 7, and 10. The next element is 13, because 11 (=1+10) and 12 (=2+10) are sums of previous elements, but 13 is not.

I am looking for the shortest code. My own, in Ruby, is 108 characters long, but maybe I'll wait to see what others come up with before posting it?

• I like the answers so far. Now, it's perhaps too late to go back and change the requirements, but I suppose I should have mentioned that I'm particularly interested in solutions that use the definition of the sequence itself (i.e., the code doesn't know in advance that eventually the numbers go up by 3). So: moral bonus points if you can do that. Jan 26, 2015 at 13:09
• Such is the problem with mathematical sequences. If you know the pattern, it will usually be shorter.
– user8777
Jan 27, 2015 at 4:41
• This sequence is arithmetical without any use(?). Jan 6, 2018 at 19:39
• @user75200 The sequence is not arithmetical, as you can see from the differences in the first three elements, but the subsequence starting at the third element is indeed arithmetical. It is used in connection to the Postage Stamp problem. Jan 6, 2018 at 22:12

# APL, 7

In APL you can choose if you want to work with index 0 or index 1. You do this by setting global variable ⎕IO←0

If we choose to work in index 0 we have:

+\3⌊1⌈⍳


Explanation:

⍳    creates a sequence 0...n   (0 1 2 3 4 5)
1⌈   takes whichever is bigger, number in sequence or 1 (1 1 2 3 4 5)
3⌊   takes whichever is lower, number in sequence or 3 (1 1 2 3 3 3)
+\   partial sums for the sequence (1 2 4 7 10 13)


Try it on tryapl.org

• Can't you work with 1 based index and then create 1 to n array and simply prepend it with another 1 ? If that can be done, is it shorter ? Jan 27, 2015 at 10:18
• The code I got to was longer. This was my code for index 1, 10 chars: +\3⌊1,⍳¯1+ Also, the index-0 version works with argument 0 too, while this one does not. Jan 27, 2015 at 10:21
• Ah. yeah . APL really shined through here .. Jan 27, 2015 at 10:26

Lazy infinite sequence

1:2:[4,7..]


Function that returns just supplied number of members (sigh)

flip take$1:2:[4,7..]  • @Optimizer Well, technically, you have to "generate the first n elements of the Stöhr sequence"—it doesn't say you can't generate the rest of them as well! It doesn't say that you have to take an input, either. swish's original code actually does generate the first n terms, for any n. Jan 26, 2015 at 19:41 • @WChargin trying to being oversmart isn't new. Taking the OP's wording too literally and producing extra output than required both are considered as standard loopholes. Jan 26, 2015 at 19:42 • @Optimizer Actually, being lazy means no extra output would be generated until you ask for it, and you can ask for any terms you want. Jan 26, 2015 at 20:01 • @swish I don't understand. What is lazy here ? Jan 26, 2015 at 20:03 • @Optimizer The chunk that produces the sequence. Jan 26, 2015 at 20:04 # Python 2, 37 35 bytes lambda n:[1,2][:n]+range(4,n*3-4,3)  Making use of a pattern... • You can include the 4 in the range: lambda n:[1,2][:n]+range(4,n*3-4,3) Jan 26, 2015 at 11:19 • Nice find. Edited to 35 now. Jan 26, 2015 at 13:32 # CJam, 14 bytes 1l~{_p_3e<+}*;  Test it here. Starts at 1. Then, S[n] = S[n-1] + min(S[n-1], 3). 1l~{_p_3e<+}*; 1 "Push 1."; l~ "Read and evaluate input N."; { }* "Repeat this block N times.": _p "Duplicate the last number and print it."; _3e< "Duplicate it again, and take minimum with 3."; + "Add to last number."; ; "Discard final number to prevent output.";  This generalises easily to h-Stöhr sequences if we replace 3 by 2h-1. Brainfuck, 13 chars +.+.++.[+++.]  Or 30 chars if we want to limit it to n outputs: ,->+.<[->+.<[->++.<[->+++.<]]]  • I think you need to print the first n elements, not an infinite stream of them... Jan 26, 2015 at 11:04 • @Sp3000 Is using charcodes as numeric input and output accepted generally? Can't find on meta. With that it would be fairly easy to correct to BF code. Jan 26, 2015 at 11:13 • Personally I'm not sure what the general consensus is for this, sorry. I've had a bit of a problem with this too. Jan 26, 2015 at 11:19 • for the first n elements, i think i could do ->+.<[->+.<[->++.<[->+++.<]]] (29 chars), but that's not as elegant. And i don't think the language is specifically limited to using ASCII codes for input and output. Jan 26, 2015 at 11:48 • Your code have to answer the question even if it's not that elegant. I would suggest to edit the post and correct the answer to ,->+.<[->+.<[->++.<[->+++.<]]]. (You missed the input reading comma at the beginning.) Jan 26, 2015 at 12:35 # Python, 136 bytes def f(n): if n<1:return x=f(n-1);y=set(x)|{a+b for a in x for b in x if a!=b};return x+[min([a for a in range(1,max(y)+2)if{a}-y])]  Straight from the definition. I'm not sure how much I can golf this — it's certainly a lot longer than I expected. # J, 14 chars This just hardcodes the [1,2, 4+3*k (k=0..n-1) ] sequence and takes the first N.  ({.1,2,4+3*i.) 10 1 2 4 7 10 13 16 19 22 25  . # J, 18 chars This one uses a linear combination of [0,1,2,3...], [1,1,0,0...] and [0,1,1,1...]. Should be shorter but can't seem to golf it.  ((3&*+<&2-2**)@i.) 10 1 2 4 7 10 13 16 19 22 25  # Prelude, 32 20 Edit: ...with twice the voices now! ?(1-) 4 +3 2 ^ 1 !^  This assumes the Python interpreter with NUMERIC_OUTPUT = True. Like the Brainfuck submission this answer assumes that input is given in the form of a code point. This is partly to get more attention for this meta discussion (and partly, because I love Prelude). So if you want to print the first 32 numbers, say, you need to put a space on STDIN. Of course, this means there's an upper limit to the valid inputs, but this answer isn't winning anyway, so I think within the limitations of Prelude this is fine. ## Explanation In Prelude, all lines are executed in parallel, which line having its own stack, initialised to an infinite amount of zeroes. There is only a single instruction pointer (pointing at columns), so if you enter a loop on one voice, all other voices will loop along with it. In the following I've transpose the code, so that I can annotate lines instead of columns: ?421 Read a character into the first stack. Push 4, 2, 1 onto the other stacks, respectively. Generally, the fourth stack will hold the next number to be printed, the third stack the one after that, and the second stack the number two steps ahead. ( Start a loop if the input wasn't 0. 1+ ! Push a 1 onto the first stack. Add the top elements in the second stack. On the first iteration this will be 0 and 4, so it does nothing. On all further iterations this will increment the last number by 3. -3^^ Subtract one from the first stack. Push a 3 onto the second stack for the next iteration. Copy the last value from the second to the third, and the third to the fourth stack. ) If the top of the first stack is not 0, jump back to the column after the (.  # JavaScript (ES6) 92 As a recursive function based upon the problem definition S=(n,v=1,s=[],r=0)=>[for(a of s)for(b of s)r+=(a-b&&a+b==v)]|r||(s.push(v),--n)?S(n,v+1,s):s  Using the pattern 1,2, 1+3*k : 58 S=(n)=>(i=>{for(t=1;n>r.push(t+=i);i+=(i<3));})(0,r=[])||r  Side note: finding the h-Stöhr sequence (verifying the sum of up to h numbers instead of just 2). The R function tries all possibile sums of up a given number of list elements. S=(n,h=2,s=[],v=1,R=(t,v,l,i=0,r=t,w)=>{ for(;r&&l&&v[i];i++) w=[...v],r=!R(t-w.splice(i,1),w,l-1) return!r; })=>R(v,s,h)||(s.push(v),--n)?S(n,h,s,v+1):s  Ungolfed roughly equivalent (and ES5 compatible) function S(n, v, s) { var r=0,a,b v = v||1 s = s||[] for(a of s) for(b of s) { if (a != b && a+b == v) r++; } if (r == 0) { s.push(v); --n; } if (n != 0) return S(n,v+1,s) else return s }  Test In FireFox/FireBug console. Simple function: S(20)  [1, 2, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55] Advanced function: S(10,5)  [1, 2, 4, 8, 16, 32, 63, 94, 125, 156] # ><> (fish), 726549 46 chars 1n1-:?!;' 'o2n1-v v1&no' ':<4&;!?:< >-:?!;&3+^  Input is supplied to interpreter: >fish.py stohr.fish -v 10 1 2 4 7 10 13 16 19 22 25  My first ><> program, suggestions appreciated. • Oh, good! I was hoping someone would write a ><> program. Jan 27, 2015 at 4:04 # ><>, 31 bytes 4i1nao:?!;2nao1-:?!;$:nao3+$d0.  Reads in a single char, uses its code point (e.g. space = 32) and prints the numbers one on each line. # Perl6 22 / 30 I'm going to see if Perl6 can deduce the sequence for me. To do that I used the REPL built into Perl6 $ perl6
> 1,2,4,7...*
Unable to deduce arithmetic or geometric sequence from 2,4,7 (or did you really mean '..'?)
> 1,2,4,7,10...*
1 2 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 ...


Hmm, I see the pattern that Perl deduced. After 4 to get the next value you just add 3.

1,2,4,*+3...*


Which saves one character making the code to get an infinite list of the numbers in the Stöhr sequence 13 characters long.

This code only does something useful in the REPL since it prints the gist of the result for us. To get it to print otherwise you would have to explicitly tell Perl to print the results.

$perl6 -e 'say 1,2,4,*+3...*'  ( * + 3 is simply a way to get a code reference which returns 3 added to it's only argument. Other ways to write it would be {$_ + 3 }, or -> $i {$i + 3 }, or { $^i + 3 } or sub ($i){ $i + 3 } ) The shortest way to create something Callable to generate the first n elements is to get a slice of the elements. {(1,2,4,*+3...*)[^$_]} # 22


In void context that would generate the first $_ values, then promptly throw them away. In anything other than void context it creates an anonymous code block ( a basic subroutine without a name ) which takes one argument. # store it in a scalar variable my$sub = {(1,2,4,*+3...*)[^$_]}; say$sub.(5);
# 1 2 4 7 10

# use it immediately
say {(1,2,4,*+3...*)[^$_]}.(5); # 1 2 4 7 10 # pretend it always had a name my &Stöhr-first = {(1,2,4,*+3...*)[^$_]};
say Stöhr-first 5;


If you really think it has to have a name to qualify as a valid for this challenge you would probably do this:

sub s(\n){(1,2,4,*+3...*)[^n]} # 30


Though since s is also used for the substitution operator, to call this the parens are non-optional. ( You could have given it a different name I suppose )

say s(5);
# 1 2 4 7 10

• Unless specified otherwise in the challenge, submissions to code golf challenges have to be full programs or functions, not just snippets. Jan 27, 2015 at 8:54
• @MartinBüttner to be fair 1,2,4,*+3...* actually creates an object that will generate the values needed. I don't think that many people would actually create something Callable around something like that in Perl6. Jan 27, 2015 at 15:52

I see there is already a MUCH better java answer but i spent a while on this and i'm going to post it. even if it sucks.

## Java 313 char (+4 to fit it on screen)

import java.util.*;public class S{public static void main(String[] a){
while(S.size()<=new Integer(a)){if(S.contains(i)){}else{k=0;for(int j:S){
{System.out.println(x);}}}


always grateful to get any tips or pointers on how to improve

# Jelly, 6 bytes

Ż«3»1Ä


Try it online!

Exactly the same as the APL answer, uses the fact that the partial sums are $$\1, 1, 2, 3, 3, 3, ...\$$

Alternative 6 byters

## How it works

Ż«3»1Ä - Main link. Takes n on the left
Ż      - [0, 1, 2, ..., n]
«3    - Min with 3; [0, 1, 2, 3, 3, 3, ...]
»1  - Max with 1; [1, 1, 2, 3, 3, 3, ...]
Ä - Cumulative sum


The alternatives all work by generating the partial sums, just in different methods

## T-SQL 204

Assumes that the input is in a variable called @N. I can make a procedure if you want, but there really isn't a good way to get STD_IN in T-SQL.

Also, yay for moral bonus!

DECLARE @Q INT=0,@B INT=2
DECLARE @ TABLE(A INT)WHILE @N>0
BEGIN
SET @N-=1
WHILE @B>1
BEGIN
SET @Q+=1
SELECT @B=COUNT(*)FROM @ C,@ B WHERE C.A+B.A=@Q
END
INSERT INTO @ VALUES(@Q)SET @B=2
END
SELECT*FROM @

• Nice! I don't know much about SQL—how is @N used here? I see that it's set near the beginning, but then it doesn't seem to be referenced later. Jan 27, 2015 at 4:07
• It looks like @N is the "i" of the "for loop". Jan 27, 2015 at 7:02
• Jacob is right. The @N is the "i" of the for loop, which is a while loop in SQL. Essentially it cross joins the table with itself and finds pairs that add to @Q. If there's at least two pairs (i.e. not just a number with itself), then it skips it. Otherwise, it adds it to the table. @ is the name of the table. Jan 27, 2015 at 12:37

# Mathematica, 27 bytes

Hmmm, still no Mathematica answer? Here are two:

NestList[#+3~Min~#&,1,#-1]&
Array[i=1/2;i+=3~Min~i&,#]&


both define an unnamed pure function which receives an integer and returns a list of integers. This is based on the same recurrence relation as my CJam submission. Note that the Array-based code starts from 1/2, because the recurrence relation is always applied before the value is returned.

## Java, 46

n->IntStream.iterate(2,x->x==2?1:x+3).limit(n)

• This is a function in Java 8. Jan 27, 2015 at 4:40

# Python - not even close (139)

Acting under the assumption that this weren't easily calculable as others have done, the shortest solution I've found is below:

from itertools import combinations as C
x,i,n=[],1,input()
while len(x)<=n:
if i not in [sum(y) for y in C(x,2)]:x.append(i)
i+=1
print n


# Clojure - 130118

(defn s[n](last(take n(iterate #(if(<(count %)3)(conj %(+ (apply + %)1))(conj %(+(last %)(second %)(first %))))))))


Un-golfed version:

(defn stohr [n]
(last
(take n
(iterate #(if (< (count %) 3)
(conj % (+ (apply + %) 1))
(conj % (+ (last %) (second %) (first %)))) ))))


Share and enjoy.

# Ruby - 108 88

q=->n{*k=1;(m=k[-1];k<<([*m+1..2*m]-k.combination(2).map{|i,j|i+j}))while k.size<n;k}


This uses the definition of the sequence.

q=->n{
*k=1
(
m = k[-1]
k << ([*m+1..2*m] - k.combination(2).map{|i,j|i+j})
) while k.size < n
k
}


print q

[1, 2, 4, 7, 10, 13, 16, 19, 22, 25]

• Ruby golf tips: *k=1 instead of k=. foo while bar instead of while bar;foo;end. [*s..e] instead of (s..e).to_a. .map instead of to_a.map. {|a,b|a+b} instead of {|i|i.inject(:+)}. Jan 29, 2015 at 18:30
• @histocrat Thanks, that's very helpful! Jan 29, 2015 at 18:41

## STATA 51

di 1 2 _r(a)
loc b=3*\$a-2
forv x=4(3)b'{
di x'
}


# TI-BASIC, 4127 30 bytes

Input N:For(I,1,N:I:If I>2:(I-2)3+1:Disp Ans:End

n=argument0;for(i=1;i<=n;i++){t=i;if i>2t=(i-2)*3+1show_message(t)}