Uczę się Ruby i napisałem swój pierwszy nieprofesjonalny kod, aby rozwiązać ten problem.

Wyzwanie polega na wygenerowaniu pierwszych n elementów sekwencji Stöhr , S , która jest zdefiniowana następująco:

S [0] = 1

S [n] jest najmniejszą liczbą, której nie można wyrazić jako sumę dwóch różnych poprzednich elementów w sekwencji.

Zatem sekwencja zaczyna się od 1, 2, 4, 7 i 10. Kolejnym elementem jest 13, ponieważ 11 (= 1 + 10) i 12 (= 2 + 10) są sumami poprzednich elementów, ale 13 nie.

Szukam najkrótszego kodu. Mój własny, w Ruby, ma 108 znaków, ale może poczekam, aby zobaczyć, co wymyślą inni, zanim go opublikuję?

APL, 7

W APL możesz wybrać, czy chcesz pracować z indeksem 0, czy indeksem 1. Robisz to, ustawiając zmienną globalną ⎕IO ← 0

Jeśli zdecydujemy się na pracę w indeksie 0, mamy:

+\3⌊1⌈⍳

Wyjaśnienie:

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

Wypróbuj na tryapl.org

Haskell - 11 21

Leniwa nieskończona sekwencja

1:2:[4,7..]

Funkcja, która zwraca właśnie podaną liczbę członków (westchnienie)

flip take$1:2:[4,7..]

Python 2, 37 35 bajtów

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

Korzystanie ze wzoru ...

CJam, 14 bajtów

1l~{_p_3e<+}*;

Sprawdź to tutaj.

Zaczyna się od 1. Następnie 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.";

Uogólnia to łatwo do sekwencji h- Stöhr, jeśli zastąpimy 3 przez 2 ^h -1 .

Brainfuck, 13 znaków

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

Lub 30 znaków, jeśli chcemy ograniczyć go do n wyjść:

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

Python, 136 bajtów

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

Prosto z definicji. Nie jestem pewien, ile potrafię w golfa - to z pewnością dużo dłużej, niż się spodziewałem.

J, 14 znaków

To po prostu koduje [1,2, 4+3*k (k=0..n-1) ]sekwencję i zajmuje pierwszą N.

   ({.1,2,4+3*i.) 10
1 2 4 7 10 13 16 19 22 25

.

J, 18 znaków

Ten używa liniowej kombinacji [0,1,2,3...], [1,1,0,0...]i [0,1,1,1...]. Powinien być krótszy, ale wydaje się, że nie można go golfa.

   ((3&*+<&2-2**)@i.) 10
1 2 4 7 10 13 16 19 22 25

Preludium , 32 20

Edycja: ... teraz z dwoma głosami!

?(1-)
4 +3
2  ^
1 !^

To zakłada interpreter Pythona z NUMERIC_OUTPUT = True. Podobnie jak przesłanie Brainfuck, ta odpowiedź zakłada, że ​​dane wejściowe są podawane w postaci punktu kodowego. Ma to częściowo na celu zwrócenie większej uwagi na tę meta dyskusję (a częściowo dlatego, że uwielbiam Preludium). Więc jeśli chcesz wydrukować pierwsze 32 cyfry, powiedzmy, musisz wstawić spację na STDIN. Oczywiście oznacza to, że istnieje górna granica prawidłowych danych wejściowych, ale i tak odpowiedź nie wygrywa, więc myślę, że w granicach Preludium jest w porządku.

Wyjaśnienie

W Preludium wszystkie linie są wykonywane równolegle, przy czym linia ta ma własny stos, zainicjowana na nieskończoną liczbę zer. Jest tylko jeden wskaźnik instrukcji (wskazujący na kolumny), więc jeśli wejdziesz w pętlę jednego głosu, wszystkie inne głosy zapętlą się wraz z nim.

Poniżej transponowałem kod, dzięki czemu mogę adnotować linie zamiast kolumn:

?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

Jako funkcja rekurencyjna oparta na definicji problemu

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

Używając wzoru 1,2, 1 + 3 * k: 58

S=(n)=>(i=>{for(t=1;n>r.push(t+=i);i+=(i<3));})(0,r=[])||r

Uwaga dodatkowa: znalezienie sekwencji h-Stöhra (weryfikacja sumy maksymalnie hliczb zamiast tylko 2). RFunkcja próbuje wszystkich possibile sumy w wysokości określonej liczby elementów listy.

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

Nieoszlifowany z grubsza odpowiednik (i kompatybilny z ES5)

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
}

Testuj w konsoli FireFox / FireBug. Prosta funkcja:

S(20)

[1, 2, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55]

Funkcja zaawansowana:

S(10,5)

[1, 2, 4, 8, 16, 32, 63, 94, 125, 156]

> <> (ryba) , 72 65 49 46 znaków

1n1-:?!;' 'o2n1-v
v1&no' ':<4&;!?:<
>-:?!;&3+^

Dane wejściowe są dostarczane do tłumacza:

>fish.py stohr.fish -v 10
1 2 4 7 10 13 16 19 22 25

Mój pierwszy> <> program, sugestie mile widziane.

> <>, 31 bajtów

4i1nao:?!;2nao1-:?!;$:nao3+$d0.

Odczytuje pojedynczy znak, używa punktu kodowego (np. Spacja = 32) i drukuje liczby jeden w każdym wierszu.

Perl6 22/30

Zobaczę, czy Perl6 może wydedukować sekwencję dla mnie.

W tym celu wykorzystałem REPL wbudowany w 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, widzę wzór, który wydedukował Perl. Po 4, aby uzyskać następną wartość, po prostu dodajesz 3.

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

To oszczędza jeden znak, dzięki czemu kod uzyskuje nieskończoną listę liczb w sekwencji Stöhra o długości 13 znaków.

Ten kod robi tylko coś pożytecznego w REPL, ponieważ drukuje dla nas sedno wyniku. Aby go wydrukować, w przeciwnym razie musisz wyraźnie powiedzieć Perlowi, aby wydrukował wyniki.

$ perl6 -e 'say 1,2,4,*+3...*'

( * + 3jest po prostu sposobem na uzyskanie odwołania do kodu, które zwraca wartość 3 dodaną do jego jedynego argumentu. Inne sposoby zapisu to { $_ + 3 }, lub -> $i { $i + 3 }, lub { $^i + 3 }lub sub ($i){ $i + 3 })

Najkrótsza droga do stworzenia czegoś wywoływalnym do generowania pierwszych n elementów jest dostać kromkę elementów.

{(1,2,4,*+3...*)[^$_]} # 22

W pustym kontekście wygenerowałoby to pierwsze $_wartości, a następnie je wyrzucił.

W kontekście innym niż void kontekst tworzy anonimowy blok kodu (podstawowy podprogram bez nazwy), który przyjmuje jeden 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;

Jeśli naprawdę uważasz, że musi mieć nazwę kwalifikującą się do tego wyzwania, prawdopodobnie zrobiłbyś to:

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

Chociaż ponieważ sjest również używany w przypadku operatora podstawienia, wywołanie tego nie jest opcjonalne. (Przypuszczam, że mogłeś nadać mu inną nazwę)

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

Widzę, że jest już O wiele lepsza odpowiedź java, ale poświęciłem trochę czasu na to i zamierzam opublikować. nawet jeśli jest do bani.

Java 313 char (+4, aby zmieścił się na ekranie)

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

zawsze wdzięczny za wszelkie wskazówki lub wskazówki, jak poprawić

T-SQL 204

Zakłada, że ​​dane wejściowe znajdują się w zmiennej o nazwie @N. Mogę wykonać procedurę, jeśli chcesz, ale tak naprawdę nie ma dobrego sposobu na uzyskanie STD_IN w T-SQL.

Również, jeśli chodzi o premię moralną!

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 @

Mathematica, 27 bajtów

Hmmm, wciąż nie ma odpowiedzi Mathematica? Oto dwa:

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

oba definiują nienazwaną czystą funkcję, która otrzymuje liczbę całkowitą i zwraca listę liczb całkowitych. Jest to oparte na tej samej relacji powtarzalności, co przesłanie przez CJam. Zauważ, że Arraykod na podstawie zaczyna się od 1/2, ponieważ relacja powtarzalności jest zawsze stosowana przed zwróceniem wartości.

Java, 46

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

Python - nawet nie blisko (139)

Działając przy założeniu, że nie było to łatwe do obliczenia, jak zrobili to inni, najkrótsze rozwiązanie, jakie znalazłem, jest poniżej:

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 - 130 118

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

Wersja bez gry w golfa:

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

Udostępnij i ciesz się.

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

Wykorzystuje to definicję sekwencji.

Bardziej czytelna wersja:

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
}

wydrukuj q [10]

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

STATA 51

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

TI-BASIC, 41 27 30 bajtów

Do twojego kalkulatora

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

GML , 67 bajtów

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