12
\$\begingroup\$

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

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

\$\endgroup\$
  • 3
    \$\begingroup\$ [_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. \$\endgroup\$ – Leaky Nun Aug 14 '16 at 9:09
  • 1
    \$\begingroup\$ I have the same for [-60, 0, 60, 120, 180] as @LeakyNun this should be admissible. \$\endgroup\$ – Karl Napf Aug 14 '16 at 9:18
  • \$\begingroup\$ -60 0 60 120 180 240 300 intersects every residue class modulo 7, so it is not admissible. \$\endgroup\$ – Greg Martin Aug 14 '16 at 9:29
  • \$\begingroup\$ Could we have longer testcases? \$\endgroup\$ – Leaky Nun Aug 14 '16 at 9:35
  • \$\begingroup\$ @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. \$\endgroup\$ – Greg Martin Aug 14 '16 at 9:55
4
\$\begingroup\$

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)?
\$\endgroup\$
7
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Well, it is not a trick, just mathematics ;-) \$\endgroup\$ – Karl Napf Aug 14 '16 at 10:13
2
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Hereby I give you credits for your approach that saved me 5 bytes. \$\endgroup\$ – Leaky Nun Aug 14 '16 at 9:34
  • \$\begingroup\$ @LeakyNun You're welcome! \$\endgroup\$ – Karl Napf Aug 14 '16 at 9:43
2
\$\begingroup\$

Mathematica, 51 bytes

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

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 
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Greg Martin Aug 14 '16 at 16:49
  • \$\begingroup\$ @GregMartin That's a very good question. We have pretty solid consensus about its answer; see here \$\endgroup\$ – Luis Mendo Aug 14 '16 at 16:53
  • 1
    \$\begingroup\$ Got it, and now I see the point of your first link. Thanks for the explanation! \$\endgroup\$ – Greg Martin Aug 14 '16 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.