Dado un entero n(donde n < 10001) como entrada, escriba un programa que genere los primeros n números Ulam . Un número de Ulam se define de la siguiente manera:

1. U ₁ = 1, U ₂ = 2.
2. Porque n > 2, U _n es el número entero más pequeño que es mayor que U _n-1, que es la suma de dos términos anteriores distintos exactamente de una manera.

Por ejemplo, U ₃ es 3(2 + 1), U ₄ es 4(3 + 1) (tenga en cuenta que (2 + 2) no cuenta ya que los términos no son distintos), y U ₅ es 6, (U ₅ no es 5 porque 5 puede representarse como 2 + 3 o 4 + 1). Aquí están los primeros números de 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

Este es el código de golf, por lo que gana la entrada más corta.

CJam, 47 41 37 bytes

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

Pruébalo en línea.

Ejecución de ejemplo

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

Cómo funciona

Esta idea básica es la siguiente:

1. Comience con la matriz A := [ 0 U₁ U₂ ... Uₖ ].

2. Calcule S, la matriz de todas las sumas x + ytales que x,y ∊ Ay x < y.

3. Descarta todas las sumas no únicas de S. Dado que cada número de Ulam mayor que 2 es la suma de dos números más pequeños y la suma de cero y de sí mismo, esto descarta los números de Ulam U₃, U₄, ... Uₖ.

4. El conjunto restante es [ U₁ U₂ Uₖ₊₁ ... ], por lo que el siguiente número de Ulam es el tercer elemento más pequeño. Añádelo Ay vuelve al paso 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

Función tomando ncomo argumento.

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

Explicado por explosión:

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

He cometido un pequeño abuso de SQL ligero.

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

Pruébelo en SQL Server 2008 aquí .

@N contiene el entero de entrada. Cambie el ejemplo "100" a lo que debería ser n. "10000" probablemente terminará eventualmente, pero no he dejado que eso se complete. El recuento de caracteres de esta entrada es para una entrada de un dígito. La salida está en forma de resultado de consulta.

Haskell 70 67 caracteres

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

uso:

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

GolfScript ( 41 37 bytes)

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

Demostración en línea

Los productos cartesianos en GolfScript son bastante largos, por lo que esto toma un enfoque diferente. El crecimiento a largo plazo de los números de Ulam es que el nnúmero de Ulam es aproximadamente 13.5n, pero en los primeros 10000 términos, la mayor proporción entre el nnúmero de Ulam y nestá justo por debajo 13.3. Entonces dado nque podemos filtrar el primero14n números para encontrar los que pertenecen a la secuencia.

Gracias a Dennis por 41-> 37.

JavaScript ES6, 100 ... 93 90 caracteres

Ejecuta esto en la consola web o en el bloc de notas de la última versión de Firefox (nocturno o de lanzamiento)

EDIT 8 Golfed mucho! y lo redujo a 94 caracteres 93 90 caracteres (gracias a @openorclose). (Mi primer sub 100)

¡Aquí está mi versión, que es mucho más rápida pero tiene 3 caracteres más (107 caracteres) y es exactamente la misma cantidad de caracteres que el anterior y es mucho más pequeña que el método de fuerza bruta a continuación! (Gracias a 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

Seguiré intentando seguir jugando al golf. Pero lo estamos exprimiendo fuera del alcance de JS: P

Aquí hay algunos números cuando ejecuto esto dentro de una etiqueta de script en una página web:

n tiempo (s)
10 0,001
100 0,005
1000 2.021
10000 236.983
100000       pendientes tldr; Demasiado tiempo no se ejecutó: P

Esta es mi primera presentación, que está muy inspirada en la respuesta 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]}

Sé que esto se puede jugar aún más. También publicaré una solución sin fuerza bruta, que podría ser aún más corta.

EDITAR 1 : Golfed un poco más y arreglado para n = 1

Debo decir que envidio a Haskell y J por esos atajos súper prácticos para cada tipo de requisito -_-

Perl - 71 bytes

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

Pruébalo en línea!

Contando el shebang como uno.
El uso de una segunda matriz para almacenar las sumas parece ser significativamente más rápido que un hash. El uso de memoria también es menor, lo que no hubiera esperado.

Uso de la muestra:

$ echo 30 | perl ulam.pl

Salida de muestra:

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

Tiempos de ejecución aproximados:

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 fuerza bruta funciona bien para esto.

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 bytes

-1 byte por Adám

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

Pruébalo en línea!

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

* (En ngn / APL, una constante puede terminar un tren sin usar ⍨. Pero ngn / APL no tiene conteo, por lo que necesitamos ⍨ en alguna parte).

PHP 5.4+, 164

El mismo enfoque que mis respuestas:

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

Jalea , 20 bytes

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

Pruébalo en línea!

Œ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

Últimamente he estado practicando CoffeeScript para mejorar el golf en JavaScript, así que aquí está mi respuesta de JavaScript compilada en 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]

No entiendo muy bien los bucles y las comprensiones en CoffeeScript, por lo que tal vez esto pueda desarrollarse más, pero es lo que tengo por ahora. Las líneas nuevas se cuentan como un carácter (estilo Unix).

JavaScript, 147 154 150 150 (136)

Muy inspirado por la solución Java de fuerza bruta de @ Ypnypn publicada anteriormente:

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

Gracias por @Dennis por eliminar 4 a 18 bytes de mi versión original

Versión peligrosa (usando for..in bucles)

No recomendaría ejecutar esto porque recorrer un objeto que está usando un bucle podría hacer que su máquina estalle en llamas y / o se transforme en una máquina de matar enojada, pero aquí está: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)}

Sin 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 bytes

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

Es una implementación muy directa de la especificación.

• Encuentra todos los pares.
• Eliminar todos los duplicados.
• Eliminar todos los números menores que el último número de Ulam.
• Agregue el mínimo a la lista.

También estoy aplicando el truco de Dennis de incluir sumas 0, pero el problema es que esto hace que el tercer elemento de la lista se 0reanude como cabría esperar, por lo que necesito eliminar ese elemento de la lista.

Maneja una entrada de 1000unos pocos segundos, pero dudo que obtenga un resultado de 10k en un tiempo razonable. Pero tampoco creo que ninguno de los otros funcione bien en eso.

OCaml - 254 caracteres

El código utiliza una tabla hash para almacenar la suma de los elementos actuales de la lista y actualizarla cada vez que se calcula un nuevo elemento.

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]

Uso:

Dentro del intérprete de 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]

Sin 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 caracteres.

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

Este es mi primer golf, y lo he reducido de ~ 250 caracteres, estoy muy contento, ¡pero me encantaría recibir sugerencias sobre cómo mejorar!

C #, 257

Enfoque de fuerza bruta, usando 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));}}

Sin golf, con arnés de prueba

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 bytes

<uaGh-sfq1lT.gksM.cG2GQS2

Pruébelo en línea aquí .

<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

Editar: golfed 2 bytes realizando la suma antes de agrupar. Versión previa:<uaGh-mssdfq1lT.gsk.cG2GQS2

C, 478 bytes

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

En Tio, ahora en 9 segundos, encontraría 10000 valores (y allí imprimiría los primeros 100 valores). El truco consiste en utilizar la búsqueda no lineal en el bucle interno, sino la búsqueda binaria ... Estas siguientes son funciones bien sangradas y completamente legibles (por fin para mí):

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 caracteres, 556 bytes

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

sería la traducción en APL de C uno que envié. Parece que no entiendo cuándo usar ∇∇ en lugar de ∇ ... posible ∇∇ se usa cuando hay un argumento es una función (y no otro tipo). "u bs x, a, b" debe ser la búsqueda de bin en la matriz "u" para el valor "x" en el rango a..b; devolvería 1, indexWhereFind o 0, indexWhereEndOfsearch. Con el argumento 200 p, la función toma + - un minuto aquí ...

  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