11
\$\begingroup\$

Given 3 positive integers a, b, and n (whose maximum values are the maximum representable integer value in your language), output a truthy value if a ≡ b (mod n), and falsey otherwise. For those unfamiliar with congruency relations, a ≡ b (mod n) is true iff a mod n = b mod n (or, equivalently, (a - b) mod n = 0).

Restrictions

  • Built-in congruence testing methods are forbidden
  • Built-in modulo operations are forbidden (this includes operations such as Python's divmod function, which return both the quotient and the remainder, as well as divisibility functions, residue system functions, and the like)

Test Cases

(1, 2, 3) -> False
(2, 4, 2) -> True
(3, 9, 10) -> False
(25, 45, 20) -> True
(4, 5, 1) -> True
(83, 73, 59) -> False
(70, 79, 29) -> False
(16, 44, 86) -> False
(28, 78, 5) -> True
(73, 31, 14) -> True
(9, 9, 88) -> True
(20, 7, 82) -> False

This is , so shortest code (in bytes) wins, with earliest submission as a tiebreaker.

\$\endgroup\$
  • \$\begingroup\$ How about divisibility functions? \$\endgroup\$ – Conor O'Brien Feb 12 '16 at 20:28
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ Those work by testing remainders, so they are also forbidden. I'll clarify. \$\endgroup\$ – user45941 Feb 12 '16 at 20:28
  • \$\begingroup\$ How about Python 2's integer floor division /? \$\endgroup\$ – xnor Feb 12 '16 at 20:29
  • \$\begingroup\$ Floating point division? \$\endgroup\$ – El'endia Starman Feb 12 '16 at 20:31
  • 1
    \$\begingroup\$ Base conversion? \$\endgroup\$ – Dennis Feb 12 '16 at 20:33

15 Answers 15

5
\$\begingroup\$

Jelly, 5 bytes

_ÆD⁵e

Making heavy use of Anything else that is not forbidden is allowed.

Try it online!

How it works

_ÆD⁵e  Main link. Left input: a. Right input: b. Additional input: n

_      Subtract b from a.
 ÆD    Compute all divisors of the difference.
   ⁵e  Test if n is among the divisors.
\$\endgroup\$
4
\$\begingroup\$

Python 2, 27 bytes

lambda a,b,n:(a-b)/n*n==a-b

Checks if a-b is a multiple of n by dividing by n, which automatically floors, and seeing if multiplying back by n gives the same result.

\$\endgroup\$
4
\$\begingroup\$

Julia, 24 bytes

f(a,b,n,t=a-b)=t÷n==t/n

This is a function that accepts three integers and returns a boolean.

We simply test whether a - b integer divded by n is equal to a - b float divided by n. This will be true when there is no remainder from division, i.e. a - b | n, which implies that a - b (mod n) = 0.

\$\endgroup\$
4
\$\begingroup\$

Pyth, 7 bytes

!@UQ-FE

Uses Pyth's cyclic indexing.

  UQ         range(first line). [0,...,Q-1]
    -FE      Fold subtraction over the second line.
 @           Cyclic index UQ at -FE
!            Logical NOT
\$\endgroup\$
3
\$\begingroup\$

Haskell, 23 bytes

(a#b)n=div(a-b)n*n==a-b

Usage example: (28#78)5 -> True.

Same method as in @xnor's answer.

\$\endgroup\$
3
\$\begingroup\$

Minkolang 0.15, 14 11 bytes

nn-n$d:*=N.

Try it here! Input is expected as a b n.

Explanation:

n              Take number from input -> a
 n             Take number from input -> a, b
  -            Subtract               -> a-b
   n           Take number from input -> a-b, n
    $d         Duplicate stack        -> a-b, n, a-b, n
      :        Integer division       -> a-b, n, (a-b)//n
       *       Multiply               -> a-b, (a-b)//n*n
        =      1 if equal, 0 otherwise
         N.    Output as number and stop.
\$\endgroup\$
3
\$\begingroup\$

MATL, 9 bytes

Sdt:i*0hm

Input format is

[a b]
n

Try it online!

S     % implicitly input [a, b]. Sort this array
d     % compute difference. Gives abs(a-b)
t:    % duplicate and generate vector [1,2,...,abs(a-b)]; or [] if a==b
i*    % input n and multiply to obtain [n,2*n,...,abs(a-b)*n]; or []
0h    % concatenate element 0
m     % ismember function. Implicitly display
\$\endgroup\$
3
\$\begingroup\$

Retina, 20

^(1+) \1*(1*) \1*\2$

Input is given in unary, space-separated, in order n a b. Output 1 for truthy and 0 for falsey.

Try it online.


If you prefer decimal input then you can do this:

\d+
$&$*1
^(1+) \1*(1*) \1*\2$

Try it online.

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

APL, 15 bytes

{(⌊d)=d←⍺÷⍨-/⍵}

This is a dyadic function that accepts n on the left and a and b as an array on the right.

The approach here is basically the same as in my Julia answer. We test whether a - b / n is equal to the floor of itself, which will be true when a - b (mod n) = 0.

\$\endgroup\$
  • \$\begingroup\$ Save a four: d=⌊d←⎕÷⍨-/⎕ \$\endgroup\$ – Adám Oct 10 '19 at 8:14
2
\$\begingroup\$

JavaScript (ES6), 27 bytes

@CᴏɴᴏʀO'Bʀɪᴇɴ posted a version which does not work; here is the "common algorithm" that people are using in a form which "works":

(a,b,n)=>n*(0|(a-b)/n)==a-b

The word "works" is in scare quotes because the shortcut we're using for Math.floor() implicitly truncates a number to be in the signed 32-bit range, so this cannot handle the full 52-bit-or-whatever space of integers that JavaScript can describe.

\$\endgroup\$
  • \$\begingroup\$ If this answer cannot handle all representable positive integers in the language, it is not valid. \$\endgroup\$ – user45941 Feb 12 '16 at 20:55
  • 1
    \$\begingroup\$ @Mego: Given that some languages will be using 32-bit integers, I think that restriction is onerously arbitrary unless you further specify either the bit-width of the integers or else that the language must have bignums. \$\endgroup\$ – CR Drost Feb 12 '16 at 20:59
  • 1
    \$\begingroup\$ It's not at all arbitrary. The challenge clearly states that the inputs may be any 3 positive integers, up to the maximum representable integer value in the chosen language. If the submission might fail for a set of inputs in that range, it's not valid. Relevant meta post. \$\endgroup\$ – user45941 Feb 12 '16 at 21:02
  • \$\begingroup\$ @Mego: Let me ask you point-blank: Are you going to object to the Haskell solution on the same criterion? (The Haskell solution is polymorphic because it does not have a signature and is not written in a way which invokes the Dreaded Monomorphism Restriction. For normal signed types it works perfectly well across the whole range; however there exists a set of inputs that you can put in -- a test set is (2, 150, 3) :: (Word8, Word8, Word8); the criterion you specify is explicitly "if theoretically an input exists that makes the answer invalid, the answer should be deemed invalid.") \$\endgroup\$ – CR Drost Feb 12 '16 at 21:18
  • 1
    \$\begingroup\$ @Mego: If you're wondering why I'm making a big deal out of this, the JavaScript number type contains noncontinuous integers around the 2^52-ish fringes, so that it becomes very possible that (a - b) == a for certain values of a. An answer which has to be valid off in those borderlands is nearly impossible even if I take the byte penalty and replace (0|...) with Math.floor(...). \$\endgroup\$ – CR Drost Feb 12 '16 at 21:25
2
\$\begingroup\$

CJam, 7 bytes

l~-\,=!

Input order is n a b.

Test it here.

Explanation

l~  e# Read input and evaluate to push n, a and b onto the stack.
-   e# Subtract b from a.
\,  e# Swap with n and turn into range [0 1 ... n-1].
=   e# Get (a-b)th element from that range, which uses cyclic indexing. This is
    e# equivalent to modulo, and as opposed to the built-in % it also works correctly
    e# for negative (a-b).
!   e# Negate, because a 0 result from the previous computation means they are congruent.
\$\endgroup\$
1
\$\begingroup\$

Python 3, 27 bytes

lambda a,b,n:pow(a-b,1,n)<1

pow(x,y,n) calculates (x**y)%n, so this is just (a-b)**1%n.

\$\endgroup\$
1
\$\begingroup\$

ES6, 28 bytes

(a,b,n)=>!/\./.test((a-b)/n)

Works by looking for a decimal point in (a-b)/n which I'm hoping is allowed.

\$\endgroup\$
1
\$\begingroup\$

Seriously, 10 bytes

,,,-A│\)/=

Takes input as N\nA\nB\n (capital letters used to distinguish from newlines).

Try it online

This uses the same method as @AlexA's answer

Explanation (capital letters used as variable names for explanatory purposes):

,,,-A│\)/=
,,,         push N, A, B
   -A       push C = abs(A-B)
     │      duplicate entire stack (result is [N, C, N, C])
      \)/=  1 if C//N == C/N (floored division equals float division)
\$\endgroup\$
0
\$\begingroup\$

F#, 24 bytes

fun a b n->(a-b)/n*n=a-b

Implements the same check as @xnor's answer.

\$\endgroup\$

Your Answer

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