Étant donné un entier n(où n < 10001) en entrée, écrivez un programme qui produira les premiers n nombres Ulam . Un nombre Ulam est défini comme suit:

1. U ₁ = 1, U ₂ = 2.
2. En effet n > 2, U _n est le plus petit entier supérieur à U _n-1 qui est la somme de deux termes antérieurs distincts d' une seule manière.

Par exemple, U ₃ est 3(2 + 1), U ₄ est 4(3 + 1) (notez que (2 + 2) ne compte pas car les termes ne sont pas distincts), et U ₅ est 6, (U ₅ n'est pas 5 car 5 peut être représenté par 2 + 3 ou 4 + 1). Voici les premiers nombres d'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

C'est le golf de code, donc l'entrée la plus courte gagne.

CJam, 47 41 37 octets

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

Essayez-le en ligne.

Exemple d'exécution

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

Comment ça fonctionne

Cette idée de base est la suivante:

1. Commencez par le tableau A := [ 0 U₁ U₂ ... Uₖ ].

2. Calculer S, le tableau de toutes les sommes x + ytelles que x,y ∊ Aet x < y.

3. Jetez toutes les sommes non uniques de S. Puisque chaque nombre Ulam supérieur à 2 est à la fois la somme de deux plus petits et la somme de zéro et de lui-même, cela supprime les nombres Ulam U₃, U₄, ... Uₖ.

4. Le tableau restant est [ U₁ U₂ Uₖ₊₁ ... ], donc le prochain nombre Ulam est le troisième plus petit élément. Ajoutez-le à Aet revenez à l'étape 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 car

Prise de fonction ncomme argument.

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

Expliqué par l'explosion:

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

J'ai commis un petit abus SQL léger.

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

Essayez-le dans SQL Server 2008 ici .

@N contient l'entier d'entrée. Changez l'exemple "100" en ce que n devrait être. "10000" finira probablement par la suite, mais je n'ai pas laissé cela se terminer. Le nombre de caractères de cette entrée correspond à une entrée à un chiffre. La sortie est sous forme de résultat de requête.

Haskell, 70 67 caractères

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

usage:

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

GolfScript ( 41 37 octets)

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

Démo en ligne

Les produits cartésiens dans GolfScript sont assez longs, donc cela prend une approche différente. La croissance à long terme des nombres Ulam est que le nnombre Ulam est d'environ 13.5n, mais dans les 10000 premiers termes le plus grand rapport entre le nnombre Ulam et nest juste inférieur 13.3. Donc, étant donné que nnous pouvons filtrer les premiers 14nnombres pour trouver ceux qui appartiennent à la séquence.

Merci à Dennis pour 41-> 37.

JavaScript ES6, 100 ... 93 90 caractères

Exécutez ceci dans la console Web ou le bloc-notes du dernier Firefox (tous les soirs ou version).

EDIT 8 Golfé beaucoup !!! et il est descendu à 94 caractères 93 90 caractères (merci à @openorclose). (Mon premier sous 100)

Voici ma version qui est beaucoup plus rapide mais qui fait 3 caractères de plus (107 caractères) et qui est exactement la même quantité de caractères que ci - dessus et est beaucoup plus petite que la méthode de force brute ci-dessous !, (grâce à 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

Je continuerai d'essayer de jouer au golf plus loin. Mais nous le tirons hors de la portée de JS: P

Voici quelques chiffres lorsque je l'exécute dans une balise de script dans une page Web:

n fois
10 0,001
100 0,005
1000 2.021
10000 236,983
100000       tldr en attente ; Trop longtemps n'a pas fonctionné: P

Ceci est ma première soumission qui est fortement inspirée par la réponse de @ rink.attendant.6 en 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]}

Je sais que cela peut être joué encore plus loin. Je publierai également une solution non bruteforce, qui pourrait être encore plus courte.

EDIT 1 : Golfé un peu plus et fixé pour n = 1

Je dois dire que j'envie Haskell et J pour de tels raccourcis super pratiques pour chaque type d'exigence -_-

Perl - 71 octets

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

Essayez-le en ligne!

Compter le shebang comme un.
L'utilisation d'un deuxième tableau pour stocker les sommes semble être beaucoup plus rapide qu'un hachage. L'utilisation de la mémoire est également moindre, ce à quoi je ne m'attendais pas.

Exemple d'utilisation:

$ echo 30 | perl ulam.pl

Exemple de sortie:

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

Temps d'exécution approximatifs:

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

La force brute fonctionne bien pour cela.

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 octets

-1 octet par Adám

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

Essayez-le en ligne!

{⍵↑{⍵,⊃∧(∊⊢⊆⍨⍧⍨∊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\}$

* (Dans ngn / APL, une constante peut terminer un train sans utiliser ⍨. Mais ngn / APL n'a pas de décompte, nous avons donc besoin de ⍨ quelque part.)

PHP 5.4+, 164

Même approche que mes réponses:

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

Gelée , 20 octets

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

Essayez-le en ligne!

Œ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

Dernièrement, j'ai pratiqué CoffeeScript pour améliorer le golf avec JavaScript, alors voici ma réponse JavaScript compilée dans 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]

Je ne comprends pas très bien les boucles et les compréhensions dans CoffeeScript, donc cela peut être approfondi, mais c'est ce que j'ai pour l'instant. Les sauts de ligne sont comptés comme un caractère (style Unix).

JavaScript, 147 154 150 (136)

Fortement inspiré par la solution Java à force brute de @ Ypnypn publiée précédemment:

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

Merci pour @Dennis d'avoir rasé de 4 à 18 octets sur ma version originale

Version dangereuse (utilisant des for..inboucles)

Je ne recommanderais pas d'exécuter cela parce que parcourir un objet qui utilise une boucle pourrait provoquer l'éclatement de votre machine et / ou la transformer en une machine à tuer en colère, mais voici: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)}

Non golfé

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 octets

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

C'est une implémentation très directe de la spécification.

• Trouvez toutes les paires.
• Supprimez tous les doublons.
• Supprimez tous les numéros inférieurs au dernier numéro Ulam.
• Ajoutez le minimum à la liste.

J'applique également l'astuce de Dennis d'inclure des sommes avec 0, mais le problème est que cela fait le troisième élément de la liste 0avant de reprendre comme on pourrait s'y attendre, donc je dois supprimer cet élément de la liste.

Il gère une entrée de 1000en quelques secondes, mais je doute que vous obtiendrez un résultat pour 10k dans un délai raisonnable. Mais je ne pense pas que les autres réussissent bien non plus.

OCaml - 254 caractères

Le code utilise une table de hachage pour stocker la somme des éléments actuels de la liste et la mettre à jour chaque fois qu'un nouvel élément est calculé.

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]

Usage:

Dans l'interpréteur 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]

Non golfé

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 caractères.

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

Ceci est mon premier golf, et je l'ai ramené de ~ 250 caractères, je suis assez content mais j'aimerais des suggestions sur la façon de s'améliorer!

C #, 257

Approche par force brute, utilisant 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));}}

Non golfé, avec harnais de test

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 octets

<uaGh-sfq1lT.gksM.cG2GQS2

Essayez-le en ligne ici .

<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

Edit: golfé 2 octets en effectuant la sommation avant le regroupement. La version précédente:<uaGh-mssdfq1lT.gsk.cG2GQS2

C, 478 octets

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

Dans Tio maintenant, en 9 secondes, il trouverait 10000 valeurs (et y imprimerait les 100 premières valeurs). L'astuce consiste à utiliser non pas la recherche linéaire dans la boucle interne mais la recherche binaire ... Ce sont ci-dessous des fonctions bien indentées et entièrement lisibles (enfin pour moi):

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 caractères, 556 octets

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

ce serait la traduction en APL de C que j'ai envoyée. Il semble que je ne comprenne pas quand utiliser ∇∇ à la place de ∇ ... possible ∇∇ est utilisé quand il y a un argument est une fonction (et pas un autre type). "u bs x, a, b" devrait être la recherche de bin dans le tableau "u" pour la valeur "x" dans la plage a..b; il retournerait 1, indexWhereFind ou 0, indexWhereEndOfsearch. Avec l'argument 200 p la fonction prend + - une minute ici ...

  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