Generate the Stöhr sequence

Question

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?

Answer 1

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

Answer 2

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

Answer 3

Python 2, 37 35 bytes

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

Making use of a pattern...

Answer 4

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 2^h-1.

Answer 5

Brainfuck, 13 chars

+.+.++.[+++.]

Or 30 chars if we want to limit it to n outputs:

,->+.<[->+.<[->++.<[->+++.<]]]

Answer 6

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.

Answer 7

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

Answer 8

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

Answer 9

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]

Answer 10

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

Answer 11

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

Answer 12

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

Answer 13

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

Answer 14

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

Answer 15

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 @

Answer 16

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.

Answer 17

Java, 46

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

Answer 18

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

Answer 19

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.

Answer 20

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]

Answer 21

STATA 51

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

Answer 22

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

Answer 23

GML, 67 bytes

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