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[0] = 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. – Théophile Jan 26 '15 at 13:09
  • Such is the problem with mathematical sequences. If you know the pattern, it will usually be shorter. – user8777 Jan 27 '15 at 4:41
  • This sequence is arithmetical without any use(?). – user75200 Jan 6 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. – Théophile Jan 6 at 22:12

22 Answers 22

up vote 13 down vote accepted

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 ? – Optimizer Jan 27 '15 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. – Moris Zucca Jan 27 '15 at 10:21
  • Ah. yeah . APL really shined through here .. – Optimizer Jan 27 '15 at 10:26

Haskell - 11 21

Lazy infinite sequence

1:2:[4,7..]

Function that returns just supplied number of members (sigh)

flip take$1:2:[4,7..]
  • You have to take an input and print only the first n numbers. – Optimizer Jan 26 '15 at 11:15
  • 4
    @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. – wchargin Jan 26 '15 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. – Optimizer Jan 26 '15 at 19:42
  • 2
    @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. – swish Jan 26 '15 at 20:01
  • 1
    @swish I don't understand. What is lazy here ? – Optimizer Jan 26 '15 at 20:03

Python 2, 37 35 bytes

lambda n:[1,2][:n]+range(4,n*3-4,3)

Making use of a pattern...

  • 1
    You can include the 4 in the range: lambda n:[1,2][:n]+range(4,n*3-4,3) – Jakube Jan 26 '15 at 11:19
  • Nice find. Edited to 35 now. – Logic Knight Jan 26 '15 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:

,->+.<[->+.<[->++.<[->+++.<]]]
  • 1
    I think you need to print the first n elements, not an infinite stream of them... – Sp3000 Jan 26 '15 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. – randomra Jan 26 '15 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. – Sp3000 Jan 26 '15 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. – jgosar Jan 26 '15 at 11:48
  • 1
    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.) – randomra Jan 26 '15 at 12:35

Python, 136 bytes

def f(n):
 if n<1:return[1]
 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), 72 65 49 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. – Théophile Jan 27 '15 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. – Martin Ender Jan 27 '15 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. – Brad Gilbert b2gills Jan 27 '15 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){
Set<Integer> S=new HashSet<Integer>();S.add(1);int i=1,k=0;
while(S.size()<=new Integer(a[0])){if(S.contains(i)){}else{k=0;for(int j:S){
for(int l:S){if(l!=j){if((j+l)==i)k=1;}}}if(k==0)S.add(i);}i++;}for(int x:S)
{System.out.println(x);}}}

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

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. – Théophile Jan 27 '15 at 4:07
  • It looks like @N is the "i" of the "for loop". – Jacob Jan 27 '15 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. – bmarks Jan 27 '15 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)

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 %))))[1]))))

Un-golfed version:

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

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})[0])while k.size<n;k}

This uses the definition of the sequence.

More readable version:

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

print q[10]

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

  • Ruby golf tips: *k=1 instead of k=[1]. 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(:+)}. – histocrat Jan 29 '15 at 18:30
  • @histocrat Thanks, that's very helpful! – Théophile Jan 29 '15 at 18:41

STATA 51

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

TI-BASIC, 41 27 30 bytes

For your calculator

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

GML, 67 bytes

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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