Краткое содержание: проверьте, является ли входная последовательность целых чисел «допустимой», что означает, что она не охватывает все классы вычетов для любого модуля.
Что такое «допустимая» последовательность?
Для целого числа m ≥ 2 классы вычетов по модулю m являются просто m возможными арифметическими прогрессиями общей разности m. Например, когда m = 4, 4 класса вычетов по модулю 4
..., -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-го остатка состоит из всех целых чисел, остаток которых при делении на m равен k. (если правильно определить «остаток» для отрицательных целых чисел)
Последовательность целых чисел a1, a2, ..., ak допустима по модулю m, если она не пересекает хотя бы один из классов вычетов. Например, {0, 1, 2, 3} и {-4, 5, 14, 23} не являются допустимыми по модулю 4, но {0, 1, 2, 4} и {0, 1, 5, 9} и {0, 1, 2, -3} являются допустимыми по модулю 4. Кроме того , {0, 1, 2, 3, 4} является не допустимым по модулю 4, а {0, 1, 2} является допустимым по модулю 4.
Наконец, последовательность целых чисел просто допустима, если она допустима по модулю m для любого целого числа m ≥ 2.
Соревнование
Напишите программу или функцию, которая принимает последовательность целых чисел в качестве входных данных и возвращает (непротиворечивое) значение Truthy, если последовательность допустима, и (непротиворечивое) значение Falsy, если последовательность недопустима.
Входная последовательность целых чисел может быть в любом разумном формате. Вы можете предположить, что входная последовательность имеет как минимум два целых числа. (Вы можете также предположить, что входные целые числа различны, если хотите, хотя это, вероятно, не помогает.) Вы должны быть в состоянии обрабатывать положительные и отрицательные целые числа (и 0).
Обычный код-гольф- выигрыш: самый короткий ответ, в байтах, выигрывает.
Пример ввода
Следующие входные последовательности должны давать значение Истина:
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
Следующие входные последовательности должны давать значение 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
подсказки
- Обратите внимание, что любая последовательность из 3 или менее целых чисел автоматически допустима по модулю 4. В более общем случае последовательность длины k автоматически допускается по модулю m, когда m> k. Отсюда следует, что проверка на допустимость действительно требует проверки конечного числа m.
- Отметим также, что 2 делит 4, и что любая последовательность, которая является допустимой по модулю 2 (то есть все четные или все нечетные), автоматически допустима по модулю 4. В более общем случае, если m делит n, а последовательность является допустимой по модулю m, то она автоматически допустимый по модулю n. Поэтому для проверки допустимости достаточно рассмотреть только простое число m, если хотите.
- Если a1, a2, ..., ak - допустимая последовательность, то a1 + c, a2 + c, ..., ak + c также допустимо для любого целого числа c (положительного или отрицательного).
Математическая значимость (дополнительное чтение)
Пусть a1, a2, ..., ak - последовательность целых чисел. Предположим, что существует бесконечно много целых чисел n, таких что n + a1, n + a2, ..., n + ak все простые. Тогда легко показать, что a1, a2, ..., ak должны быть допустимыми. Действительно, предположим, что a1, a2, ..., ak недопустимы, и пусть m - такое число, что a1, a2, ..., ak недопустимо по модулю m. Тогда независимо от того, какое n мы выберем, одно из чисел n + a1, n + a2, ..., n + ak должно быть кратным m, следовательно, не может быть простым.
Гипотеза простых k-кортежей является противоположностью этого утверждения, которое до сих пор остается широко открытой проблемой в теории чисел: оно утверждает, что если a1, a2, ..., ak - допустимая последовательность (или k-кортеж ), то должно быть бесконечно много целых чисел n, таких что n + a1, n + a2, ..., n + ak все простые. Например, допустимая последовательность 0, 2 дает утверждение, что должно быть бесконечно много целых чисел n, таких что n и n + 2 простые, это гипотеза о двойных простых числах (пока не доказано).
источник
[_60:0:60:120:180]
дает мне правду; на самом деле это не пересекаются по крайней мере один класс в каждомm
из2
к5
включительно; кроме того, он пересекает только один классm
от каждого2
до5
включительно.-60 0 60 120 180 240 300
пересекает каждый класс вычетов по модулю 7, поэтому это не допустимо.Ответы:
Желе, 10 байт
Попробуйте онлайн! или запустите все тестовые случаи .
источник
Брахилог ,
252419 байт5 байтов благодаря Карлу Напфу.
Попробуйте онлайн!
Проверьте все тестовые случаи!
источник
Python,
6160 байтВсе тестовые случаи на ideone
Редактировать: заменен логическим и с побитовым и сохранить один байт
источник
JavaScript (ES6), 59 байт
Использует трюк с набором остатков @ KarlNapf.
источник
Python,
6764 байтаКак неназванная лямбда:
set()
на{}
all(...)
range
должен идти доlen(N)+1
Старый код как функция (96 байт):
источник
Mathematica, 51 байт
источник
MATL , 11 байт
Истина - это массив (вектор-столбец), содержащий все единицы. Ложь - это массив, содержащий хотя бы один ноль. Вы можете проверить эти определения, используя эту ссылку .
Попробуйте онлайн! Или проверьте все тестовые случаи: правдивый , ложный (слегка измененный код, каждый случай выдает горизонтальный вектор для ясности).
объяснение
источник