Ulam-Nummern generieren

19

Schreiben Sie mit einer Ganzzahl n(wo n < 10001) als Eingabe ein Programm, das die ersten n Ulam-Zahlen ausgibt . Eine Ulam-Nummer ist wie folgt definiert:

  1. U 1 = 1, U 2 = 2.
  2. Denn n > 2U n ist die kleinste ganze Zahl, die größer ist als U n-1 , dh die Summe zweier unterschiedlicher früherer Terme auf genau eine Weise.

Zum Beispiel U 3 ist , 3(2 + 1), U 4 ist 4(3 + 1) ( Man beachte , daß (2 + 2) gilt nicht als die Begriffe nicht unterscheidbar sind) und U 5 ist 6, (U 5 ist nicht mehr als 5 weil 5 entweder als 2 + 3 oder 4 + 1 dargestellt werden kann). Hier sind die ersten Ulam-Nummern:

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

Dies ist Codegolf, also gewinnt der kürzeste Eintrag.

Absinth
quelle
Muss die Ausgabe wie gezeigt sein (Liste durch Komma und Leerzeichen getrennt) oder können wir zB ein Array ausgeben?
Dennis
Was ist der Mindestwert, den nwir bewältigen müssen?
Dennis
1
@ Tennis Space oder Komma oder beides ist in Ordnung. Der Mindestwert von n ist 1.
Absinth
So wie es ist, habe ich Klammern um meine Liste. Ist das auch in Ordnung oder soll ich sie entfernen?
Dennis
1
@ Tennis Brackets sind in Ordnung.
Absinth

Antworten:

10

CJam, 47 41 37 Bytes

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

Probieren Sie es online aus.

Beispiellauf

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

Wie es funktioniert

Diese Grundidee ist die folgende:

  1. Beginnen Sie mit dem Array A := [ 0 U₁ U₂ ... Uₖ ].

  2. Berechnen Sie Sdas Array aller Summen x + yso, dass x,y ∊ Aund x < y.

  3. Verwerfen Sie alle nicht eindeutigen Beträge von S. Da jede Ulam-Zahl größer als 2 sowohl die Summe zweier kleinerer Einsen als auch die Summe von Null und sich selbst ist, werden die Ulam-Zahlen verworfen U₃, U₄, ... Uₖ.

  4. Das verbleibende Array ist [ U₁ U₂ Uₖ₊₁ ... ], also ist die nächste Ulam-Nummer das drittkleinste Element. Hänge es an Aund gehe zurück zu Schritt 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.                ";
Dennis
quelle
Eine Eingabe von 100dauert bereits einige Sekunden. Ich nehme an, die Berechnung der maximalen Eingabe 1e5 würde ewig dauern.
Martin Ender
@ MartinBüttner: Der Java-Interpreter ist viel schneller, aber immer noch langsam. Alle Brute-Force-Algorithmen sind O (n²) oder schlechter. Die Verwendung einer stapelorientierten Sprache für Arrays ist nie schön (zum Beispiel erfordert das Berechnen einer Arraylänge das Kopieren des gesamten Arrays), sodass die tatsächliche Ausführungszeit wahrscheinlich 0 (n³) beträgt.
Dennis
1
@ MartinBüttner: WolframAlpha , also 1e4 (zum Glück nicht 1e5) sollte weniger als drei Wochen dauern.
Dennis
6

J - 46 Zeichen

Funktion nals Argument nehmen.

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

Erklärt durch 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
algorithmshark
quelle
Es gibt +_*...
Tomsmeding
6

T-SQL, 301 300 288 287

Ich habe einen leichten SQL-Missbrauch begangen.

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

Probieren Sie es hier in SQL Server 2008 aus .

@N enthält die ganze Zahl der Eingabe. Ändern Sie das Beispiel "100" in das, was n sein soll. "10000" wird wahrscheinlich irgendwann fertig sein, aber ich habe das nicht zu Ende laufen lassen. Die Zeichenanzahl dieses Eintrags gilt für eine einstellige Eingabe. Die Ausgabe erfolgt in Abfrageergebnisform.

Muqo
quelle
5

Haskell, 70 67 Zeichen

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

Verwendung:

>u 6
[1,2,3,4,6,8]
stolzer haskeller
quelle
5

GolfScript ( 41 37 Bytes)

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

Online-Demo

Die kartesischen Produkte in GolfScript sind ziemlich lang, daher wird ein anderer Ansatz gewählt. Das langfristige Wachstum der Ulam-Zahlen ist, dass die nth Ulam-Zahl ungefähr ist 13.5n, aber in den ersten 10000 Begriffen das größte Verhältnis zwischen der nth Ulam-Zahl und nist knapp 13.3. Daher nkönnen wir die ersten 14nZahlen filtern , um diejenigen zu finden, die in die Sequenz gehören.

Vielen Dank an Dennis für 41-> 37.

Peter Taylor
quelle
1
Das geht ganz schnell. n = 1000dauert mit GolfScript weniger als eine Minute; Ein Port zu CJam ist n = 1000in 8 Sekunden und n = 10000in 1 Stunde 20 Minuten fertig . - Sie können vier Bytes einsparen, indem Sie Ihren Ansatz mit meinem kombinieren, nämlich 0 in das Array aufnehmen und es anschließend verwerfen. Dies ermöglicht die Verwendung von set union anstelle des Blocks und macht eine Variable ~.14*,4,\{1$.{2$1$-.@<*}%&,2=*|}/1><`
Dennis
@ Tennis, wie viele Zeichen kürzer ist der CJam? Ich gehe davon aus, dass keine der Operationen länger wird, und ich bin mir ziemlich sicher, dass es einen Ein-Zeichen-Alias ​​für hat 14.
Peter Taylor
Ja 14ist gerade E. Sie müssen jedoch aus STDIN lesen, die Ganzzahl in einen Singleton konvertieren, bevor Sie die Mengenvereinigung ausführen (ich werde einen Fehlerbericht darüber einreichen) und 2$werden in der inneren Schleife nicht funktionieren, da CJam den Stapel nach jeder Iteration ändert ... I Habe verschiedene Tricks ausprobiert, aber der kürzeste war genau 37 Bytes:li4,1$E*{__{I1$-_@<*}%&,2=I*a|}fI1><`
Dennis
5

JavaScript ES6, 100 ... 93 90 Zeichen

Führen Sie dies in der Webkonsole oder im Scratchpad des neuesten Firefox (Nightly oder Release) aus.

EDIT 8 Golf viel !!! und machte es auf 94 Zeichen 93 90 Zeichen (dank @openorclose). (Meine erste Unter 100)

Hier ist meine Version, die viel schneller ist, aber 3 Zeichen länger (107 Zeichen) und genau so viele Zeichen enthält wie oben und viel kleiner als die unten angegebene Brute-Force-Methode !, (dank 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

Ich werde weiterhin versuchen, weiter Golf zu spielen. Aber wir quetschen es aus dem Rahmen von JS: P

Hier sind einige Zahlen, wenn ich dies in einem Skript-Tag auf einer Webseite ausführe:

n Zeit (en)
10 0,001
100 0,005
1000 2,021
10000 236.983
100000       pending tldr; Zu lange lief nicht: P

Dies ist meine erste Einreichung, die stark von der Antwort von @ rink.attendant.6 in JavaScript inspiriert ist.

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

Ich weiß, das kann noch weiter golfen werden. Ich werde auch eine nicht brachiale Lösung posten, die möglicherweise noch kürzer ist.

EDIT 1 : Golf ein bisschen mehr und für n = 1 behoben

Ich muss sagen, ich beneide Haskell und J um solch super nützliche Verknüpfungen für jede Art von Anforderung -_-

Optimierer
quelle
Bei Haskell machen
meiner
1
Die schnellere kann man sicherlich mehr Golf spielen: (104) u=n=>{for(s=[,1,1],r=[i=1,l=2];c=l<n;!c?s[r[l++]=i]=1:0,i++)for(j of r)c-=j<i/2&s[i-j];return n>1?r:[1]}und vielleicht noch mehr
edc65
1
1. Ich verstehe immer noch kaum, wie du die Doppelschleife umgangen hast.Kudos 2.Golf-Tipp: Bei E6 versuche ich immer, das zu vermeiden return. 100:u=n=>(s=>{for(r=[i=1,l=2];c=l<n;i+=!c?s[r[l++]=i]=1:1)for(j of r)c-=j<i/2&s[i-j]})([,1,1])|n>1?r:[1]
edc65
1
Es gibt ein u=n=>(s=>{for(r=[i=l=1];c=l<n;i+=c&&i-2?1:s[r[l++]=i]=1)for(j of r)c-=j<i/2&s[i-j]})([,1])||r
Zeichen
1
90 Zeichen: 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 Sofern das [, 1] nicht irgendwo benötigt wird
öffnen oder schließen Sie den
5

Perl - 71 Bytes

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

Probieren Sie es online!

Zähle den Shebang als einen.
Die Verwendung eines zweiten Arrays zum Speichern der Summen scheint bedeutend schneller zu sein als ein Hash. Die Speichernutzung ist auch geringer, was ich nicht erwartet hätte.

Beispielnutzung:

$ echo 30 | perl ulam.pl

Beispielausgabe:

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

Ungefähre Laufzeiten:

n = 100     0.015s
n = 1000    0.062s
n = 10000   4.828s
primo
quelle
2
8,6 s für n == 1e4. Tolle! Die Ausgabe für n == 1ist jedoch falsch. es sollte eine einzelne Zahl drucken.
Dennis
@ Tennis jetzt behoben.
Primo
4

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 funktioniert gut dafür.

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);
    }
}
Ypnypn
quelle
1. Für das Drucken des Ergebnisses ist anscheinend Java 8 erforderlich, was erwähnenswert sein könnte. 2. Die Ausgabe für 1sollte eine einzelne Zahl sein.
Dennis
1
Behandelt dies eine Eingabe von 10k?
Martin Ender
Ich glaube, die j und k for-Schleifen brauchen keine geschweiften Klammern.
Michael Easter
Wie Martin andeutet, würde ich mir auch eine zeitgesteuerte Ausführung dieses Programms für N = 10K wünschen.
Michael Ostern
4

APL (Dyalog ausgefahren) , 36 35 Bytes

-1 Byte von Adám

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

Probieren Sie es 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.

Wenn wir die Additionstabelle erstellen, sind diagonale Elemente doppelt so groß wie die Einträge in ⍵. Nichtdiagonale Elemente sind jeweils Summen verschiedener Elementex zweimal für jeden Weg auftreten xkann als Summe verschiedener Elemente geschrieben werden. Daher jede Nummerx tritt ein 2a+b times, where a is the number of ways x can be written as a sum of distinct elements from ⍵, and b is 1 iff x is twice some entry in ⍵. We want a=1Es reicht also aus, dies zu überprüfen 2a+b{2,3}.

* (In ngn / APL kann eine Konstante einen Zug ohne Verwendung beenden. In ngn / APL ist jedoch kein Count-In vorhanden, daher benötigen wir so irgendwo.)

Lirtosiast
quelle
{(2 3∊⍨⍵⍧⍵)/⍵}(∊⊢⊆⍨⍧⍨∊2 3⍨)
Adám
3

PHP 5.4+, 164

Gleicher Ansatz wie meine Antworten:

<?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);}
rink.attendant.6
quelle
3

Gelee , 20 Bytes

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

Probieren Sie es 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.
Lirtosiast
quelle
2

CoffeeScript, 119 114

In letzter Zeit habe ich CoffeeScript geübt, um das Golfspiel mit JavaScript zu verbessern. Deshalb ist hier meine in CoffeeScript kompilierte JavaScript-Antwort:

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]

Ich verstehe die Loops und das Verständnis in CoffeeScript nicht sehr gut, so dass ich vielleicht weiter Golf spielen kann, aber es ist das, was ich jetzt habe. Zeilenumbrüche werden als ein Zeichen gezählt (Unix-Stil).

rink.attendant.6
quelle
2

JavaScript, 147 154 150 (136)

Stark inspiriert von der Brute-Force-Java-Lösung von @ Ypnypn:

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

Vielen Dank für @Dennis, dass Sie 4 bis 18 Bytes von meiner ursprünglichen Version entfernt haben

Gefährliche Version (mit for..in Schleifen)

Ich würde es nicht empfehlen, dies auszuführen, da das Durchlaufen eines Objekts, das eine Schleife verwendet, dazu führen kann, dass Ihr Computer in Flammen aufgeht und / oder sich in einen wütenden Mörder verwandelt. Aber hier ist es: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)}

Ungolfed

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);
}
rink.attendant.6
quelle
Die Ausgabe für 1 sollte ein Singleton sein.
Dennis
@ Tennis Danke, korrigiert.
rink.attendant.6
1. Wenn Sie sich z=0innerhalb der Schleife bewegen , brauchen Sie sie nur einmal. 2. for(j in l)for(k in l)z+=l[j]<l[k]&l[j]+l[k]==i;ist viel kürzer als der l.forEachAnsatz.
Dennis
2

Mathematica, 107 91 Bytes

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

Es ist eine sehr direkte Implementierung der Spezifikation.

  • Finde alle Paare.
  • Löschen Sie alle Duplikate.
  • Löschen Sie alle Nummern, die kleiner als die letzte Ulam-Nummer sind.
  • Hängen Sie das Minimum an die Liste an.

Ich wende auch Dennis 'Trick an, Summen mit einzubeziehen 0, aber der Haken ist, dass dies das dritte Element der Liste macht, 0bevor ich wie erwartet fortfahre, also muss ich dieses Element aus der Liste entfernen.

Es verarbeitet eine Eingabe von 1000in ein paar Sekunden, aber ich bezweifle, dass Sie in angemessener Zeit ein Ergebnis für 10k erhalten werden. Aber ich denke auch, dass keiner der anderen darin gute Leistungen erbringt.

Martin Ender
quelle
2

OCaml - 254 Zeichen

Der Code verwendet eine Hash-Tabelle, um die Summe der aktuellen Elemente der Liste zu speichern und sie jedes Mal zu aktualisieren, wenn ein neues Element berechnet wird.

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]

Verwendung:

Im OCaml-Interpreter:

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

Ungolfed

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]
Virgile
quelle
2

Python, 137 128 126 Zeichen.

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

Dies ist mein erstes Golfspiel, und ich habe es von ~ 250 Zeichen reduziert. Ich bin ziemlich glücklich, würde aber gerne Vorschläge zur Verbesserung machen!

QuadmasterXLII
quelle
Klein, aber lohnenswert: Kombinieren Sie die Linien 5 & 6 bis for b in U:t[a+b]+=a!=bund die Linien 8 & 9 biswhile t[i]-2:i+=1
James Waldby - jwpat7
Danke für den Vorschlag! Ich habe auch die while-Schleife in einen Index geändert, aber nicht so viele Zeichen gespeichert, wie ich erwartet hatte.
QuadmasterXLII
2 weitere Zeichen: Init U nach [1] und Zeile 7 nachfor
James Waldby - jwpat7
Sie können immer noch 2 Zeichen entfernen, indem Sie U,i=[1,2],2auf U,i=[1],2und input()-2nach input()-1und t=_*3*inach wechseln und am Ende von fort=_*3*i;U+=[i];U+=[i]
James Waldby - jwpat7
0

C #, 257

Brute-Force-Ansatz unter Verwendung von 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));}}

Ungolfed, mit Testgeschirr

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();
    }
}
Richard II
quelle
Sehr langsam: 46 s für n = 500, 6 m für n = 1000, 50 m für n = 2000. Bei dieser exponentiellen Rate wird die Verarbeitung von n = 10K meines Erachtens 5 oder 6 Tage dauern.
Richard II
0

Pyth, 27 25 Bytes

<uaGh-sfq1lT.gksM.cG2GQS2

Probieren Sie es hier online aus .

<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

Bearbeiten: 2 Bytes durch Summieren vor dem Gruppieren golfen. Vorherige Version:<uaGh-mssdfq1lT.gsk.cG2GQS2

Sok
quelle
0

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

In Tio würde es nun in 9 Sekunden 10000 Werte finden (und dort die ersten 100 Werte ausgeben). Der Trick ist, nicht die lineare Suche in der inneren Schleife zu verwenden, sondern die binäre Suche ... Die folgenden Funktionen sind gut eingerückt und vollständig lesbar (endlich für mich):

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;
}
RosLuP
quelle
Sehen Sie, ob ich etwas reduzieren kann ...
RosLuP
Etwas sagen Sie mir, dass in der Programmierung Golf ist in
Ordnung,
1
328 Bytes
Ceilingcat
@ceilingcat "z = k" ist für mich falsch, weil mir die binäre Suche (bs () - Funktion oder Ihre B () - Funktion) als Argumentbereiche erscheinen soll (ich weiß nicht, ob es auch richtig ist ...) Die Funktion, die die Bin-Suche
aufruft
0

APL (NARS), 278 Zeichen, 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
∇

Es wäre die Übersetzung in APL von C, die ich gesendet habe. Es scheint, ich verstehe nicht, wann ich ∇∇ anstelle von ∇ verwenden soll ... möglich ∇∇ wird verwendet, wenn es ein Argument gibt, bei dem es sich um eine Funktion handelt (und nicht um einen anderen Typ). "u bs x, a, b" sollte die Bin-Suche im "u" -Array nach dem Wert "x" im Bereich a..b sein; es würde 1, indexWhereFind oder 0, indexWhereEndOfsearch zurückgeben. Mit Argument 200 p Funktion + - hier eine Minute ...

  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 
RosLuP
quelle
1
∇∇in einem dop bezieht sich auf den Operator selbst, während sich auf die abgeleitete Funktion bezieht, die aus dem Operator mit seinen Operanden besteht. In einem monadischen Operator ist es also dasselbe wie (⍺⍺∇∇)in einem dyadischen Operator (⍺⍺∇∇⍵⍵).
Adám