Biorąc pod uwagę liczbę całkowitą n(gdzie n < 10001) jako dane wejściowe, napisz program, który wyświetli pierwsze n liczby Ulam . Liczba Ulam jest zdefiniowana następująco:

1. U ₁ = 1, U ₂ = 2.
2. Bo n > 2U _n jest najmniejszą liczbą całkowitą większą niż U _n-1, która jest sumą dwóch różnych wcześniejszych wyrazów w dokładnie jeden sposób.

Na przykład U ₃ to 3(2 + 1), U ₄ to 4(3 + 1) (zauważ, że (2 + 2) się nie liczy, ponieważ warunki nie są odrębne), a U ₅ to 6(U ₅ to nie 5 ponieważ 5 można przedstawić jako 2 + 3 lub 4 + 1). Oto kilka pierwszych liczb Ulam:

1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99

To jest golf golfowy, więc wygrywa najkrótszy wpis.

CJam, 47 41 37 bajtów

li4,1${__m*{_~<\:+*}%$2/z:^$2=+}*1><`

Wypróbuj online.

Przykładowy przebieg

$ cjam <(echo 'li4,1${__m*{_~<\:+*}%$2/z:^$2=+}*1><`') <<< 26
[1 2 3 4 6 8 11 13 16 18 26 28 36 38 47 48 53 57 62 69 72 77 82 87 97 99]

Jak to działa

Ta podstawowa idea jest następująca:

1. Zacznij od tablicy A := [ 0 U₁ U₂ ... Uₖ ].

2. Oblicz S, tablicę wszystkich sum x + ytakich, że x,y ∊ Ai x < y.

3. Odrzuć wszystkie nie unikalne kwoty z S. Ponieważ każda liczba Ulam większa niż 2 jest zarówno sumą dwóch mniejszych, jak i sumą zera i samego siebie, to odrzuca liczby Ulam U₃, U₄, ... Uₖ.

4. Pozostała tablica jest [ U₁ U₂ Uₖ₊₁ ... ], więc następny numer Ulama jest trzecim najmniejszym elementem. Dołącz go Ai wróć do kroku 1.

li                                    " Read one integer (I) from STDIN.                  ";
  4,                                  " Push the array A = [ 0 1 2 3 ].                   ";
    1${                        }*     " Do the following I times:                         ";
       __m*                           " Push the Cartesian product A × A.                 ";
           {       }%                 " For each pair (x,y) in A × A:                     ";
            _~<\:+*                   " Compute (x + y) * (x < y).                        ";
                     $2               " Sort the resulting array.                         ";
                       /              " Split it into chunks of length 2.                 ";
                        z             " Transpose the resulting two-dimensional array.    ";
                         :^           " Compute the symmetric difference of its rows.     ";
                           $          " Sort the resulting array.                         ";
                            2=        " Extract its third element.                        ";
                              +       " Push it on the array A.                           ";
                                 1>   " Discard the first element of A (0).               ";
                                   <  " Discard all but the first I elements of A.        ";
                                    ` " Push a string representation of A.                ";

J - 46 znaków

Funkcja njako argument.

_2}.(,]<./@-.~</~({.+_*1<#)/.~@#&,+/~)@[&0&1 2

Wyjaśnione przez wybuch:

    (                                )          NB. procedure for a list:
                                  +/~           NB.   take an addition table
              </~              #&,              NB.   select the top right half (no diag)
                 (        )/.~@                 NB.   for each unique value:
                       1<#                      NB.     if more than one present
                  {.+_*                         NB.     add infinity to it
      ]    -.~                                  NB.   remove existing Ulam numbers
       <./@                                     NB.   take the smallest
     ,                                          NB.   append to Ulam numbers
                                      @[&0      NB. repeat this procedure:
                                          &1 2  NB.   n times starting with [1, 2]
_2}.                                            NB. drop the last two numbers

T-SQL, 301 300 288 287

Popełniłem lekkie nadużycie SQL.

DECLARE @N INT=100,@T INT=1DECLARE @ TABLE(I INT,U INT)INSERT @ VALUES(1,1),(2,2)#:IF @T>2INSERT @ SELECT TOP 1@T,A.U+B.U FROM @ A,@ B WHERE A.U>B.U GROUP BY A.U+B.U HAVING COUNT(*)=1AND A.U+B.U>ALL(SELECT U FROM @)ORDER BY 2SET @T+=1IF @T<=@N GOTO # SELECT U FROM @ WHERE I<=@N ORDER BY I

Wypróbuj w SQL Server 2008 tutaj .

@N przechowuje całkowitą liczbę wejściową. Zmień przykład „100” na n. „10000” prawdopodobnie ostatecznie skończy, ale nie pozwoliłem, by biegło do końca. Liczba znaków dla tego wpisu dotyczy jednej cyfry. Dane wyjściowe są w postaci wyników zapytania.

Haskell, 70 67 znaków

u n=take n$1:2:[x|x<-[1..],[_]<-[[y|y<-u$n-1,z<-u$n-1,y<z,y+z==x]]]

stosowanie:

>u 6
[1,2,3,4,6,8]

GolfScript ( 41 37 bajtów)

~.14*,3,\{1$.{2$1$-.@<*}%&,2=*|}/0-<`

Demo online

Produkty kartezjańskie w GolfScript są dość długie, więc to podejście jest inne. Długoterminowy wzrost liczby Ulamów jest taki, że nth liczba Ulam jest około 13.5n, ale w pierwszych 10000 kategoriach największy stosunek między ntą liczbą Ulam a njest tuż poniżej 13.3. Tak podanen że możemy filtrować pierwsze 14nliczby, aby znaleźć te, które należą do sekwencji.

Z podziękowaniami dla Dennisa za 41-> 37.

JavaScript ES6, 100 ... 93 90 znaków

Uruchom to w konsoli internetowej lub Scratchpad najnowszej przeglądarki Firefox (Nightly lub release).

EDYCJA 8 Dużo grał w golfa !!! i doprowadził do 94 znaków 93 90 znaków (dzięki @openorclose). (Moje pierwsze sub 100)

Oto moja wersja, która jest znacznie szybsza, ale ma 3 znaki dłuższe (107 znaków) i ma dokładnie taką samą liczbę znaków jak powyżej i jest znacznie mniejsza niż metoda brutalnej siły poniżej !, (dzięki edc65):

u=n=>(s=>{for(r=[i=l=1];c=l<n;i+=c&&i-2?1:s[r[l++]=i]=1)r.map(j=>c-=j<i/2&s[i-j])})([])||r

Będę próbował dalej grać w golfa. Ale wyciskamy to z zakresu JS: P.

Oto kilka liczb, kiedy uruchamiam to wewnątrz tagu skryptu na stronie internetowej:

n razy
10 0,001
100 0,005
1000 2.021
10000 236,983
100000       czeka tldr; Za długo nie działało: P

To jest moje pierwsze zgłoszenie, które jest mocno zainspirowane odpowiedzią @ rink.attendant.6 w JavaScript.

u=n=>{for(l=[1,g=2],i=3;g<n;++i){z=1;for(j of l)for(k of l)z-=j<k&j+k==i;!z?l[g++]=i:0}return n>1?l:[1]}

Wiem, że można to pograć jeszcze bardziej. Zamierzam również opublikować niewzmocnione rozwiązanie, które może być jeszcze krótsze.

EDYCJA 1 : Grał trochę bardziej w golfa i naprawił dla n = 1

Muszę powiedzieć, że zazdroszczę Haskellowi i J tak super przydatnych skrótów dla każdego rodzaju wymagań -_-

Perl - 71 bajtów

#!perl -p
@a=$b[2]=1;1while$b[++$a]^1||$_>map(++$b[$_+$a],@a)&&push@a,$a;$_="@a"

Wypróbuj online!

Licząc shebang jako jeden.
Używanie drugiej tablicy do przechowywania sum wydaje się znacznie szybsze niż skrót. Zużycie pamięci jest również mniejsze, czego nie spodziewałbym się.

Przykładowe użycie:

$ echo 30 | perl ulam.pl

Przykładowe dane wyjściowe:

1 2 3 4 6 8 11 13 16 18 26 28 36 38 47 48 53 57 62 69 72 77 82 87 97 99 102 106 114 126

Przybliżone czasy działania:

n = 100     0.015s
n = 1000    0.062s
n = 10000   4.828s

Java, 259

import java.util.*;class C{public static void main(String[]a){List<Integer>l=new ArrayList<>();l.add(1);l.add(2);for(int i=3,z=0;l.size()<new Long(a[0]);i++,z=0){for(int j:l){for(int k:l){if(j<k&j+k==i)z++;}}if(z==1)l.add(i);}l.forEach(System.out::println);}}

Brute force sprawdza się w tym przypadku.

import java.util.*;
class C {
    public static void main(String[] a) {
        List<Integer>l = new ArrayList<>();
        l.add(1);
        l.add(2);
        for (int i = 3, z = 0; l.size() < new Long(a[0]); i++, z = 0) {
            for (int j : l) {
                for (int k : l) {
                    if (j < k & j + k == i)
                        z++;
                }
            }
            if (z == 1)
                l.add(i);
        }
        l.forEach(System.out::println);
    }
}

APL (Dyalog Extended) , 36 35 bajtów

-1 bajt autorstwa Adáma

{⍵↑{⍵,⊃∧(∊⊢⊆⍨⍧⍨∊2 3⍨)⍵~⍨,+⍀⍨⍵}⍣⍵⍳2}

Wypróbuj online!

{⍵↑{⍵,⊃∧(∊⊢⊆⍨⍧⍨∊2 3⍨)⍵~⍨,+⍀⍨⍵}⍣⍵⍳2}      Monadic function taking an argument n:

{⍵,⊃∧(∊⊢⊆⍨⍧⍨∊2 3⍨)⍵~⍨,+⍀⍨⍵}   Helper function to compute the next Ulam number
                                    given ⍵ (the first few Ulam numbers)
                        +⍀⍨⍵      Make an addition table from ⍵.
                       ,          Flatten into a list.
                   ⍵~⍨            Remove all entries already in ⍵.

     (∊⊢⊆⍨2 3∊⍨⍧⍨)               Helper function taking an argument x:
                ⍧⍨                  The count of elts of x in itself                 
           2 3∊⍨                    1s where those counts are in (2 3), else 0s.*
       ⊢⊆⍨                          Partition x, removing values corresponding to 0s.
      ∊                             Join the partitions into a single list.

    (∊⊢⊆⍨⍧⍨∊2 3⍨)                Keep all elements that occur exactly 2 or 3 times.
                                  (i.e. that occur once as a
                                  sum of distinct elements of ⍵).
    ∧                         Sort ascending.
   ⊃                          Take the first value (the next Ulam #).
 ⍵,                           Append that value to ⍵.

{⍵↑{...}⍣⍵⍳2}
{  {...}⍣⍵  }                 Call the helper function n times
           ⍳2                 starting with (1 2). First n+2 Ulam numbers.
 ⍵↑                           Keep the first n elements.

$x$$x$$x$$2a+b$$a$$x$$b$$x$$a=1$$2a+b \in \{ 2, 3\}$

* (W ngn / APL stała może zakończyć pociąg bez użycia ⍨. Ale ngn / APL nie ma odliczania, więc musimy gdzieś ⍨.)

PHP 5.4+, 164

Takie samo podejście jak moje odpowiedzi:

<?function u($n){for($l=[1,2],$i=3;count($l)<$n;++$i){$z=0;foreach($l as $j){foreach($l as $k){$z+=$j<$k&$j+$k==$i;}}if($z==1)$l[]=$i;}return array_slice($l,0,$n);}

Galaretka , 20 bajtów

Œc§ḟµḟœ-Q$Ṃɓ;
2RÇ⁸¡ḣ

Wypróbuj online!

Œc§ḟµḟœ-Q$Ṃɓ;    Helper link that appends the next number to x, a list of Ulam numbers:
Œc                  All unordered pairs of x
  §                 Sum each pair
   ḟ                Filter out the numbers already present in x.
    µ               Let this list be y. Then apply the following chain:

     œ-Q$Ṃ          Find the minimum of all unique elements.
     ḟ                Take y and filter out the elements in
      œ-Q$            the multiset difference between y and its unique elements.
          Ṃ           Then find the Ṃinimum of the result.

           ɓ;    Append (ɓ reverses argument order) the result to 


2RÇ⁸¡ḣ           Main link:
2R               Start with [1,2].
  Ç⁸¡            Apply the helper link (Ç) n (⁸) times to generate n+2 Ulam #s.
     ḣ           Keep the first n values.

CoffeeScript, 119 114

Ostatnio ćwiczyłem CoffeeScript, aby poprawić golfowy JavaScript, więc oto moja odpowiedź JavaScript skompilowana w CoffeeScript:

u=(n)->l=[1,2];i=3;z=0;(for j in l
 for k in l
  z+=j<k&j+k==i
l.push(i) if z==1;++i;z=0)while l.length<n;l[..n-1]

Nie rozumiem dobrze pętli i rozumienia w CoffeeScript, więc być może można to pograć w golfa, ale na razie to mam. Nowe linie są liczone jako jeden znak (styl uniksowy).

JavaScript, 147 154 150 (136)

Mocno zainspirowany wcześniej napisanym przez @ Ypnypn rozwiązaniem Java brute-force:

function u(n){for(l=[1,2],i=3;l.length<n;++i){z=0;l.forEach(function(j){l.forEach(function(k){z+=j<k&j+k==i})});if(z==1)l.push(i)}return l.slice(0,n)}

Dzięki za @Dennis za zgolenie od 4 do 18 bajtów mojej oryginalnej wersji

Niebezpieczna wersja (przy użyciu for..inpętli)

Nie polecałbym uruchamiania tego, ponieważ zapętlanie przez obiekt będący pętlą używającą może spowodować, że twoja maszyna wybuchnie w płomieniach i / lub przekształci się w gniewną maszynę do zabijania, ale oto ona:instanceof Arrayfor..in

function u(n){for(l=[1,2],i=3;l.length<n;++i){z=0;for(j in l)for(k in l)z+=l[j]<l[k]&l[j]+l[k]==i;if(z==1)l.push(i)}return l.slice(0,n)}

Nie golfił

function u(n) {
    var l = [1, 2],
        i = 3,
        j, k, z;

    for (; l.length < n; ++i) {
        z = 0; 
        l.forEach(function (j) {
            l.forEach(function (k) {
                if (j < k & j + k === i) {
                    z++;
                }
            });
        });
        if (z === 1) {
            l.push(i);
        }
    }

    return l.slice(0, n);
}

Mathematica, 107 91 bajtów

Nest[#~Append~Min@Cases[Tally[Tr/@#~Subsets~2],{n_,1}:>n]&,{1,2},i=Input[]]~Drop~{3}~Take~i

Jest to bardzo bezpośrednie wdrożenie specyfikacji.

• Znajdź wszystkie pary.
• Usuń wszystkie duplikaty.
• Usuń wszystkie liczby mniejsze niż ostatni numer Ulam.
• Dołącz minimum do listy.

Stosuję też sztuczkę Dennisa polegającą na dodawaniu sum 0, ale haczyk polega na tym, że powoduje to, że trzeci element listy 0przed wznowieniem jest zgodny z oczekiwaniami, więc muszę usunąć ten element z listy.

Obsługuje dane wejściowe 1000w ciągu kilku sekund, ale wątpię, aby uzyskać wynik za 10k w rozsądnym czasie. Ale nie sądzę, żeby którykolwiek z pozostałych wypadł dobrze w tej kwestii.

OCaml - 254 znaków

Kod używa tabeli skrótów do przechowywania sumy bieżących elementów listy i aktualizuje ją za każdym razem, gdy obliczany jest nowy element.

open Hashtbl let h=create 7 let()=add h 3 1 let rec r n i l=if n=0then List.rev l else if mem h i&&find h i=1then(List.iter(fun x->if mem h(x+i)then replace h(x+i)2else add h(x+i)1)l;r(n-1)(i+1)(i::l))else r n(i+1)l let u n=if n=1then[1]else r(n-2)3[2;1]

Stosowanie:

W ramach interpretera OCaml:

# u 26;;
- : int list =
[1; 2; 3; 4; 6; 8; 11; 13; 16; 18; 26; 28; 36; 38; 47; 48; 53; 57; 62; 69;
 72; 77; 82; 87; 97; 99]

Nie golfił

open Hashtbl
let h = create 7
let() = add h 3 1
let rec r n i l =
  if n=0 then List.rev l
  else if mem h i && find h i=1 then
    begin
      List.iter
        (fun x-> if mem h(x+i) then replace h (x+i) 2 else add h (x+i) 1)
        l;
      r (n-1) (i+1) (i::l)
    end
  else r n (i+1) l

let u n = if n=1 then [1] else r (n-2) 3 [2;1]

Python, 137 128 126 znaków.

U,i=[1,2],2
for _ in [[0]]*(input()-2):
 t=_*3*i
 for a in U:
  for b in U:t[a+b]+=a!=b
 i=t[i+1:].index(2)+i+1;U+=[i]
print U

To jest mój pierwszy golf i zredukowałem go z ~ 250 postaci, jestem bardzo szczęśliwy, ale chętnie podpowiemy, jak poprawić!

C #, 257

Podejście brutalnej siły przy użyciu LINQ:

using System.Linq;class U{void F(int n){var u=n<2?new int[]{1}:new int[]{1,2};for(int i=3;u.Length<n;++i)if(u.SelectMany(x=>u,(a,b)=>new{A=a,B=b}).Count(x=>x.A>x.B&&x.A==i-x.B)==1)u=u.Union(new int[]{i}).ToArray();System.Console.Write(string.Join("",u));}}

Bez golfa, z uprzężą testową

using System.Linq;
class Ulam
{
    void F(int n)
    {
        //handle special case where n = 1 (ugh)
        var u = n < 2 ? new int[] { 1 } : new int[] { 1, 2 };
        for (int i=3; u.Length<n; ++i)
            if (u.SelectMany(x => u, (a, b) => new { A = a, B = b })
                     .Count(x => x.A > x.B && x.A == i - x.B) == 1)
                u = u.Union(new int[] { i }).ToArray();
        System.Console.Write(string.Join(" ",u));
    }
    public static void Main(string[] args)
    {
        new Ulam().F(1);
        System.Console.WriteLine();
        new Ulam().F(2);
        System.Console.WriteLine();
        new Ulam().F(3);
        System.Console.WriteLine();
        new Ulam().F(26);
        System.Console.WriteLine();
    }
}

Pyth, 27 25 bajtów

<uaGh-sfq1lT.gksM.cG2GQS2

Wypróbuj online tutaj .

<uaGh-sfq1lT.gksM.cG2GQS2Q   Implicit: Q=eval(input())
                             Trailing Q inferred
 u                    Q      Perform the following Q times...
                       S2    ... with G initialised to [1,2]:
                 .cG2          Get all 2-element combinations of G
               sM              Sum each pair
            .gk                Group them by value
                                 The groups are sorted by the result of the sum
       f                       Filter the groups, as T, keeping those where:
          lT                     Length of T
        q1                       Equal to 1
      s                        Flatten list
     -               G         Remove elements of the above which are already in G
    h                          Take the first of the remaining elements
                                 This is the smallest, as the grouping also sorted them
  aG                           Append this to G
<                        Q   Take the first Q elements, implicit print

Edycja: grał w golfa 2 bajty, wykonując sumowanie przed grupowaniem. Poprzednia wersja:<uaGh-mssdfq1lT.gsk.cG2GQS2

C, 478 bajtów

#define R return
bs(x,v,l,h,r)unsigned x,*v,l,h,*r;{unsigned m;for(;l<=h;){m=(l+h)/2;if(x<v[m])h=m-1;else if(x>v[m])l=m+1;else{*r=m;R 1;}}*r=m;R 0;}
#include<stdlib.h>
unsigned*f(unsigned w){unsigned*u=0,i,k,m,y,z;if(w>1E6||w==0)R u;u=malloc(w*sizeof*u);if(!u)R u;k=0;u[k++]=1;if(w==1)R u;m=u[k++]=2;if(w==2)R u;l:for(i=0,y=0,z=k-1,++m;i<k;y+=bs(m-u[i],u,i+1,z,&z),++i)if(y>1||u[i]+(i+1!=k?u[i+1]:0)>m)break;if(m==0){free(u);u=0;R u;}if(y!=1)goto l;u[k++]=m;if(k< w)goto l;R u;}

W Tio teraz za 9 sekund znajdzie 10000 wartości (i tam wydrukuje pierwsze 100 wartości). Sztuką jest użycie nieliniowego wyszukiwania w wewnętrznej pętli, ale wyszukiwanie binarne ... Poniżej znajdują się funkcje dobrze wcięte i w pełni czytelne (w końcu dla mnie):

bsCopy(x,v,l,h,r)unsigned x,*v,l,h,*r;
{unsigned m;
 for(;l<=h;){m=(l+h)/2;if(x<v[m])h=m-1;else if(x>v[m])l=m+1;else{*r=m;R 1;}}
 *r=m;R 0;// in *r if return 0 the min index that fail else the index of find x
}

unsigned*fCopy(unsigned w)
{unsigned*u=0,i,k,m,y,z;
 if(w>1E6||w==0)R u;
 u=malloc(w*sizeof*u);
 if(!u)R u;
 k=0;u[k++]=1;if(w==1)R u;
   m=u[k++]=2;if(w==2)R u;//below I suppose m-u[i] is in the range (if exist in u) (i+1)..z 
 l: for(i=0,y=0,z=k-1,++m;i<k;y+=bsCopy(m-u[i],u,i+1,z,&z),++i)
          if(y>1||u[i]+(i+1!=k?u[i+1]:0)>m)break;
   if(m==0){free(u);u=0;R u;}
          if(y!=1)goto l;
   u[k++]=m;if(k< w)goto l;
 R u;
}

APL (NARS), 278 znaków, 556 bajtów

∇u←p w;m;y;i;k;z;r;bs
bs←{(x l h)←⍵⋄l>h:0,h⋄x<⍺[t←⌊2÷⍨l+h]:⍺∇x,l,t-1⋄x>⍺[t]:⍺∇x,(t+1),h⋄1,t}
u←⍬  ⋄→0×⍳(w>1E6)∨w≤0
u←u,1⋄→0×⍳w=1
u←u,2⋄→0×⍳w=2⋄k←m←2
i←1⋄y←0⋄m+←1⋄z←k
→7×⍳(y>1)∨i>k⋄→7×⍳m<u[i]+{i=k:0⋄u[i+1]}⋄r←u bs(m-u[i]),(i+1),z⋄y+←↑r⋄z←2⊃r⋄i+←1⋄→6
→5×⍳y≠1⋄u←u,m⋄k+←1⋄→5×⍳k<w
∇

byłoby to tłumaczenie w APL C jednego, które wysłałem. Wydaje się, że nie rozumiem, kiedy użyć ∇∇ zamiast ∇ ... możliwe ∇∇ jest używane, gdy istnieje jeden argument to jedna funkcja (a nie inny typ). „u bs x, a, b” powinno być wyszukiwaniem bin w tablicy „u” dla wartości „x” w zakresie a..b; zwróci 1, indexWhereFind lub 0, indexWhereEndOfsearch. Z funkcją argumentu 200 p weź + - minuta tutaj ...

  p 100
1 2 3 4 6 8 11 13 16 18 26 28 36 38 47 48 53 57 62 69 72 77 82 87 97 99 102 106 114 126 
  131 138 145 148 155 175 177 180 182 189 197 206 209 219 221 236 238 241 243 253 
  258 260 273 282 309 316 319 324 339 341 356 358 363 370 382 390 400 402 409 412 
  414 429 431 434 441 451 456 483 485 497 502 522 524 544 546 566 568 585 602 605 
  607 612 624 627 646 668 673 685 688 690 
  p¨1 2 3 4
1  1 2  1 2 3  1 2 3 4