Generuj szczęśliwe liczby

22

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.

Numer jeden
źródło
8
Proponuję zawrzeć definicję w poście, a także pierwsze dziesięć liczb.
xnor
Fajnym rozszerzeniem byłoby to, że dla każdego badanego elementu (3, 7 itd.) Wykona tę operację tyle razy. Na przykład dla 3 usuń trzeci element z listy 3 razy, siódmy element 7 razy itd. (Zauważ, że to nie sekwencja, ale idea jest taka sama)
Ryan
@ Ryan Myślę, że ta sekwencja byłaby niezwykle podobna do liczb naturalnych :)
TheNumberOne
@TheBestOne Tak myślisz? Napisałem wcześniej na math.stackexchange: math.stackexchange.com/questions/1153889/…
Ryan
@ Ryan Właściwie źle zinterpretowałem twoją sugestię. Jak powiedziałeś w swoim pytaniu na stronie matematyki. Myślę, że byłoby to interesujące.
TheNumberOne

Odpowiedzi:

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]

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.

xnor
źródło
Potrzebujesz tylko n**2liczb, a nie2**n
Optymalizator
3
To jedno z maptwoich niesamowitych zastosowań . Zastanawiałem się, czy jest lepszy sposób ...
Sp3000,
@Optimizer Niestety, n**2+1chyba że sprawa n=1może zostać wybaczona.
xnor
Takie użycie mapy jest genialne. Jak przy użyciu zamówionego zestawu. Być może można również użyć map(A.index,B)do znalezienia indeksów elementów B w A, map(A.count,B)do znalezienia liczby elementów B w A, map(A.extend,B)do dodania spłaszczonej listy B do A. Umysł porusza się.
Logic Knight
13

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.

Zgarb
źródło
12

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.

feersum
źródło
10

> <> , 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)
Sp3000
źródło
7
Nadal lepszy niż Java;)
Optymalizator
5
Podoba mi się fakt, że naomożna to interpretować jako „wydrukuj to teraz”.
Zgarb
10

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
aditsu
źródło
Ciekawa technika :)
TheNumberOne
6

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ć).

Jakube
źródło
5

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
freekvd
źródło
64 bajty: zmień n=as.numeric(readline())na function(n){...}. Tworzy to obiekt funkcji, który można przypisać i wywołać. Upuść nawiasy klamrowe w forpętli.
Alex A.
Dzięki @Alex! Chociaż to 66, skoro potrzebuje nazwy?
freekvd
Nie wymaga nazwy do przesłania. Zobacz rozwiązania Matlab / Octave. Obiekty funkcji R są podobne do funkcji nienazwanych / lambda w innych językach, które są poprawnymi zgłoszeniami.
Alex A.
Co n=scan(n=1)?
koekenbakker
2
To działa! I to o 1 znak mniej. Jest jeszcze krótszy, gdybym upuścił n = 1, funkcja ignoruje wszystkie elementy n po pierwszym.
freekvd
4

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

Optymalizator
źródło
4

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.

Sp3000
źródło
3

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

Martin Ender
źródło
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 "}

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}
Vynce
źródło
3

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
dcsohl
źródło
2

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.

randomra
źródło
2

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]
edc65
źródło
1
Możesz zapisać 1, odliczając w pierwszej pętli, a w górę w drugiej: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)}
DocMax
Twój nie golfowany tutaj tak naprawdę nie pomaga: P;)
Optymalizator
@Optimizer unfolfed zaktualizowany - może nadal nie jest zbyt pomocny, ale przynajmniej działa teraz
edc65
Miałem na myśli więcej na temat „po prostu zmiana formatowania nie pomoże, proszę podać komentarze :)”
Optymalizator
2

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
Luis Mendo
źródło
Dzięki! Używałem tego w przeszłości, ale zwykle zapominam
Luis Mendo
@flawr Dobra uwaga. Ta odpowiedź staje się bardziej twoja niż moja! :-)
Luis Mendo,
Pewnie! Częściej spotykam się w StackOverflow, ale tam jest ten sam duch. Doceniam to!
Luis Mendo,
Słuszna uwaga! Nie jestem jednak pewien, czy to wszystko, czego się uczę, będzie pomocne lub faktycznie szkodliwe dla mojego standardowego użytkowania Matlaba, jednak :-P
Luis Mendo
2
Cóż, codegolf nie polega na użyciu, ale na nadużywaniu języka ^^
flawr
1

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}
Cyfrowa trauma
źródło
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.

David
źródło
7
W tym Code Golf dodaj liczbę bajtów.
edc65
1

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.

Sanchises
źródło
0

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)
rnso
źródło