Diberikan bilangan bulat n(di mana n < 10001) sebagai input, tulis sebuah program yang akan menampilkan n angka Ulam pertama . Nomor Ulam didefinisikan sebagai berikut:

1. U ₁ = 1, U ₂ = 2.
2. Sebab n > 2, U _n adalah bilangan bulat terkecil yang lebih besar dari U _n-1 yang merupakan jumlah dari dua istilah sebelumnya yang berbeda dalam satu cara.

Misalnya, U ₃ adalah 3(2 + 1), U ₄ adalah 4(3 + 1) (perhatikan bahwa (2 + 2) tidak dihitung karena persyaratannya tidak berbeda), dan U ₅ adalah 6, (U ₅ bukan 5 karena 5 dapat direpresentasikan sebagai 2 + 3 atau 4 + 1). Berikut adalah beberapa angka Ulam pertama:

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

Ini kode golf, jadi entri terpendek menang.

CJam, 47 41 37 byte

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

Cobalah online.

Contoh dijalankan

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

Bagaimana itu bekerja

Ide dasar ini adalah sebagai berikut:

1. Mulai dengan array A := [ 0 U₁ U₂ ... Uₖ ].

2. Hitung S, array dari semua jumlah x + ysehingga x,y ∊ Adan x < y.

3. Buang semua jumlah non-unik dari S. Karena setiap angka Ulam lebih besar dari 2 adalah jumlah dari dua yang lebih kecil dan jumlah nol dan itu sendiri, ini membuang angka-angka Ulam U₃, U₄, ... Uₖ.

4. Array yang tersisa adalah [ U₁ U₂ Uₖ₊₁ ... ], jadi angka Ulam berikutnya adalah elemen terkecil ketiga. Tambahkan ke Adan kembali ke langkah 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 char

Mengambil fungsi nsebagai argumen.

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

Dijelaskan oleh ledakan:

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

Saya telah melakukan sedikit penyalahgunaan SQL ringan.

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

Cobalah di SQL Server 2008 di sini .

@ N memegang integer input. Ubah contoh "100" menjadi apa yang seharusnya. "10000" mungkin akan selesai pada akhirnya, tapi aku belum membiarkannya selesai. Hitungan char entri ini adalah untuk input satu digit. Output dalam bentuk hasil kueri.

Haskell, 70 67 karakter

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

pemakaian:

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

GolfScript ( 41 37 byte)

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

Demo online

Produk Cartesian di GolfScript cukup panjang, jadi ini membutuhkan pendekatan yang berbeda. Pertumbuhan jangka panjang dari angka-angka Ulam adalah bahwa angka nUlam ke-sekitar 13.5n, tetapi dalam 10.000 istilah pertama rasio terbesar antara angka nke-Ulam dan nhanya di bawah 13.3. Jadi diberikann kita dapat memfilter 14nangka pertama untuk menemukan nomor yang termasuk dalam urutan.

Dengan terima kasih kepada Dennis untuk 41-> 37.

JavaScript ES6, 100 ... 93 90 karakter

Jalankan ini di Web Console atau Scratchpad dari Firefox terbaru (Malam atau rilis).

EDIT 8 Golf banyak !!! dan membuatnya menjadi 94 karakter 93 90 karakter (terima kasih kepada @openorclose). (Sub 100 pertama saya)

Ini adalah versi saya yang jauh lebih cepat tetapi lebih panjang 3 karakter (107 karakter) dan jumlah karakter yang persis sama seperti di atas dan jauh lebih kecil daripada metode brute force di bawah ini !, (terima kasih kepada 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

Saya akan terus mencoba golf lebih jauh. Tapi kami memerasnya dari ruang lingkup JS: P

Berikut adalah beberapa angka ketika saya menjalankan ini di dalam tag skrip di halaman web:

n waktu
10 0,001
100 0,005
1000 2.021
10000 236.983
100000       tldr tertunda ; Terlalu lama tidak berjalan: P

Ini adalah kiriman pertama saya yang sangat terinspirasi oleh jawaban @ rink.attendant.6 di 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]}

Saya tahu ini bisa bermain golf lebih jauh. Saya juga akan memposting solusi non-bruteforced, yang mungkin lebih pendek.

EDIT 1 : Golf sedikit lebih dan tetap untuk n = 1

Saya harus mengatakan bahwa saya iri pada Haskell dan J karena pintasan yang sangat berguna untuk setiap jenis persyaratan -_-

Perl - 71 byte

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

Cobalah online!

Menghitung shebang sebagai satu.
Menggunakan array kedua untuk menyimpan jumlah tampaknya jauh lebih cepat daripada hash. Penggunaan memori juga kurang, yang tidak saya duga.

Penggunaan sampel:

$ echo 30 | perl ulam.pl

Output sampel:

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

Perkiraan runtime:

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

Jawa, 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 bekerja dengan baik untuk ini.

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 byte

-1 byte oleh Adám

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

Cobalah 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\}$

* (Dalam ngn / APL, konstanta dapat mengakhiri kereta tanpa menggunakan ⍨. Tapi ngn / APL tidak memiliki hitungan, jadi kita perlu ⍨ suatu tempat.)

PHP 5.4+, 164

Pendekatan yang sama dengan jawaban saya:

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

Jelly , 20 byte

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

Cobalah 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

Akhir-akhir ini saya telah mempraktikkan CoffeeScript untuk meningkatkan dalam bermain golf JavaScript, jadi inilah jawaban JavaScript saya yang dikompilasi ke dalam 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]

Saya tidak mengerti loop dan pemahaman dalam CoffeeScript dengan sangat baik jadi mungkin ini bisa di-golf lebih lanjut tetapi itulah yang saya miliki untuk saat ini. Baris baru dihitung sebagai satu karakter (gaya Unix).

JavaScript, 147 154 150 (136)

Sangat terinspirasi oleh solusi Java Brute-force @ Ypnypn yang diposting sebelumnya:

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

Terima kasih untuk @Dennis karena mencukur 4 hingga 18 byte dari versi asli saya

Versi berbahaya (menggunakan for..inloop)

Saya tidak akan merekomendasikan menjalankan ini karena perulangan melalui objek yang menggunakan perulangan dapat menyebabkan mesin Anda terbakar dan / atau berubah menjadi mesin pembunuh yang marah, tapi ini dia: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)}

Tidak disatukan

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 byte

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

Ini adalah implementasi yang sangat langsung dari spesifikasi.

• Temukan semua pasangan.
• Hapus semua duplikat.
• Hapus semua angka kurang dari angka Ulam terakhir.
• Tambahkan minimum ke daftar.

Saya juga menerapkan trik Dennis untuk memasukkan jumlah 0 , tetapi hasilnya adalah ini membuat elemen ketiga dari daftar 0sebelum melanjutkan seperti yang diharapkan, jadi saya perlu menghapus elemen itu dari daftar.

Ini menangani input 1000dalam beberapa detik, tapi saya ragu Anda akan mendapatkan hasil 10k dalam jumlah waktu yang wajar. Tapi saya tidak berpikir ada yang melakukan dengan baik pada hal itu.

OCaml - 254 Karakter

Kode menggunakan tabel hash untuk menyimpan jumlah elemen saat ini dari daftar dan memperbaruinya setiap kali elemen baru dihitung.

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]

Pemakaian:

Dalam juru bahasa 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]

Tidak disatukan

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

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

Ini adalah golf pertama saya, dan saya telah menurunkannya dari ~ 250 karakter, saya cukup senang tetapi akan senang dengan saran tentang cara meningkatkan!

C #, 257

Pendekatan kekerasan, menggunakan 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));}}

Tidak Serigala, Dengan Test Harness

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 byte

<uaGh-sfq1lT.gksM.cG2GQS2

Cobalah online di sini .

<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

Sunting: golf 2 byte dengan melakukan penjumlahan sebelum pengelompokan. Versi sebelumnya:<uaGh-mssdfq1lT.gsk.cG2GQS2

C, 478 byte

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

Di Tio sekarang dalam 9 detik akan menemukan nilai 10.000 (dan di sana mencetak 100 nilai pertama). Triknya adalah menggunakan pencarian tidak linier di loop dalam tetapi pencarian biner ... Berikut ini adalah fungsi yang terindentasi dengan baik dan dapat dibaca penuh (akhirnya bagi saya):

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 char, 556 byte

∇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
∇

itu akan menjadi terjemahan dalam APL dari C yang saya kirim. Sepertinya saya tidak mengerti kapan harus menggunakan ∇∇ di tempat ∇ ... mungkin ∇∇ digunakan ketika ada satu argumen adalah satu fungsi (dan bukan satu tipe lainnya). "u bs x, a, b" harus menjadi pencarian bin di array "u" untuk nilai "x" dalam rentang a..b; itu akan mengembalikan 1, indexWhereFind atau 0, indexWhereEndOfsearch. Dengan fungsi argumen 200 p ambil + - sebentar di sini ...

  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