Streszczenie: sprawdź, czy wejściowa sekwencja liczb całkowitych jest „dopuszczalna”, co oznacza, że ​​nie obejmuje wszystkich klas reszt dla żadnego modułu.

Co to jest „dopuszczalna” sekwencja?

Biorąc pod uwagę liczbę całkowitą m ≥ 2, klasy reszt modulo m są tylko m możliwymi postępami arytmetycznymi wspólnej różnicy m. Na przykład, gdy m = 4, 4 klasy reszt modulo 4 to

..., -8, -4, 0, 4, 8, 12, ...
..., -7, -3, 1, 5, 9, 13, ...
..., -6, -2, 2, 6, 10, 14, ...
..., -5, -1, 3, 7, 11, 15, ...

K-ta klasa resztowa składa się ze wszystkich liczb całkowitych, których reszta po podzieleniu przez m równa się k. (o ile poprawnie zdefiniowano „resztę” dla liczb całkowitych ujemnych)

Sekwencja liczb całkowitych a1, a2, ..., ak jest dopuszczalnym modułem, jeżeli nie przecina ona co najmniej jednej z klas reszt. Na przykład {0, 1, 2, 3} i {-4, 5, 14, 23} nie są dopuszczalnym modułem 4, ale {0, 1, 2, 4} i {0, 1, 5, 9} i {0, 1, 2, -3} są dopuszczalnym modułem 4. Również {0, 1, 2, 3, 4} nie jest dopuszczalnym modułem 4, podczas gdy {0, 1, 2} jest dopuszczalnym modułem 4.

Wreszcie, ciąg liczb całkowitych jest po prostu dopuszczalny, jeśli jest dopuszczalny moduł dla każdej liczby całkowitej m ≥ 2.

Wyzwanie

Napisz program lub funkcję, która pobiera sekwencję liczb całkowitych jako dane wejściowe i zwraca (spójną) wartość Prawdy, jeśli sekwencja jest dopuszczalna i (spójną) wartość Falsy, jeśli sekwencja jest niedopuszczalna.

Sekwencja wejściowa liczb całkowitych może mieć dowolny rozsądny format. Możesz założyć, że sekwencja wejściowa ma co najmniej dwie liczby całkowite. (Możesz również założyć, że wejściowe liczby całkowite są różne, jeśli chcesz, choć prawdopodobnie to nie pomaga.) Musisz być w stanie obsłużyć liczby całkowite dodatnie i ujemne (i 0).

Zwykle punktowanie w golfa : wygrywa najkrótsza odpowiedź w bajtach.

Przykładowe dane wejściowe

Następujące sekwencje wejściowe powinny dać wartość Prawda:

0 2
-1 1
-100 -200
0 2 6
0 2 6 8
0 2 6 8 12
0 4 6 10 12
-60 0 60 120 180
0 2 6 8 12 26
11 13 17 19 23 29 31
-11 -13 -17 -19 -23 -29 -31

Następujące sekwencje wejściowe powinny dać wartość Falsy:

0 1
-1 4
-100 -201
0 2 4
0 2 6 10
0 2 6 8 14
7 11 13 17 19 23 29
-60 0 60 120 180 240 300

Porady

• Należy zauważyć, że każda sekwencja 3 lub mniej liczb całkowitych jest automatycznie dopuszczalna modulo 4. Ogólniej, sekwencja długości k jest automatycznie dopuszczalna modulo m, gdy m> k. Wynika z tego, że sprawdzenie dopuszczalności wymaga jedynie sprawdzenia skończonej liczby m.
• Zauważ również, że 2 dzieli 4, i że każda sekwencja, która jest dopuszczalna modulo 2 (to znaczy wszystkie parzyste lub wszystkie nieparzyste) jest automatycznie dopuszczalna modulo 4. Ogólniej, jeśli m dzieli n, a sekwencja jest dopuszczalna modulo m, to jest automatycznie dopuszczalny moduł n. Aby sprawdzić dopuszczalność, wystarczy rozważyć tylko pierwszą liczbę m, jeśli chcesz.
• Jeśli a1, a2, ..., ak jest dopuszczalną sekwencją, to a1 + c, a2 + c, ..., ak + c jest również dopuszczalne dla dowolnej liczby całkowitej c (dodatniej lub ujemnej).

Znaczenie matematyczne (czytanie opcjonalne)

Niech a1, a2, ..., ak będą ciągiem liczb całkowitych. Załóżmy, że istnieje nieskończenie wiele liczb całkowitych n takich, że n + a1, n + a2, ..., n + ak są liczbami pierwszymi. Łatwo więc wykazać, że a1, a2, ..., ak muszą być dopuszczalne. Rzeczywiście, załóżmy, że a1, a2, ..., ak jest niedopuszczalne, i niech m będzie liczbą taką, że a1, a2, ... ak nie jest dopuszczalnym modułem. Zatem bez względu na to, co n wybierzemy, jedna z liczb n + a1, n + a2, ..., n + ak musi być wielokrotnością m, a zatem nie może być liczbą pierwszą.

Pierwotna hipoteza k-krotek jest odwrotnością tego stwierdzenia, które wciąż jest szeroko otwartym problemem w teorii liczb: stwierdza, że ​​jeśli a1, a2, ..., ak jest dopuszczalną sekwencją (lub k-krotką ), to jest powinno być nieskończenie wiele liczb całkowitych n takich, że n + a1, n + a2, ..., n + ak są liczbami pierwszymi. Na przykład dopuszczalna sekwencja 0, 2 daje stwierdzenie, że powinno być nieskończenie wiele liczb całkowitych n, tak aby zarówno n, jak i n + 2 były liczbami pierwszymi, jest to hipoteza podwójnych liczb pierwszych (wciąż niesprawdzona).

Galaretka, 10 bajtów

JḊðḶḟ%@ð€Ạ

Wypróbuj online! lub uruchom wszystkie przypadki testowe .

               Input: L.
JḊ             Range of [2..len(L)].
  ð    ð€      For x in [2..len(L)]:
   Ḷ             [0..x-1] (residue classes)
    ḟ              without elements from
     %@            L % x.
         Ạ     All truthy (non-empty)?

Brachylog , 25 24 19 bajtów

5 bajtów dzięki Karlowi Napfowi.

lybb '(eM-yA,?: [M] z:% aodA) 
l: 2' (eM-yA,?: [M] z:% aodA)
l: 2 '(eMg:? rz:% adlM)

Wypróbuj online!

Zweryfikuj wszystkie przypadki testowe!

l:2'(eMg:?rz:%adlM)
l:2                  Temp = [2:length(input)]
   '(             )  true if the following cannot be proven:
     eM                  M is an element of the interval
                         indicated by Temp, i.e. from 2
                         to the length of input inclusive,
       g:?rz:%adlM       every element of input modulo M
                         de-duplicated has length M.

Pyton, 61 60 bajtów

q=lambda l,d=2:d>len(l)or q(l,d+1)&(len({v%d for v in l})<d)

Wszystkie przypadki testowe na ideone

Edycja: zastąpiono logicznym i bitowym &, aby zapisać jeden bajt

JavaScript (ES6), 59 bajtów

a=>a.every((_,i)=>!i++|new Set(a.map(e=>(e%i+i)%i)).size<i)

Wykorzystuje @ KarlNapf's Set of reszt trick trick.

Python, 67 64 bajtów

Jako nienazwana lambda:

lambda N:all(len({i%m for i in N})<m for m in range(2,len(N)+1))

• Edycja1: zastąpiona set()przez{}
• Edycja2: nie potrzebujesz nawiasów kwadratowych wokół generatora all(...)
• Edycja3: Jak zauważył Jonathan Allan, rangetrzeba iść dolen(N)+1

Stary kod jako funkcja (96 bajtów):

def f(N):
 for m in range(2,len(N)+1):
    if len(set(i%m for i in N))==m:return False
 return True

Mathematica, 51 bajtów

And@@Table[Length@Union@Mod[#,i]<i,{i,2,Length@#}]&

MATL , 11 bajtów

"X@QGy\un>v

Prawda to tablica (wektor kolumny) zawierająca wszystkie. Falsy to tablica zawierająca co najmniej jedno zero. Możesz sprawdzić te definicje za pomocą tego linku .

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe: prawda , fałsz (nieznacznie zmodyfikowany kod, każdy przypadek tworzy poziomy wektor dla przejrzystości).

Wyjaśnienie

"       % Take input array. For each; i.e. repeat n times, where n is arrray size
  X@Q   %   Push iteration index plus 1, say k. So k is 2 in the first iteration,
        %   3 in the second, ... n+1 in the last. Actually we only need 2, ..., n;
        %   but the final n+1 doesn't hurt
  G     %   Push input again
  y     %   Duplicate k onto the top of the stack
  \     %   Modulo. Gives vector of remainders of input when divided by k
  un    %   Number of distinct elements
  >     %   True if that number is smaller than k
  v     %   Vertically concatenate with previous results
        % End for each. Implicitly display