Nietykalni

9

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ą nza pomocą standardowych parametrów wejściowych lub funkcji i drukuje pierwsze nnietykalne 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 , 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.

Kade
źródło
Jest to czysto spekulacyjne, ponieważ tak naprawdę nie zastanawiałem się, jak to rozwiązać: Czy oszustwo byłoby, gdyby przyjęłam górną granicę wynikowych liczb? Powiedzmy, czy napisałem kod, który znajduje tylko nietykalne liczby do 60 000? To by wystarczyło na pokrycie zakresu wejściowego. Ale oczywiście wiem to tylko na podstawie częściowych wyników, które podałeś.
Reto Koradi
Myślę, że byłoby dobrze. Z technicznego punktu widzenia nie jest to twarde zakodowanie wyników, o ile wiem, nie narusza standardowych luk. Dopóki pasuje do reszty specyfikacji, będzie dobrze.
Kade
@vihan Zdecydowanie nie.
Kade

Odpowiedzi:

6

Pyth, 21 bajtów

.f!fqZsf!%TYStTSh^Z2Q

Ostrzeżenie: niezwykle powolne. Uruchomienie testowe i harmonogram poniżej.

$ time pyth -c '.f!fqZsf!%TYStTSh^Z2Q' <<< 3
[2, 5, 52]

real    2m46.463s
user    2m46.579s
sys 0m0.004s

Jest to w zasadzie tak brutalna siła, jak to tylko możliwe, testuje faktoryzacje do potencjalnej samotnej liczby podniesionej do kwadratu plus jeden.

isaacg
źródło
4

C, 104 bajty

j,i,z,w;u(y){for(z=2;y;z++)for(w=0;(++w<z*z||0&printf("%i ",z)+y--)&&j^z;)for(i=j=0;++i<w;j+=i*!(w%i));}

Zajmie to kilka minut dla y > 20, ale cokolwiek.

Oberon
źródło
2

Java, 310 bajtów

class U{int[] p;U(int e){p=new int[(int)4e9];for(int i=1,c=0;c<e;i++)if(u(i)>0){System.out.println(i);c++;}}int p(int n){if(p[n]!=0)return p[n];int i,s=1;for(i=2;i<=n-1;i++)s+=n%i==0?i+(n/i!=i?n/i:0):0;return(p[n]=s);}int u(int n){if(n==1)return 0;for(int i=2;i<=(n-1)*(n-1);i++)if(p(i)==n)return 0;return 1;}}

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

public class Untouchable {
    int[] properDivisorSumMap;


    public Untouchable(int estimatedMaxium){
        properDivisorSumMap = new int[(estimatedMaxium-1)*(estimatedMaxium-1)];
    }


    public int properDivisorSum(int n){
        if(properDivisorSumMap[n] != 0){
            return properDivisorSumMap[n];
        }

        int sum = 1;
        for(int i=2;i<=(int)Math.sqrt(n);i++){
            if(n%i==0){
                sum+=i;
                if(n/i != i){
                    sum+=n/i;
                }
            }
        }
        properDivisorSumMap[n] = sum;
        return sum;
    }


    public boolean untouchable(int n){
        if(n==1){
            return false;
        }
        for(int i=2;i<=(n-1)*(n-1);i++){
            if(properDivisorSum(i) == n){
                return false;
            }
        } 
        return true;
    }


    public static void main(String[] args){
        Untouchable test = new Untouchable(8480);

        int elements = Integer.parseInt(args[0]);

        for(int i=1,count=0;count < elements;i++){
            if(test.untouchable(i)){
                System.out.printf("%4d: %4d%n",count,i);
                count++;
            }
        }
    }
}
ankh-morpork
źródło
1

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.

func untouchable(n int) {
    const C = 59997
    const N = C * C
    s := make([]uint16, N)
    for d := 1; d < N; d++ {
        for i := 2 * d; i < N; i += d {
            v := int(s[i]) + d
            if v > C {
                v = C + 1 // saturate at C+1
            }
            s[i] = uint16(v)
        }
    }
    var m [C]bool
    for i := 2; i < N; i++ {
        if s[i] < C {
            m[s[i]] = true
        }
    }
    for i := 2; n > 0; i++ {
        if !m[i] {
            println(i)
            n--
        }
    }
}
Keith Randall
źródło