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

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

• [_60:0:60:120:180] is giving me true; indeed it does not intersect at least one class in every m from 2 to 5 inclusive; additionally, it intersects only one class in every m from 2 to 5 inclusive. Aug 14, 2016 at 9:09
• I have the same for [-60, 0, 60, 120, 180] as @LeakyNun this should be admissible. Aug 14, 2016 at 9:18
• -60 0 60 120 180 240 300 intersects every residue class modulo 7, so it is not admissible. Aug 14, 2016 at 9:29
• Could we have longer testcases? Aug 14, 2016 at 9:35
• @LeakyNun: For any m, the first m primes larger than m form an admissible sequence. (The second-to-last Truthy test case is an example of this with m=7.) Falsy test cases can be generated by starting with the integers 1, ..., m, choosing k ≤ m, and adding random multiples of k to any or all of the starting integers 1, ..., m. Aug 14, 2016 at 9:55

# Brachylog, 2524 19 bytes

5 bytes thanks to Karl Napf.

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


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.


# Jelly, 10 bytes

JḊðḶḟ%@ð€Ạ

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


# 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

## 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.

• Well, it is not a trick, just mathematics ;-) Aug 14, 2016 at 10:13

# 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

• Hereby I give you credits for your approach that saved me 5 bytes. Aug 14, 2016 at 9:34
• @LeakyNun You're welcome! Aug 14, 2016 at 9:43

# Mathematica, 51 bytes

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


# 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

• I'm still getting oriented at this site, so apologies if this is a well-asked type of question, but: I would think that truthy/falsy values should be actual constants of some sort, not patterns such as "an array containing at least one zero". Shouldn't one process the array (using bitwise AND in this case) to arrive at constants in the end? Aug 14, 2016 at 16:49
• @GregMartin That's a very good question. We have pretty solid consensus about its answer; see here Aug 14, 2016 at 16:53
• Got it, and now I see the point of your first link. Thanks for the explanation! Aug 14, 2016 at 16:57