Glückszahlen generieren

22

Geschichte:

Lucy fragte George, was seine Glückszahl sei. Nach einigem Nachdenken antwortete George, dass er mehrere Glückszahlen habe. Nach einigem Durcheinander fragte Lucy George, was seine ersten nGlückszahlen seien. George bat Sie dann, seinen Kumpel, ihm ein Programm zu schreiben, um die Arbeit für ihn zu erledigen.

Die Herausforderung:

Sie schreiben ein Programm / eine Funktion, die vom Standardeingabe- / Funktionsargument einen String oder eine Ganzzahl erhält n. Das Programm / die Funktion gibt dann die ersten n Glückszahlen aus . Glückszahlen werden über ein Sieb wie folgt definiert.

Beginnen Sie mit den positiven ganzen Zahlen:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, ...

Entferne nun jede zweite Zahl:

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, ...

Die zweite verbleibende Zahl ist 3 , also entferne jede dritte Zahl:

1, 3, 7, 9, 13, 15, 19, 21, 25, ...

Jetzt ist die nächste verbleibende Zahl 7 , also entferne jede siebte Zahl:

1, 3, 7, 9, 13, 15, 21, 25, ...

Entfernen Sie als Nächstes jede neunte Nummer und so weiter. Die Folge sind die Glückszahlen.

Gewinnen:

Wie bei Codegolf üblich, gewinnen die wenigsten Bytes.

Wie üblich werden Einsendungen mit Standardlücken disqualifiziert.

Die Nummer eins
quelle
8
Ich würde vorschlagen, die Definition in den Post sowie die ersten zehn oder so Zahlen aufzunehmen.
xnor
Eine coole Erweiterung wäre, dass für jedes untersuchte Element (3, 7 usw.) diese Operation so oft ausgeführt wird. Zum Beispiel für 3, entfernen Sie das dritte Element in der Liste 3-mal, das 7. Element 7-mal usw. (beachten Sie, dass dies nicht die Reihenfolge ist, aber die Idee ist die gleiche)
Ryan
@ Ryan Ich denke, diese Sequenz wäre bemerkenswert ähnlich zu den natürlichen Zahlen :)
TheNumberOne
@TheBestOne Du denkst schon? Ich habe früher auf math.stackexchange gepostet: math.stackexchange.com/questions/1153889/…
Ryan
@ Ryan Eigentlich habe ich deinen Vorschlag falsch interpretiert. Wie Sie in Ihrer Frage zu math.se dargelegt haben, finde ich das interessant.
TheNumberOne

Antworten:

16

Python 2, 79

n=input()
L=range(1,2**n)
for r in L:r+=r<2;map(L.remove,L[r-1::r])
print L[:n]

Die Magie, eine Liste zu durchlaufen, während die Schleife sie ändert!

Die Liste Lbeginnt mit allen ganzen Zahlen 1mit einem ausreichend hohen Wert. Der Code durchläuft jedes Element rvon L, nimmt die Unterliste jedes rElements und entfernt jeden dieser Werte. Infolgedessen werden die entfernten Werte nicht wiederholt. Am Ende drucken Sie die ersten nElemente.

Der Ausdruck map(A.remove,B)ist ein Trick, auf dessen Verwendung ich lange gewartet habe. Es ruft A.removefür jedes Element von auf B, wodurch alle Elemente von Bentfernt werden A. BTatsächlich nimmt es den Listenunterschied , obwohl es eine Unterliste von sein muss A. Es erfordert Python 2, da Python 3 die Map nicht wirklich auswerten würde.

Die erste Schleife muss ein spezielles Gehäuse haben, um rvon 1nach 2, as konvertieren zu können r+=r<2.

Die ausreichend hohe Obergrenze von 2**nmacht das Programm für große Werte von sehr langsam n. Verwenden n*n+1reicht aus, kostet aber einen Charakter. Beachten Sie, dass n*ndies nicht funktioniert n=1.

xnor
quelle
Sie brauchen nur n**2Zahlen, nicht2**n
Optimierer
3
Das ist eine erstaunliche Verwendung, die mapSie dort haben. Ich habe mich gefragt, ob es einen besseren Weg gibt ...
Sp3000
@Optimizer Leider, n**2+1sofern der Fall n=1nicht vergeben werden kann.
Donnerstag,
Diese Verwendung der Karte ist brillant. Wie bei einem bestellten Set. Vielleicht kann man auch gerne map(A.index,B)die Indizes der Elemente von B in A map(A.count,B)finden, die Anzahl der Elemente von B in A finden, map(A.extend,B)eine abgeflachte B-Liste zu A hinzufügen. Der Verstand verwirrt.
Logic Knight
13

Haskell, 71 69 Bytes

s(n:k)p=n:s[m|(i,m)<-zip[p..]k,i`mod`n>0](p+1)
f n=take n$1:s[3,5..]3

Definiert eine Funktion f. Der Ausdruck wird 1:s[3,5..]3zu einer unendlichen Liste von Glückszahlen ausgewertet und fnimmt einfach die erste nvon ihnen durch take n.

f 20
[1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,73,75,79]

Mit einem parallelen Listenverständnis konnte ich 5 Bytes aus dem Sieb entfernen

s(n:k)p=n:s[m|m<-k|i<-[p..],i`mod`n>0](p+1)

Dazu müsste jedoch das humongous-Compiler-Flag -XParallelListCompan GHC übergeben werden, damit die Erweiterung aktiviert werden kann.

Erklärung des Siebs

s(n:k)p=               -- Sieving a list with head n and tail k with accumulator p is
 n:                    -- the head n, followed by
  s[m|                 -- the result of sieving the list of numbers m
    (i,m)<-zip[p..]k,  -- where (i,m) is drawn from [(p,k_0),(p+1,k_1),(p+2,k_2),..] and
    i`mod`n>0]         -- i does not divide n,
   (p+1)               -- using p+1 as the accumulator

Die Grundidee ist, dass s(n:k)pdie (p-1)dritte Glückszahl erzeugt wird n, jede ndritte Zahl aus dem Endlosschwanz entfernt wird k(um pdie zuvor erzeugten Zahlen zu berücksichtigen) und mit dem Akkumulator auf diese Liste zurückgegriffen wird (p+1). In finitialisieren wir den Prozess mit den ungeraden Zahlen von Ausgangs 3und Klebrigkeit 1an der Vorderseite, genau die Glückszahlen zu erhalten.

Zgarb
quelle
12

Python 2, 71 69 67

Zuerst dachte ich, dass dies eine große Herausforderung für Pythons Array-Slicing sein würde. Ich bin jedoch auf einen Stolperstein gestoßen, als ich entdeckte, dass Slices mit einem anderen Schritt als 1 nur Slices mit identischer Länge zugewiesen werden können. Aber nachdem ich "Python Remove Slice" gegoogelt hatte, war mein Glaube wiederhergestellt: Ich fand eine funky delAussage, die den Trick perfekt macht.

n=input()
l=range(n*n+9)
for v in l:del l[v&~1::v or 2]
print l[:n]

Alte Version

n=input()
l=range(1,n*n+9)
for v in l:del l[v-1%v::v+1/v]
print l[:n]

-2 Bytes dank Sp3000.

Feersum
quelle
10

> <> , 121 114 111 Bytes

i2+:&:*1\
:})?v:2+>l{
nao2\r~1
)?vv>1+:&:&=?;:[{::nao}]$}l1-[01+}:l3-$%$l1-@@-{$[{~l1
3.\ ff+
!?:<]-1v
~]{43. >

Ich habe nur ein paar Worte zu sagen ...

... "Argh, mein Gehirn tut weh."


Erläuterung

> <> ist eine esoterische 2D-Programmiersprache und aufgrund des Fehlens von Arrays definitiv nicht für diese Aufgabe geeignet. Tatsächlich ist der einzige Datentyp in> <> eine seltsame Mischung aus int / float / char, und alles geschieht auf einem Stapel von Stapeln.

Hier ist der Überblick:

Line 1:            i2+:&:*1\

i2+:&              Read a char as input (n) and add 2, copying n+2 into the register
:*                 Duplicate and multiply, giving (n+2)^2 on the stack
1\                 Push 1 and go to the next line

Line 2:            >l{:})?v:2+

l{:})?v            Go to the next line if the stack's length is greater than (n+2)^2
:2+                Otherwise duplicate the top of the stack and add 2 to it

Line 3:            \r~1nao2

r~                 Reverse the stack and pop; stack contains the first (n+2)^2 odd integers
1nao               Print 1 (special case)
2\                 Push 2 (let's call this "i" for "iterations") and go to the next line

Line 4:            >1+:&:&=?;:[{::nao}]$}l1-[01+}:l3-$%$l1-@@-{$[{~l1)?vv

1+                 Increment i
:&:&=?;            If i is equal to n+2 (+2 because we started at 2), halt
:[{::nao}]$}       Print the i-th element down (the next lucky number) and also
                   copy it to the top of the stack, while moving i to the bottom
l1-[               Move everything but i to a new stack
0                  Push 0 (let's call this "r" for recursion depth)

Sieve loop:

1+                 Increment r
}:l3-$%$l1-@@-{$[  Move everything up to the last element to be sieved out to a new stack
{~                 Remove said last element
1)?vv              If the length is 1, go to line 6 (sieving complete)
                   Otherwise go to line 5, which repeats this sieve loop by teleporting

Line 6:            :?!v1-]

:?!v1-]            Keep unrolling and decrementing r until r is 0

Line 7:            >~]{43.             

~]                 Pop r and unroll once more (to the stack where i waits)
43.                Loop, performing everything from line 4 all over again

Hier ist ein Musterbeispiel, das ungefähr zeigt, wie das Sieben funktioniert (hier kist die Glückszahl, mit der wir sieben):

[[15 13 11 9 7 5 3 1 k=3 r=0]]     -- move -->
[[15 13] [11 9 7 5 3 1 k=3 r=1]]   -- pop  -->
[[15 13] [9 7 5 3 1 k=3 r=1]]      -- move -->
[[15 13] [9 7] [5 3 1 k=3 r=2]]    -- pop  -->
[[15 13] [9 7] [3 1 k=3 r=2]]      -- move -->
[[15 13] [9 7] [3 1] [k=3 r=3]]    -- pop  -->
[[15 13] [9 7] [3 1] [r=3]]        (now we unroll)
Sp3000
quelle
7
Immer noch besser als Java;)
Optimierer
5
Ich mag die Tatsache, dass naoanscheinend als "Print this thing now" interpretiert werden kann.
Zgarb,
10

CJam - 25

Lri{1$W%{1$\(1e>/+}/)+}/p

Probieren Sie es online aus

Erläuterung:

Diese Implementierung entfernt keine Zahlen nacheinander aus einem Array, sondern berechnet jede Zahl basierend darauf, wie viele zuvor entfernt worden wären.
Für jeden Index i (von 0 bis n-1) und jede vorherige Glückszahl l erhöhen wir i in umgekehrter Reihenfolge um i / (l-1), mit Ausnahme von l = 1 verwenden wir 1 anstelle von 0 und addieren auch 1 am Ende.
ZB für i = 4 haben wir die ersten 4 Zahlen [1 3 7 9] und berechnen:
4 + 4 / (9-1) = 4
4 + 4 / (7-1) = 4
4 + 4 / (3 -1) = 6
6 + 6/1 = 12
12 + 1 = 13

L              empty array - the first 0 lucky numbers :)
ri             read and convert to integer (n)
{…}/           for each number (i) from 0 to n-1
    1$         copy the previous array
    W%         reverse the order
    {…}/       for each array element (l)
        1$     copy i
        \(     swap with l and decrement l
        1e>    use 1 if l=1
        /+     divide and add to i
    )+         increment and add the new lucky number to the array
p              pretty print
aditsu
quelle
Interessante Technik :)
TheNumberOne
6

Pyth: 23 22 Bytes

<u-G%@GhH+0GQ%2r1^hQ2Q

Probieren Sie es online aus: Pyth Compiler / Executor

Erläuterung:

<u-G%@GhH+0GQ%2r1^hQ2Q    Q = input()
             %2r1^hQ2     create the list [1, 2, ..., (Q+1)^2-1][::2]
 u          Q%2r1^hQ2     G = [1, 2, ..., (Q+1)^2-1][::2]
                           modify G for each H in [0, 1, 2, ..., Q]:
  -G%:GhH+0G                  G = G - ([0] + G)[::G[H+1]]
                               (minus is remove in Pyth)
<                    Q    print the first Q elements of the resulting list

Die Reduzierung berechnet tatsächlich mehr als QGlückszahlen (der Entfernungsbefehl wird Q + 1 mal aufgerufen, Q-1 sollte ausreichen).

Jakube
quelle
5

R, 58 Bytes

n=scan();s=r=1:n^2;for(j in 1:n)r=r[-max(2,r[j])*s];r[1:n]

Mit Zeilenumbrüchen:

n=scan()              #user input
s=r=1:n^2             #declare r and s simultaneously, both large enough to sieve
for(j in 1:n)
  r=r[-max(2,r[j])*s] #iteratively remove elements by position in vector
r[1:n]                #print

Vorherige Version, 62 Bytes

function(n){
  s=r=1:n^2             #declare r and s simultaneously, both large enough to sieve
  for(j in 1:n)
    r=r[-max(2,r[j])*s] #iteratively remove elements by position in vector
  r[1:n]                #print
}

Vorherige Version, 78 Bytes

n=as.numeric(readline())   #ask for user input and convert it to numeric
r=1:n^2                    #create a large enough vector to sieve
for(j in 1:n){             #loop
  r=r[-max(2,r[j])*1:n^2]  #iteratively remove elements by position in vector
}
r[1:n]                     #print
freekvd
quelle
64 Bytes: Ändern n=as.numeric(readline()) in function(n){...}. Dadurch wird ein Funktionsobjekt erstellt, das zugewiesen und aufgerufen werden kann. Lassen Sie die geschweiften Klammern in der forSchleife fallen.
Alex A.
Vielen Dank @Alex! Obwohl das 66 ist, da es einen Namen braucht?
Freekvd
Es braucht keinen Namen für die Einreichung. Siehe die Matlab / Octave-Lösungen. R-Funktionsobjekte ähneln unbenannten / Lambda-Funktionen in anderen Sprachen, bei denen es sich um gültige Übermittlungen handelt.
Alex A.
Was ist n=scan(n=1)?
Koekenbakker
2
Das funktioniert! Und es ist 1 Zeichen weniger. Es ist sogar noch kürzer, wenn ich n = 1 fallen lasse, die Funktion ignoriert alle Elemente von n nach dem ersten.
Freekvd
4

CJam, 32 30 Bytes

3ri:N#,N{0\__I1e>)=%-+}fI(;N<p

Übernimmt die Eingabe von STDIN.

Code Erklärung :

3ri:N#,                          "Read the input in N and get first 3^N whole numbers";
       N{0\__I1e>)=%-+}fI        "Run the code block N times, storing index in I";
         0\__                    "Put 0 before the array and take 2 copies";
             I1e>)=              "Take min(2, I + 1) th index from the copy";
                   %             "Take every array[ min (2, I + 1)] element from the array";
                    -+           "Remove it from the list and prepend 0 to the list";
                         (;N<p   "Print number index 1 to N";

Probieren Sie es hier online aus

Optimierer
quelle
4

Python 2, 105 101 Bytes

n=input()
L=range(-1,n*n+9,2)
i=2
while L[i:]:L=sorted(set(L)-set(L[L[i]::L[i]]));i+=1
print L[1:n+1]

Nur eine einfache Implementierung.

Pyth, 39, 36, 35 32 Bytes

J%2r1h^Q2VJI>JhN=J-J%@JhN+2J;<JQ

Ähnlich wie oben, aber die Dinge sind 0-indiziert und nicht 1-indiziert. Probieren Sie es online aus .

Vielen Dank an @Jakube für den Hinweis auf eine Byte-Speicherung.

Sp3000
quelle
3

Mathematica, 80 Bytes

(For[l=Range[#^2];i=1,(m=l[[i++]]~Max~2)<=Length@l,l=l~Drop~{m,-1,m}];l[[;;#]])&

Einfache Umsetzung der Definition. Beginnt, wie einige andere Antworten zeigen, mit einem Bereich von 1bis und filtert dann weiter.n2

Martin Ender
quelle
3

Perl, 86 81 78

86

@a=(1..($k=<>)**2);for$n(@a){$i=1;@a=map{$i++%($n+($n<2))?$_:()}@a;$k-=$k&&print"$n "}

UPDATE: ist natürlich grep{...}besser als map{...?$_:()} 81:

@a=(1..($k=<>)**2);for$n(@a){$i=1;@a=grep{$i++%($n+($n<2))}@a;$k-=$k&&print"$n "}

UPDATE: OK, jetzt eigentlich ein Einzeiler. Ich kann aufhören. (?) 78:

@a=(1..($k=<>)**2);for$n(@a){$k-=$i=$k&&print"$n ";@a=grep{$i++%($n+=$n<2)}@a}
Vynce
quelle
3

Octave, 139 83 72

function r=l(n)r=1:2:n^2;for(i=2:n)h=r(i);r(h:h:end)=[];end;r=r(1:n);end

Ungolfed:

function r=l(n)
  r=1:2:n^2;
  for(i=2:n)
    h=r(i);
    r(h:h:end)=[];
  end
r=r(1:n);  # reduce it to only N lucky numbers
end
dcsohl
quelle
2

J 60 52 Bytes

   ({.}.@((>:@{.,]#~0<({~{.)|i.@#)@]^:[2,1+2*i.@*:@>:)) 8
1 3 7 9 13 15 21 25

Erklärung (von rechts nach links):

2,1+2*i.@*:@>:  generates the list 2 1 3 5 7 9... with (n+1)^2 odd numbers
^:[             repeats n times the following
@]                using the list
0<({~{.)|i.@#     is the remainder of the indexes of the lists elements with the first element positive (i.e. index divisible by first element)
]#~               keep those elements from the list
>:@{.,            concatenate a first element with the value of the current one +1
}.@             drop first element
{.              take the first n element

2,1+2*i.@*:@>:zu lang scheint Art und Weise , aber ich kann es nur um 1 Byte verkürzen Austausch *:mit !so dass die Liste exponentiell wachsen.

randomra
quelle
2

JavaScript (ES6) 96 99

Edit Countdown in der ersten Schleife - danke @DocMax

F=n=>(i=>{
  for(o=[1];--i;)o[i]=i-~i;
  for(;++i<n;)o=o.filter((x,j)=>++j%o[i]);
})(n*n)||o.slice(0,n)

Ungolfed

F=n=>{
  for (i = n*n, o = [1]; --i;)
    o[i] = i+i+1;
  for (; ++i < n; )
    o = o.filter((x, j) => (j+1) % o[i])
  return o.slice(0,n)
}

Test In der Firefox / FireBug-Konsole

F(57)

Ausgabe

[1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, 87, 93, 99, 105, 111, 115, 127, 129, 133, 135, 141, 151, 159, 163, 169, 171, 189, 193, 195, 201, 205, 211, 219, 223, 231, 235, 237, 241, 259, 261, 267, 273, 283, 285, 289, 297, 303]
edc65
quelle
1
Sie können 1 speichern, indem Sie mit der ersten Schleife abwärts und mit der zweiten F=n=>{for(o=[1],i=n*n;--i;)o[i]=2*i+1;for(;++i<n;o=o.filter((x,j)=>++j%o[i]));return o.slice(0,n)}
aufwärts zählen
Dein ungolfed hilft hier nicht wirklich: P;)
Optimizer
@Optimizer ungolfed aktualisiert - vielleicht hilft es immer noch nicht viel, aber zumindest funktioniert es jetzt
edc65
Ich meinte mehr in den Zeilen auf "Einfach eine Formatänderung wird nicht helfen, bitte geben Sie Kommentare :)"
Optimierer
2

Matlab, 104 Bytes

function x=f(n)
k=1;N=n;x=0;while nnz(x)<n
x=1:N;m=1;while m-nnz(x)
m=x(x>m);x(m:m:end)=[];end
N=N+2;end

Vielen Dank an @flawr für sehr zutreffende Kommentare und Vorschläge.

Beispiel an der Matlab-Eingabeaufforderung:

>> f(40)
ans =
  Columns 1 through 22
     1     3     7     9    13    15    21    25    31    33    37    43    49    51    63    67    69    73    75    79    87    93
  Columns 23 through 40
    99   105   111   115   127   129   133   135   141   151   159   163   169   171   189   193   195   201
Luis Mendo
quelle
Vielen Dank! Ich habe das in der Vergangenheit benutzt, vergesse aber
Luis Mendo
@flawr Guter Punkt. Diese Antwort wird mehr deine als meine! :-)
Luis Mendo
Sicher! Ich bin öfter in StackOverflow, aber es ist der gleiche Geist dort. Ich schätze es!
Luis Mendo
Guter Punkt! Ich bin mir nicht sicher, ob all das, was ich lerne, für meine normale Matlab-Nutzung hilfreich oder sogar schädlich sein wird :-P
Luis Mendo
2
Nun, bei Codegolf geht es nicht um den Gebrauch, sondern um den Missbrauch einer Sprache ^^
flawr
1

Bash + Coreutils, 136

Ich hatte gehofft, noch mehr Golf spielen zu können, aber na ja. Nicht an jedem Tag, an dem Sie eine rekursive Funktion in einem Shell-Skript aufrufen:

f(){
mapfile -tn$2 a
(($1>$2))&&{
tr \  \\n<<<${a[@]}
sed $[${a[-1]}-$2]~${a[-1]}d
}|f $1 $[$2+1]||echo ${a[@]}
}
yes|sed -n 1~2=|f $1 2

Ausgabe:

$ ./lucky.sh 23
1 3 7 9 13 15 21 25 31 33 37 43 49 51 63 67 69 73 75 79 87 93 99
$ 

Bash + Coreutils, 104

Kürzere Verwendung einer einfacheren Implementierung:

a=(`seq 1 2 $[3+$1**2]`)
for((;i++<$1;));{
a=($(tr \  \\n<<<${a[@]}|sed 0~${a[i]}d))
}
echo ${a[@]:0:$1}
Digitales Trauma
quelle
1

Los, 326

package main
import"fmt"
func s(k, p int,in chan int)chan int{
    o := make(chan int)
    go func(){
        for p>0{
            o<-<-in;p--
        }
        for{
            <-in
            for i:=1;i<k;i++{o<-<-in}
        }
    }()
    return o
}
func main(){
    n := 20
    fmt.Print(1)
    c := make(chan int)
    go func(c chan int){
        for i:=3;;i+=2{c<-i}
    }(c)
    for i:=1;i<n;i++{
        v := <-c
        fmt.Print(" ", v)
        c = s(v, v-i-2, c)
    }
}

Einfache Implementierung mit Goroutine und Rohren zur Herstellung von Sieben.

David
quelle
7
Dieser Code Golf, fügen Sie bitte eine Byteanzahl hinzu.
Edc65
1

MATLAB, 62 Zeichen

n=input('');o=1:2:n^2;for i=2:n;o(o(i):o(i):end)=[];end;o(1:n)

Ich habe die Herausforderung zunächst falsch interpretiert - meine überarbeitete Version ist jetzt tatsächlich kürzer.

Sanchises
quelle
0

Schläger 196 Bytes

Erzeugt Glückszahlen bis n:

(λ(n)(let loop((l(filter odd?(range 1 n)))(i 1))(define x(list-ref l i))(set! l(for/list((j(length l))
#:unless(= 0(modulo(add1 j)x)))(list-ref l j)))(if(>= i(sub1(length l)))l(loop l(add1 i)))))

Ungolfed-Version:

(define f
 (λ(n)
    (let loop ((l (filter odd? (range 1 n))) (i 1))
      (define x (list-ref l i))
      (set! l (for/list ((j (length l)) #:unless (= 0 (modulo (add1 j) x)))
                (list-ref l j)))
      (if (>= i (sub1 (length l)))
          l
          (loop l (add1 i)))))
  )

Testen:

(f 100)

Ausgabe:

'(1 3 7 9 13 15 21 25 31 33 37 43 49 51 63 67 69 73 75 79 87 93 99)
rnso
quelle