Fabuła:

Lucy zapytała George'a, jaki jest jego szczęśliwy numer. Po krótkiej kontemplacji George odpowiedział, że ma kilka szczęśliwych liczb. Po krótkim zamieszaniu Lucy zapytała George'a, jakie są jego pierwsze nSzczęśliwe Liczby. George poprosił cię, jego kumpel, o napisanie mu programu do wykonania pracy za niego.

Wyzwanie:

Napisz program / funkcję, która otrzyma od standardowego argumentu wejścia / funkcji ciąg lub liczbę całkowitą n. Program / funkcja zwróci / wyśle ​​pierwsze n szczęśliwe liczby . Szczęśliwe liczby są definiowane przez sito w następujący sposób.

Zacznij od dodatnich liczb całkowitych:

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

Teraz usuwaj co drugi numer:

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

Drugi pozostały numer to 3 , więc usuwaj co trzeci numer:

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

Kolejny pozostały numer to 7 , więc usuwaj co siódmy numer:

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

Następnie usuń co dziewiąty numer i tak dalej. Wynikowa sekwencja to szczęśliwe liczby.

Zwycięski:

Jak zwykle dla codegolf, wygrywa najmniej bajtów.

Jak zwykle zgłoszenia korzystające ze standardowych luk są dyskwalifikowane.

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]

Magia iteracji po liście, gdy pętla ją modyfikuje!

Lista Lzaczyna się od wszystkich liczb całkowitych 1do wystarczająco wysokiej wartości. Kod iteracje nad każdym elementem rz L, biorąc podmenu każdym r-tym elemencie, i usunięcie każdej z tych wartości. W rezultacie usunięte wartości nie są powtarzane. Na koniec wydrukuj pierwsze nelementy.

Wyrażenie map(A.remove,B)to sztuczka, na którą czekałem od dawna. Wzywa A.removekażdy element B, co powoduje usunięcie wszystkich elementów Bz A. W rzeczywistości bierze różnicę listy, choć wymaga Bpodlisty A. Wymaga Python 2, ponieważ Python 3 tak naprawdę nie ocenia mapy.

Pierwsza pętla musi być w specjalnej obudowie, aby przekonwertować rz 1na 2, as r+=r<2.

Wystarczająco wysoka górna granica 2**npowoduje, że program działa bardzo wolno dla dużych wartości n. Używanie n*n+1wystarcza, ale kosztuje postać. Pamiętaj, że n*nto nie działa n=1.

Haskell, 71 69 bajtów

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

Definiuje funkcję f. Wyrażenie 1:s[3,5..]3ocenia na nieskończoną listę szczęśliwych liczb i fpo prostu bierze pierwszą nz nich take n.

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

Mógłbym ogolić 5 bajtów z sita przy użyciu równoległego rozumienia listy

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

ale wymagałoby to przekazania -XParallelListCompdo GHC flagi ogromnego kompilatora, aby umożliwić rozszerzenie.

Objaśnienie sita

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

Podstawowa idea polega na tym, że s(n:k)pprodukuje tę (p-1)szczęśliwą liczbę n, upuszcza każdą tę nliczbę z nieskończonego ogona k(przesunięty o, paby uwzględnić liczby wyprodukowane wcześniej) i powraca do tej listy z akumulatorem (p+1). W f, inicjalizujemy proces liczbami nieparzystymi zaczynającymi się od 3i halsując 1do przodu, uzyskując dokładnie szczęśliwe liczby.

Python 2, 71 69 67

Na początku myślałem, że będzie to duże wyzwanie dla krojenia tablic Pythona. Jednak natknąłem się na przeszkodę, gdy odkryłem, że plasterkom z krokiem innym niż 1 można przypisać tylko kolejny plaster o identycznej długości. Ale po googlowaniu „python remove slice”, moja wiara została przywrócona: znalazłem funky del, która doskonale sobie z tym radzi.

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

Stara wersja

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

-2 bajty dzięki Sp3000.

> <> , 121 114 111 bajtów

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

Mam tylko kilka słów do powiedzenia ...

... „Ach mój mózg boli.”

Wyjaśnienie

> <> to ezoteryczny język programowania 2D i zdecydowanie nie nadaje się do tego zadania z powodu braku tablic. W rzeczywistości jedynym typem danych w> <> jest dziwna mieszanka int / float / char i wszystko dzieje się na stosie.

Oto podsumowanie:

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

Oto próbny przykład, który pokazuje z grubsza, jak działa przesiewanie (oto kszczęśliwa liczba, z którą przesiewamy):

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

CJam - 25

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

Wypróbuj online

Wyjaśnienie:

Ta implementacja nie usuwa liczb kolejno z tablicy, ale oblicza każdą liczbę na podstawie liczby, które zostałyby usunięte przed nią.
Dla każdego indeksu i (od 0 do n-1) i każdej poprzedniej szczęśliwej liczby l, w odwrotnej kolejności, zwiększamy i o i / (l-1), z wyjątkiem l = 1 używamy 1 zamiast 0, a także dodajemy 1 na końcu.
Np. Dla i = 4 mamy pierwsze 4 liczby [1 3 7 9] i obliczamy:
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

Pyth: 23 22 bajtów

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

Wypróbuj online: Pyth Compiler / Executor

Wyjaśnienie:

<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

Redukcja faktycznie oblicza więcej niż Qszczęśliwe liczby (polecenie usuwania nazywa się Q + 1 razy, Q-1 powinno wystarczyć).

R, 58 bajtów

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

Z podziałami linii:

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

Poprzednia wersja, 62 bajty

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
}

Poprzednia wersja, 78 bajtów

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

CJam, 32 30 bajtów

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

Pobiera dane wejściowe ze STDIN.

Objaśnienie kodu :

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

Wypróbuj online tutaj

Python 2, 105 101 bajtów

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]

Po prostu prosta implementacja.

Pyth, 39 36 35 32 bajtów

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

Podobne do powyższego podejścia, ale rzeczy są indeksowane 0, a nie indeksowane 1. Wypróbuj online .

Dzięki @Jakube za wskazanie oszczędności bajtów.

Mathematica, 80 bajtów

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

Proste wdrożenie definicji. Podobnie jak inne odpowiedzi, zaczyna się od zakresu od 1do, a następnie filtruje.n2

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

AKTUALIZACJA: oczywiście grep{...}jest lepsza niż map{...?$_:()} 81:

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

AKTUALIZACJA: OK, teraz jest to jedna linia. Mogę przestać. (?) 78:

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

Oktawa, 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

Nie golfowany:

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

J, 60 52 bajtów

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

Objaśnienie (od prawej do lewej):

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.@*:@>:wydaje się o wiele za długi, ale mogę go skrócić tylko o 1 bajt zamiany, *:dzięki !czemu lista rośnie wykładniczo.

JavaScript (ES6) 96 99

Edytuj Odliczanie w pierwszej pętli - dzięki @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)

Nie golfił

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

Przetestuj w konsoli Firefox / FireBug

F(57)

Wydajność

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

Matlab, 104 bajty

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

Dzięki @flawr za bardzo odpowiednie komentarze i sugestie.

Przykład z wiersza polecenia Matlab:

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

Bash + coreutils, 136

Miałem nadzieję pograć w golfa bardziej, ale no cóż. Nie codziennie, gdy włączasz potok do funkcji rekurencyjnej w skrypcie powłoki:

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

Wydajność:

$ ./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

Krótszy przy użyciu prostszej implementacji:

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

Idź, 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)
    }
}

Proste wdrożenie za pomocą goroutine i rur do robienia sit.

MATLAB, 62 znaki

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

Na początku źle zinterpretowałem wyzwanie - moja poprawiona wersja jest teraz krótsza.

Rakieta 196 bajtów

Produkuje szczęśliwe liczby do 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)))))

Wersja bez golfa:

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

Testowanie:

(f 100)

Wydajność:

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