Nietykalne liczby α
Nietykalna liczba jest dodatnią liczbą całkowitą, której nie można wyrazić jako sumę wszystkich właściwych dzielników dowolnej dodatniej liczby całkowitej (w tym samej liczby nietykalnej).
Na przykład liczba 4 nie jest nietykalna, ponieważ jest równa sumie właściwych dzielników 9: 1 + 3 = 4. Liczba 5 jest nietykalna, ponieważ nie jest sumą właściwych dzielników jakiejkolwiek dodatniej liczby całkowitej. 5 = 1 + 4 to jedyny sposób, aby zapisać 5 jako sumę różnych dodatnich liczb całkowitych, w tym 1, ale jeśli 4 dzieli liczbę, 2 również, więc 1 + 4 nie może być sumą wszystkich właściwych dzielników dowolnej liczby (ponieważ lista czynników musiałaby zawierać zarówno 4, jak i 2).
Uważa się, że liczba 5 jest jedyną nieparzystą liczbą nietykalną, ale nie zostało to udowodnione: wynikałoby to z nieco mocniejszej wersji hipotezy Goldbacha. β
Istnieje nieskończenie wiele nietykalnych liczb, co udowodnił Paul Erdős.
Kilka właściwości nietykalnych:
- Żaden nietykalny jest o 1 większy niż liczba pierwsza
- Żaden nietykalny nie jest większy niż 3, z wyjątkiem 5
- Nietykalny jest liczbą idealną
- Do tej pory wszystkie nietykalne oprócz 2 i 5 są złożone.
Cel
Utwórz program lub funkcję, która pobiera liczbę naturalną n
za pomocą standardowych parametrów wejściowych lub funkcji i drukuje pierwsze n
nietykalne liczby.
Dane wyjściowe muszą mieć separację między liczbami, ale może to być cokolwiek (tj. Znaki nowej linii, przecinki, spacje itp.).
To powinno być w stanie działać przynajmniej 1 <= n <= 8153
. Jest to oparte na tym, że plik b przewidziany dla wpisu OEIS γ idzie w górę n = 8153
.
Standardowe luki są niedozwolone, jak zwykle.
Przykład I / O
1 -> 2
2 -> 2, 5
4 -> 2, 5, 52, 88
10 -> 2, 5, 52, 88, 96, 120, 124, 146, 162, 188
8153 -> 2, 5, 52, 88, 96, 120, ..., ..., ..., 59996
To jest golf-golf, więc wygrywa najmniejsza liczba bajtów.
α - Wikipedia , β - MathWorld , γ - OEIS
Z jakiegoś powodu oznaczono to jako duplikat pytania „znajdowanie liczb półfunkcyjnych”, jednak zadania są zupełnie inne. W takim przypadku musisz sprawdzić, czy żadna suma doskonałych dzielników dowolnej liczby naturalnej nie może być równa określonej liczbie.
Odpowiedzi:
Pyth, 21 bajtów
Ostrzeżenie: niezwykle powolne. Uruchomienie testowe i harmonogram poniżej.
Jest to w zasadzie tak brutalna siła, jak to tylko możliwe, testuje faktoryzacje do potencjalnej samotnej liczby podniesionej do kwadratu plus jeden.
źródło
C, 104 bajty
Zajmie to kilka minut dla y > 20, ale cokolwiek.
źródło
Java, 310 bajtów
Grałem w golfa tak dobrze, jak tylko mogłem, ale byłem bardziej zainteresowany upewnieniem się, że będzie działał w rozsądnym czasie. Wersja nieklofowana jest prawdopodobnie bardziej interesująca
źródło
Idź, 396 bajtów
Nie bardzo gra w golfa, ale może wykonać cały wymagany zasięg. Działa w około ~ 20 minut i potrzebuje ~ 7 GB (niezależnie od n). Tworzy gigantyczną tablicę do obliczania sumy dzielników dla wszystkich liczb do 59997 podniesionych do kwadratu.
źródło