# Do I have a twin with permutated remainders?

We define $$\R_n\$$ as the list of remainders of the Euclidean division of $$\n\$$ by $$\2\$$, $$\3\$$, $$\5\$$ and $$\7\$$.

Given an integer $$\n\ge0\$$, you have to figure out if there exists an integer $$\0 such that $$\R_{n+k}\$$ is a permutation of $$\R_n\$$.

## Examples

The criterion is met for $$\n=8\$$, because:

• we have $$\R_8=(0,2,3,1)\$$
• for $$\k=44\$$, we have $$\R_{n+k}=R_{52}=(0,1,2,3)\$$, which is a permutation of $$\R_8\$$

The criterion is not met for $$\n=48\$$, because:

• we have $$\R_{48}=(0,0,3,6)\$$
• the smallest integer $$\k>0\$$ such that $$\R_{n+k}\$$ is a permutation of $$\R_{48}\$$ is $$\k=210\$$ (leading to $$\R_{258}=(0,0,3,6)\$$ as well)

## Rules

• You may either output a truthy value if $$\k\$$ exists and a falsy value otherwise, or two distinct and consistent values of your choice.
• This is .

## Hint

Do you really need to compute $$\k\$$? Well, maybe. Or maybe not.

## Test cases

Some values of $$\n\$$ for which $$\k\$$ exists:

3, 4, 5, 8, 30, 100, 200, 2019


Some values of $$\n\$$ for which $$\k\$$ does not exist:

0, 1, 2, 13, 19, 48, 210, 1999


# R, 63 59 bytes

s=scan()%%c(2,3,5,7);i=which(s<c(0,2,3,5));any(s[i]-s[i-1])


Try it online!

-4 bytes thanks to Giuseppe

(The explanation contains a spoiler as to how to solve the problem without computing $$\k\$$.)

Explanation: Let $$\s\$$ be the list of remainders. Note the constraint that s[1]<2, s[2]<3, s[3]<5 and s[4]<7. By the Chinese Remainder Theorem, there exists a $$\k\$$ iff there is a permutation of $$\s\$$, distinct from $$\s\$$, which verifies the constraint. In practice, this will be verified if one of the following conditions is verified:

• s[2]<2 and s[2]!=s[1]
• s[3]<3 and s[3]!=s[2]
• s[4]<5 and s[4]!=s[3]
• Could you explain why the permutation is necessarily distinct from $s$? – dfeuer Apr 5 '19 at 18:41
• @dfeuer It is a consequence of the Chinese Remainder Theorem; I added a link. If two integers have the same remainders modulo 2, 3, 5 and 7 (without a permutation), then the two integers are equal modulo 2*3*5*7=210. – Robin Ryder Apr 5 '19 at 19:46

Based on the Chinese remainder theorem

m=[2,3,5,7]
f x|s<-mod x<$>m=or[m!!a>b|a<-[0..2],b<-drop a s,s!!a/=b]  Try it online! • Actually, my working title for this challenge was "Do I have a Chinese twin?" :) – Arnauld Apr 5 '19 at 10:22 # Haskell, 47 bytes g.mod g r|let p?q=r p/=r q&&r q<p=2?3||3?5||5?7  Try it online! • Can you explain? – dfeuer Apr 5 '19 at 6:24 • @dfeuer It's using Robin Ryder's method. – Ørjan Johansen Apr 5 '19 at 17:39 # Perl 6, 646159 43 bytes {map($!=(*X%2,3,5,7).Bag,^209+$_+1)∋.&$!}


Try it online!

-16 thanks to @Jo King

# C# (Visual C# Interactive Compiler), 1254238 36 bytes

n=>n%7<5&5<n%35|n%5<3&3<n%15|-~n%6>3


Direct port of @xnor's answer, which is based off of @RobinRyder's solution.

Saved 4 bytes thanks to @Ørjan Johansen!

Saved 2 more thanks to @Arnauld!

Try it online!

• I found a variation that only ties for xnor's languages but helps for this: 38 bytes – Ørjan Johansen Apr 5 '19 at 6:04
• Isn't -~n%6/4>0 just -~n%6>3? – Arnauld Apr 6 '19 at 9:55
• BTW, this is a JavaScript polyglot. – Arnauld Apr 7 '19 at 7:55

# Python 2, 41 bytes

lambda n:n%5!=n%7<5or n%3!=n%5<3or-~n%6/4


Try it online!

Uses the same characterization as Robin Ryder. The check n%2!=n%3<2 is shortened to -~n%6/4. Writing out the three conditions turned out shorter than writing a general one:

46 bytes

lambda n:any(n%p!=n%(p+1|1)<p for p in[2,3,5])


Try it online!

# Wolfram Language (Mathematica), 67 bytes

!FreeQ[Sort/@Table[R[#+k],{k,209}],Sort@R@#]&
R@n_:=n~Mod~{2,3,5,7}


Try it online!

# Ruby, 54 bytes

->n{[2,3,5,7].each_cons(2).any?{|l,h|n%l!=n%h&&n%h<l}}


Try it online!

Uses Robin Ryder's clever solution.

# Wolfram Language (Mathematica), 56 bytes

Or@@(Min[s-#]>0&/@Rest@Permutations@Mod[#,s={2,3,5,7}])&


Try it online!

Finds all non-identity permutations of the remainders of the input modulo 2, 3, 5, 7, and checks if any of them are below {2,3,5,7} in each coordinate. Note that Or@@{} is False.

# Java (JDK), 36 bytes

n->n%7<5&5<n%35|n%5<3&3<n%15|-~n%6>3


Try it online!

## Credits

• Port of xnor's solution, improved by Ørjan Johansen.

# R, 72 bytes

n=scan();b=c(2,3,5,7);for(i in n+1:209)F=F|all(sort(n%%b)==sort(i%%b));F


Try it online!

# PHP, 8178 72 bytes

while($y<3)if($argn%($u='235'[$y])!=($b=$argn%'357'[$y++])&$b<$u)die(T);  A riff on @Robin Ryder's answer. Input is via STDIN, output is 'T' if truthy, and empty '' if falsy. $ echo 3|php -nF euc.php
T
$echo 5|php -nF euc.php T$ echo 2019|php -nF euc.php
T
$echo 0|php -nF euc.php$ echo 2|php -nF euc.php

$echo 1999|php -nF euc.php  Try it online! ### Or 73 bytes with 1 or 0 response while($y<3)$r|=$argn%($u='235'[$y])!=($b=$argn%'357'[$y++])&$b<$u;echo$r;

$echo 2019|php -nF euc.php 1$ echo 1999|php -nF euc.php
0


Try it online (all test cases)!

### Original answer, 133 127 bytes

function($n){while(++$k<210)if(($r=function($n){foreach([2,3,5,7]as$d)$o[]=$n%$d;sort($o);return$o;})($n+$k)==$r($n))return 1;}


Try it online!

# Python 3, 69 bytes

lambda x:int('4LR2991ODO5GS2974QWH22YTLL3E3I6TDADQG87I0',36)&1<<x%210


Try it online!

Hardcoded

# 05AB1E, 16 bytes

Ƶ.L+ε‚ε4Åp%{}Ë}à


Explanation:

Ƶ.L          # Create a list in the range [1,209] (which is k)
+         # Add the (implicit) input to each (which is n+k)
ε        # Map each value to:
‚       #  Pair it with the (implicit) input
ε      #  Map both to:
4Åp   #   Get the first 4 primes: [2,3,5,7]
%  #   Modulo the current number by each of these four (now we have R_n and R_n+k)
{ #   Sort the list
}Ë     #  After the inner map: check if both sorted lists are equal
}à      # After the outer map: check if any are truthy by taking the maximum
# (which is output implicitly as result)


See this 05AB1E tip of mine (section How to compress large integers?) to understand why Ƶ. is 209.

# J, 40 bytes

1 e.(>:+i.@209)-:&(/:~)&(2 3 5 7&|"1 0)]


Try it online!

Brute force...

# Jelly, 15 bytes

8ÆR©PḶ+%Ṣ¥€®ċḢ$ Try it online! I’m sure there’s a golfier answer. I’ve interpreted a truthy value as being anything that isn’t zero, so here it’s the number of possible values of k. If it needs to be two distinct values that costs me a further byte. ### Explanation 8ÆR | Primes less than 8 [2,3,5,7] © | Copy to register P | Product [210] Ḷ | Lowered range [0, 1, ..., 208, 209] + | Add to input ¥€ | For each of these 210 numbers... % ® | Modulo 2, 3, 5, 7 Ṣ | And sort ċḢ$ | Count how many match the first (input) number’s remainders

• All good regarding truthy vs falsey. Using the meta agreed definition of truthy and falsey (effectively "what does the language's if-else construct do if there is one) zero is falsey and non-zeros are truthy (? is the if-else construct in Jelly; for some languages it's a harder question). – Jonathan Allan Apr 4 '19 at 18:08
• Oh, and you could get distinct values for no cost with Ḣe\$ if you wanted :) – Jonathan Allan Apr 4 '19 at 18:11
• @JonathanAllan yes of course, thanks. :) – Nick Kennedy Apr 4 '19 at 18:12