Testing for admissible sequences

Question

Executive summary: test whether an input sequence of integers is "admissible", meaning that it doesn't cover all residue classes for any modulus.

What is an "admissible" sequence?

Given an integer m ≥ 2, the residue classes modulo m are just the m possible arithmetic progressions of common difference m. For example, when m=4, the 4 residue classes modulo 4 are

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

The kth residue class consists of all the integers whose remainder upon dividing by m equals k. (as long as one defines "remainder" correctly for negative integers)

A sequence of integers a1, a2, ..., ak is admissible modulo m if it fails to intersect at least one of the residue classes. For example, {0, 1, 2, 3} and {-4, 5, 14, 23} are not admissible modulo 4, but {0, 1, 2, 4} and {0, 1, 5, 9} and {0, 1, 2, -3} are admissible modulo 4. Also, {0, 1, 2, 3, 4} is not admissible modulo 4, while {0, 1, 2} is admissible modulo 4.

Finally, a sequence of integers is simply admissible if it is admissible modulo m for every integer m ≥ 2.

The challenge

Write a program or function that takes a sequence of integers as input, and returns a (consistent) Truthy value if the sequence is admissible and a (consistent) Falsy value if the sequence is not admissible.

The input sequence of integers can be in any reasonable format. You may assume that the input sequence has at least two integers. (You may also assume that the input integers are distinct if you want, though it probably doesn't help.) You must be able to handle positive and negative integers (and 0).

Usual code-golf scoring: the shortest answer, in bytes, wins.

Sample input

The following input sequences should each give a Truthy value:

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

The following input sequences should each give a Falsy value:

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

Tips

• Note that any sequence of 3 or fewer integers is automatically admissible modulo 4. More generally, a sequence of length k is automatically admissible modulo m when m > k. It follows that testing for admissibility really only requires checking a finite number of m.
• Note also that 2 divides 4, and that any sequence that is admissible modulo 2 (that is, all even or all odd) is automatically admissible modulo 4. More generally, if m divides n and a sequence is admissible modulo m, then it is automatically admissible modulo n. To check admissibility, it therefore suffices to consider only prime m if you wish.
• If a1, a2, ..., ak is an admissible sequence, then a1+c, a2+c, ..., ak+c is also admissible for any integer c (positive or negative).

Mathematical relevance (optional reading)

Let a1, a2, ..., ak be a sequence of integers. Suppose that there are infinitely many integers n such that n+a1, n+a2, ..., n+ak are all prime. Then it's easy to show that a1, a2, ..., ak must be admissible. Indeed, suppose that a1, a2, ..., ak is not admissible, and let m be a number such that a1, a2, ..., ak is not admissible modulo m. Then no matter what n we choose, one of the numbers n+a1, n+a2, ..., n+ak must be a multiple of m, hence cannot be prime.

The prime k-tuples conjecture is the converse of this statement, which is still a wide open problem in number theory: it asserts that if a1, a2, ..., ak is an admissible sequence (or k-tuple), then there should be infinitely many integers n such that n+a1, n+a2, ..., n+ak are all prime. For example, the admissible sequence 0, 2 yields the statement that there should be infinitely many integers n such that both n and n+2 are prime, this is the twin primes conjecture (still unproved).

Answer 1

Brachylog, 25 24 19 bytes

5 bytes thanks to Karl Napf.

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

Try it online!

Verify all testcases!

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.

Answer 2

Jelly, 10 bytes

JḊðḶḟ%@ð€Ạ

Try it online! or run all test cases.

               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)?

Answer 3

Python, 61 60 bytes

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

All test cases on ideone

Edit: replaced logical and with bitwise & to save one byte

Answer 4

JavaScript (ES6), 59 bytes

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

Uses @KarlNapf's Set of remainders trick.

Answer 5

Python, 67 64 bytes

As unnamed lambda:

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

• Edit1: replaced set() with {}
• Edit2: dont't need square brackets around generator in all(...)
• Edit3: As pointed out by Jonathan Allan, range must go up to len(N)+1

Old code as function (96 bytes):

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

Answer 6

Mathematica, 51 bytes

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

Answer 7

MATL, 11 bytes

"X@QGy\un>v

Truthy is an array (column vector) containing all ones. Falsy is an array containing at least one zero. You can check these definitions using this link.

Try it online! Or verify all test cases: truthy, falsy (slightly modified code, each case produces a horizontal vector for clarity).

Explanation

"       % 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