18
\$\begingroup\$

The task:

Output a value for x, where a mod x = b for two given values a,b.

Assumption

  • a and b will always be positive integers
  • There won't always be a solution for x
  • If multiple solutions exist, output at least one of them.
  • If there aren't any solutions, output nothing or some indication that no solutions exist.
  • Built-ins are allowed (not as fun as other mathematical approaches)
  • Outputs are always integers

Examples

A, B >> POSSIBLE OUTPUTS

5, 2 >> 3
9, 4 >> 5
8, 2 >> 3, 6
6, 6 >> 7, (ANY NUMBER > 6)
8, 7 >> NO SOLUTION
2, 4 >> NO SOLUTION
8, 5 >> NO SOLUTION
10,1 >> 3, 9

This is , so lowest bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Can it error if no solution is found? \$\endgroup\$ – clap May 17 '17 at 3:14
  • \$\begingroup\$ @ConfusedMr_C Technically that does indicate no solution, so yes. \$\endgroup\$ – Graviton May 17 '17 at 20:55

28 Answers 28

11
\$\begingroup\$

JavaScript, 28 27 26 24 23 bytes

a=>b=>(a-=b)?a>b&&a:b+1

Try it online!

false indicates no solution.

-1 thanks @Arnauld

\$\endgroup\$
  • \$\begingroup\$ Nicely done and nicely golfed. \$\endgroup\$ – Shaggy May 16 '17 at 20:54
  • \$\begingroup\$ So, to call it, you need to give the outer function a name, say f=..., then call f(8)(3)? That seems a little bit cheaty? The normal way to call a function would be f(8,3), which would make your function definition longer? \$\endgroup\$ – Steve Bennett May 17 '17 at 11:56
  • 3
    \$\begingroup\$ @SteveBennett True, the definition is curried, which means it must be called like (8)(3), but there is a consensus on PPCG that that's allowed. You don't have to give it a name though. \$\endgroup\$ – eush77 May 17 '17 at 12:10
  • 1
    \$\begingroup\$ @SteveBennett It's amusing how you think 26 vs -15 is anything but a clear consensus. Good luck trying to dispute. \$\endgroup\$ – eush77 May 17 '17 at 12:25
  • 1
    \$\begingroup\$ @SteveBennett how is 55 to 1 a weak consensus? \$\endgroup\$ – Cyoce May 24 '17 at 17:16
6
\$\begingroup\$

MATL, 6 bytes

tQ:\=f

Try it online! Or verify all test cases.

Explanation

Consider inputs 8, 2 as an example.

t    % Implicit input. Duplicate                STACK: 8, 8
Q    % Add 1                                    STACK: 8, 9
:    % Range                                    STACK: 8, [1 2 3 4 5 6 7 8 9]
\    % Modulo                                   STACK: [0 0 2 0 3 2 1 0 8]
=    % Implicit input. Equality comparison      STACK: [0 0 1 0 0 1 0 0 0]
f    % Indices of nonzeros. Implicit display    STACK: [3 6]
\$\endgroup\$
5
\$\begingroup\$

Python 2, 40 34 bytes

-6 bytes thanks to Bubbler

lambda a,b:[(a==b)*-~a,a-b][a>b*2]

Try it online!

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

Jelly, 5 bytes

‘R⁸%i

Returns the minimal valid x or 0 is there is none.

Try it online!

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

Groovy, 48 bytes (using built-in):

{a,b->Eval.me(a+"g").modInverse(Eval.me(b+"g"))}

Eval.me(...+"g") - Affixes "g" to the input, making it a BigInteger.

modInverse(...) - Performs the inverse modulo operation.


Java 8, 70 bytes

{a,b->return BigInteger.valueOf(a).modInverse(BigInteger.valueOf(b));}
\$\endgroup\$
3
\$\begingroup\$

R, 33 28 bytes

pryr::f(match(b,a%%1:(a+1)))

Try it online!

-4 bytes thanks to Jarko Dubbeldam.

-1 byte thanks to Giuseppe.

Returns NA if there is no solution. TIO doesn't have the pryr library installed, so the code at that link uses function(a,b) instead.

\$\endgroup\$
  • \$\begingroup\$ pryr::f(which(a%%1:(a+1)==b)) is 4 bytes shorter. \$\endgroup\$ – JAD May 17 '17 at 9:21
  • \$\begingroup\$ you can also drop another byte by using match(b,a%%1:(a+1)), which returns NA for a missing value. \$\endgroup\$ – Giuseppe May 17 '17 at 15:47
1
\$\begingroup\$

Jelly, 11 10 bytes

³%_⁴
r‘ÇÐḟ

A full program taking the two positive integers, a and b, and printing a list of the integer solutions between min(a,b)+1 and max(a,b)+1 inclusive.

Try it online!

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

Mathematica 36 Bytes

a_±b_:=Select[Range[9a],a~Mod~#==b&]

Input:

5 ± 2
9 ± 4
8 ± 2
6 ± 6
8 ± 7
2 ± 4
8 ± 5
10 ± 1

Output:

{3}
{5}
{3, 6}
{7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, \
25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, \
42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54}
{}
{}
{}
{3, 9}
\$\endgroup\$
  • \$\begingroup\$ When using these extended ASCII operators in a binary form, they need a space in front when being defined, otherwise the parser throws an error. So it would have to be a_ ±b_. But it's shorter to use Cases instead of Select an an unnamed function anyway: Cases[Range[9#],x_/;#~Mod~x==#2]& \$\endgroup\$ – Martin Ender May 17 '17 at 8:56
1
\$\begingroup\$

Haskell, 33 bytes

Crashes with code.hs: out of memory (requested ??? bytes) if there is no solution (times out on TIO before that):

a!b=[x|x<-[b+1..],mod(a-b)x<1]!!0

Try it online!

Thanks at Ørjan Johansen for spotting a mistake!

\$\endgroup\$
  • \$\begingroup\$ This gives wrong answers for the test cases where b divides a. \$\endgroup\$ – Ørjan Johansen Oct 2 '18 at 3:11
1
\$\begingroup\$

C# (Mono C# compiler), 57 56 26 bytes

Port of Rod's Python answer. Thanks to W W for -1 byte.

HUGE thanks to Kevin Cruijssen for -30 bytes.

a=>b=>a-b>b?a-b:a==b?a+1:0

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to the site! It looks like you can removed the space after return. \$\endgroup\$ – Sriotchilism O'Zaic Oct 2 '18 at 3:19
  • \$\begingroup\$ Welcome to PPCG! For non-recursive C# answers it's always best and shortest to use a lambda function (i=>{/*code here*/}). In this case however, since you have 2 inputs, it can be a currying lambda function to save an additional byte (a=>b=>{/*code here*/} instead of (a,b)=>{/*code here*/}). Also, you can remove the parenthesis around your if-checks. In total, without changing any of your functionality, it becomes a=>b=>a-b>b?a-b:a==b?a+1:0 26 bytes \$\endgroup\$ – Kevin Cruijssen Oct 3 '18 at 9:58
  • \$\begingroup\$ Also, if you haven't seen it yet, Tips for golfing in <all languages> and Tips for golfing in C# might both be interesting to read through. Enjoy your stay! :) \$\endgroup\$ – Kevin Cruijssen Oct 3 '18 at 10:00
  • \$\begingroup\$ Thank you all for the tips, I will keep these in mind when golfing in the future. \$\endgroup\$ – Epicness Oct 3 '18 at 12:02
0
\$\begingroup\$

Pyth, 16 bytes

hhx!0mqeQ%hQdShh

Try it online!

All test cases

Takes input as [a, b], errors if no solution found. Will revise if erroring isn't allowed.

\$\endgroup\$
0
\$\begingroup\$

APL (Dyalog Unicode), 19 bytes

A←{(⍳⍵+1)/⍨⍺=⍵|⍨⍳⍵+1}

Try it online!

Golfing in progress...

\$\endgroup\$
0
\$\begingroup\$

Mathematica, 28 bytes

Which[#>2#2,#-#2,#==#2,#+1]&
\$\endgroup\$
0
\$\begingroup\$

PHP>=7.1, 51 Bytes

for([,$a,$b]=$argv;++$x<2*$a;)$a%$x!=$b?:print$x._;

Online Version

\$\endgroup\$
0
\$\begingroup\$

Axiom, 147 128 bytes

g(a:PI,c:PI):Union(List PI,Stream INT)==(a<c=>[];r:=a-c;r=0=>expand((a+1..)::UniversalSegment INT);[b for b in divisors(r)|b>c])

ungolf it and test

--a%b=c return all possible b
f(a:PI,c:PI):Union(List PI, Stream INT)==
    a<c=>[]
    r:=a-c
    r=0=>expand((a+1..)::UniversalSegment INT)
    [b  for b in divisors(r)|b>c]

(3) -> [[i,j,g(i,j)] for i in [5,9,8,6,8,2,8,10] for j in [2,4,2,6,7,4,5,1]]
   (3)
   [[5,2,[3]], [9,4,[5]], [8,2,[3,6]], [6,6,[7,8,9,10,11,12,13,14,15,16,...]],
    [8,7,[]], [2,4,[]], [8,5,[]], [10,1,[3,9]]]
                                                      Type: List List Any

This would find all the solution even the infinite set solution...

\$\endgroup\$
0
\$\begingroup\$

Pip, 9 bytes

a%,a+2@?b

Takes the two numbers as command-line arguments. Outputs the smallest solution, or nil if no solution exists. Try it online!

Explanation

           a, b are cmdline args (implicit)
  ,a+2     Range from 0 up to but not including a+2
a%         Take a mod each of those numbers
           (Note that a%0 returns nil; it emits a warning, but only if warnings are turned on)
      @?b  Find the index of the first occurrence of b in this list, or nil if it doesn't occur
           Autoprint (implicit)

For example, with input of 8 and 2:

   a+2   10
  ,      [0 1 2 3 4 5 6 7 8 9]
a%       [() 0 0 2 0 3 2 1 0 8]

The 0-based index of the first occurrence of 2 in this list is 3, which is our solution.

\$\endgroup\$
0
\$\begingroup\$

J, 14 bytes

(->]){-,~=*1+]

Try it online!

Translation of Rod's Python 2 solution.

How it works

The rare cases where a J code can be directly translated into Python.

(->]){-,~=*1+]  <=>  [(a==b)*(1+b),a-b][a-b>b]
         =*1+]        (a==b)*(1+b)
      -,~            [            ,a-b]
     {                                 [     ]
(->])                                   a-b>b
\$\endgroup\$
0
\$\begingroup\$

Japt, 13 bytes

UµV ?U>V©U:ÒV

Try it online!

Translation of eush77's JS solution.

The code is just (U-=V)?U>V&&U:-~V when transpiled to JS, where U and V are the two input values.

\$\endgroup\$
0
\$\begingroup\$

Ruby, 31 bytes

->a,b{(1..a+1).find{|x|a%x==b}}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Japt, 7 bytes

(Eventually) Outputs undefined if there's no solution.

@%X¥V}a

Try it here

\$\endgroup\$
0
\$\begingroup\$

Perl 6, 23 bytes

{grep $^a%*==$^b,^$a+2}

Try it online!

Anonymous code block that returns a list of possible values from 2 up to a+1

\$\endgroup\$
0
\$\begingroup\$

ORK, 566 bytes

When this program starts:
I have a inputter called I
I have a number called a
I have a number called b
I is to read a
I is to read b
I have a mathematician called M
M's first operand is a
M's second operand is b
M is to subtract
I have a number called n
n is M's result
M's first operand is b
M's second operand is n
M is to compare
I have a scribe called W
If M says it's less then W is to write n
If M says it's less then W is to write "\n"
M's second operand is a
M is to compare
If M says it's equal then W is to write a
If M says it's equal then W is to write a

Try it online!

Objects R Kool. Luckily, however, I didn't need to use any (besides the built-in ones) for this task.

\$\endgroup\$
0
\$\begingroup\$

F#, 40 bytes

let m a b=Seq.find(fun x->a%x=b){1..a+1}

Try it online!

Pretty straight-forward. Throws a System.Collections.Generic.KeyNotFoundException if no solution can be found.

You could also modify it to Seq.tryFind, which will return an int option, with None if no solution could be found.

\$\endgroup\$
0
\$\begingroup\$

05AB1E, 7 bytes

>Lʒ¹s%Q

Try it online or verify all test cases.

Explanation:

>          # First (implicit) input + 1
 L         # Create a range [1, n]
  ʒ        # Filter; only keep elements where:
   ¹s%     #  The first input modulo this value
      Q    #  Equals the second (implicit) input
\$\endgroup\$
0
\$\begingroup\$

Java 8, 26 bytes

a->b->a-b>b?a-b:a==b?a+1:0

Port of @Epicness' C# answer, after I golfed it a bit more.

Try it online.

\$\endgroup\$
0
\$\begingroup\$

><>, 21 bytes

Same trick as most posted solutions. First, we prepare all necessary values on the stack and then check the comparisons.

::r::{-:{)?nr=?!;1+n;

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Whispers v2, 128 bytes

> Input
> Input
>> 1²
>> (3]
>> 1%L
>> L=2
>> Each 5 4
>> Each 6 7
>> L⋅R
>> Each 9 4 8
> {0}
>> {10}
>> 12∖11
>> Output 13

Try it online!

Returns a set of all possible solutions, and the empty set (i.e. \$\emptyset\$) when no solution exists.

How it works

Unsurprisingly, it works almost identically to most other answers: it generates a list of numbers and checks each one for inverse modulus with the argument.

If you're familiar with how Whispers' program structure works, feel free to skip ahead to the horizontal line. If not: essentially, Whispers works on a line-by-line reference system, starting on the final line. Each line is classed as one of two options. Either it is a nilad line, or it is a operator line.

Nilad lines start with >, such as > Input or > {0} and return the exact value represented on that line i.e > {0} returns the set \$\{0\}\$. > Input returns the next line of STDIN, evaluated if possible.

Operator lines start with >>, such as >> 1² or >> (3] and denote running an operator on one or more values. Here, the numbers used do not reference those explicit numbers, instead they reference the value on that line. For example, ² is the square command (\$n \to n^2\$), so >> 1² does not return the value \$1^2\$, instead it returns the square of line 1, which, in this case, is the first input.

Usually, operator lines only work using numbers as references, yet you may have noticed the lines >> L=2 and >> L⋅R. These two values, L and R, are used in conjunction with Each statements. Each statements work by taking two or three arguments, again as numerical references. The first argument (e.g. 5) is a reference to an operator line used a function, and the rest of the arguments are arrays. We then iterate the function over the array, where the L and R in the function represent the current element(s) in the arrays being iterated over. As an example:

Let \$A = [1, 2, 3, 4]\$, \$B = [4, 3, 2, 1]\$ and \$f(x, y) = x + y\$. Assuming we are running the following code:

> [1, 2, 3, 4]
> [4, 3, 2, 1]
>> L+R
>> Each 3 1 2

We then get a demonstration of how Each statements work. First, when working with two arrays, we zip them to form \$C = [(1, 4), (2, 3), (3, 2), (4, 1)]\$ then map \$f(x, y)\$ over each pair, forming our final array \$D = [f(1, 4), f(2, 3), f(3, 2), f(4, 1)] = [5, 5, 5, 5]\$

Try it online!


How this code works

Working counter-intuitively to how Whispers works, we start from the first two lines:

> Input
> Input

This collects our two inputs, lets say \$x\$ and \$y\$, and stores them in lines 1 and 2 respectively. We then store \$x^2\$ on line 3 and create a range \$A := [1 ... x^2]\$ on line 4. Next, we jump to the section

>> 1%L
>> L=2
>> Each 5 4
>> Each 6 7

The first thing executed here is line 7, >> Each 5 4, which iterates line 5 over line 4. This yields the array \$B := [i \: \% \: x \: | \: i \in A]\$, where \$a \: \% \: b\$ is defined as the modulus of \$a\$ and \$b\$.

We then execute line 8, >> Each 6 7, which iterates line 6 over \$B\$, yielding an array \$C := [(i \: \% \: x) = y \: | \: i \in A]\$.

For the inputs \$x = 5, y = 2\$, we have \$A = [1, 2, 3, ..., 23, 24, 25]\$, \$B = [0, 1, 2, 1, 0, 5, 5, ..., 5, 5]\$ and \$C = [0, 0, 1, 0, 0, ..., 0, 0]\$

We then jump down to

>> L⋅R
>> Each 9 4 8

which is our example of a dyadic Each statement. Here, our function is line 9 i.e >> L⋅R and our two arrays are \$A\$ and \$C\$. We multiply each element in \$A\$ with it's corresponding element in \$C\$, which yields an array, \$E\$, where each element works from the following relationship:

$$E_i = \begin{cases} 0 & C_i = 0 \\ A_i & C_i = 1 \end{cases}$$

We then end up with an array consisting of \$0\$s and the inverse moduli of \$x\$ and \$y\$. In order to remove the \$0\$s, we convert this array to a set (>> {10}), then take the set difference between this set and \$\{0\}\$, yielding, then outputting, our final result.

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

C#, 53 bytes (83 with function heading)

static int F(int a, int b){
    for(int i=1;i<=a+1;i++){if(a%i==b)return i;}return 0;
}

Try It Online

First try at codegolf. Probably not the best language to use, nor the most efficient coding.

\$\endgroup\$
  • 5
    \$\begingroup\$ Remove the unnecessary whitespace to save about 10 or more bytes \$\endgroup\$ – Mr. Xcoder May 17 '17 at 4:38

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.