17
\$\begingroup\$

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<k<210\$ 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
\$\endgroup\$

16 Answers 16

20
\$\begingroup\$

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]

The code can probably be golfed further.

\$\endgroup\$
  • \$\begingroup\$ Could you explain why the permutation is necessarily distinct from \$s\$? \$\endgroup\$ – dfeuer Apr 5 at 18:41
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Robin Ryder Apr 5 at 19:46
8
\$\begingroup\$

Haskell, 69 bytes

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!

\$\endgroup\$
  • 4
    \$\begingroup\$ Actually, my working title for this challenge was "Do I have a Chinese twin?" :) \$\endgroup\$ – Arnauld Apr 5 at 10:22
5
\$\begingroup\$

Perl 6, 64 61 59 43 bytes

{map($!=(*X%2,3,5,7).Bag,^209+$_+1)∋.&$!}

Try it online!

-16 thanks to @Jo King

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

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!

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

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!

\$\endgroup\$
  • \$\begingroup\$ Can you explain? \$\endgroup\$ – dfeuer Apr 5 at 6:24
  • 1
    \$\begingroup\$ @dfeuer It's using Robin Ryder's method. \$\endgroup\$ – Ørjan Johansen Apr 5 at 17:39
4
\$\begingroup\$

C# (Visual C# Interactive Compiler), 125 42 38 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!

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

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!

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

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.

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

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

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!

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

PHP, 81 78 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!

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

Python 3, 69 bytes

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

Try it online!

Hardcoded

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

05AB1E, 16 bytes

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

Try it online or verify all test cases.

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.

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

J, 40 bytes

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

Try it online!

Brute force...

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

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.

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

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
\$\endgroup\$
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – Jonathan Allan Apr 4 at 18:08
  • \$\begingroup\$ Oh, and you could get distinct values for no cost with Ḣe$ if you wanted :) \$\endgroup\$ – Jonathan Allan Apr 4 at 18:11
  • \$\begingroup\$ @JonathanAllan yes of course, thanks. :) \$\endgroup\$ – Nick Kennedy Apr 4 at 18:12

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.