Divisible by 1000003? Easy, just multiply the last digit by 300001 and add!

Question

Given a prime P greater than 10, your program or function must figure out its divisibility rule x, defined as the integer with smallest absolute value which yields a multiple of the original prime when multiplied by the last digit of the prime and added to the rest of the original prime.

Example

Given an input 31, the last digit is 1 and the rest of the number is 3. Thus your program must find the integer x with minimum absolute value such that 1*x + 3 is a multiple of 31. In this case, x=-3 works, so the program or function would return -3.

Given an input 1000003, the last digit is 3 and the rest of the number is 100000. Thus your program would find x=300001 because 3*300001+100000 = 1000003 which is a multiple of 1000003.

Mathematical Background

The value of x can be used as a divisibility test. If a number N is divisible by P, then adding x times the last digit of N to the rest of N will yield a multiple of P if and only if N is divisible by P in the first place.

For P=11, we get x=-1, which is equivalent to the well-known divisibility rule for 11: a number is divisible by 11 alternating difference of its digits is divisible by 11.

Rules

• The output may be in any form that clearly encodes both the sign and value of the output.
• The input prime will be between 10 and 2^30.
• You do not need to handle if the input is not a prime or is not in the range.
• You do not need to handle if both x and -x are valid outputs (should not happen).
• Brute force is permitted, but more creative solutions are appreciated.
• This is code-golf, so shortest code in each language wins! Do not let answers in golfing languages discourage you from posting in other languages.

Test Cases

Input   Output
11  -1
13  4
17  -5
19  2
23  7
29  3
31  -3
37  -11
41  -4
43  13
47  -14
53  16
59  6
61  -6
67  -20
71  -7
73  22
79  8
83  25
89  9
97  -29
101 -10
103 31
107 -32
109 11
113 34
127 -38
131 -13
1000003 300001
2000003 600001
2999999 300000
9999991 -999999

Answer 1

JavaScript (ES6), 32 25 23 bytes

f=
n=>(3/(n%5*2-5)*n+1)/10

<input type=number min=1 oninput=o.textContent=this.value%5*(this.value%2)?f(this.value):``><pre id=o>

3/(n%5*2-5) would be written 9/n(mod -10) if I had access to balanced modulo division. Edit: Saved 2 bytes thanks to @EgorSkriptunoff

Answer 2

Python 2, 27 bytes

lambda n:(n%5*2-5^2)*n/10+1

Try it online!

The operations are done left to right: (((n%5)*2)-5)^2.

I used my arithmetic brute forcer to find the expression n%5*2-5^2 to perform {1:-1,3:3,2:-3,4:1}[k], taking the negative inverse of a residue mod 5 into the range [-2..2].

Answer 3

Jelly, 10 8 bytes

,N⁵æiAÞḢ

Try it online!

Explanations

,N       Get [Input, -Input].
⁵æi      Modular inverse of 10 mod each of [Input, -Input].
AÞ       Sort by absolute value.
Ḣ        First.

Answer 4

Brachylog, 14 bytes

∧.ℤ≜×₁₀-₁;?%0∧

Try it online!

Answer 5

Japt, 16 9 bytes

Saved way too many bytes thanks to an observation by @xnor

_*AÉ vU}c

Test it online! May take a couple of seconds on larger inputs.

Explanation

_  *AÉ  vU}c    Implicit: U = input integer
Z{Z*A-1 vU}c    Ungolfed
Z{        }c    Loop through each integer Z in [0, -1, 1, -2, ...] and yield the first where
  Z*A             Z times 10
     -1           minus 1
        vU        is divisible by the input.
                Implicit: output result of last expression

Answer 6

Python 2, 69 54 53 bytes

Edit: -15 bytes thanks to @Mr.Xcoder

Edit: -1 byte by using recursion

f=lambda a,x=-1:(a%10*x+a/10)%a and f(a,-x-(x>0))or x

Try it online!

Answer 7

Python 2, 31 29 27 bytes

lambda n:3/(n%5*2-5)*n/10+1

Try it online!

Answer 8

Java 8, 23 21 bytes

n->3/(n%5*2-5)*++n/10

Port of @Neil's JavaScrip (ES6) answer, but -2 bytes thanks to @Nevay due to implicit flooring of integers.

Try it here.

Answer 9

Japt, 14 bytes

Inspired by Neil's solution.

Ì*2%E-3 *UÄ /A

Test it online!

Explanation:

  Ì  *2%E-3 *UÄ  /A
((UgJ*2%E-3)*U+1)/A
  U                  // Implicit U = Input
   gJ                // Get the char at index -1 (last char)
     *2              // Multiply by 2
       %E            // Mod 14
         -3          // Minus 3
            *U+1     // Multiply by U+1
                 /A  // Divided by 10 

Answer 10

Pyke, 12 bytes

3Q5%}5-f*hTf

Try it here!

Answer 11

Pyth, 14 bytes

h/*x-y%QK5K2QT

Try it here.

Answer 12

Python 2, 44 43 bytes

(Crossed out 44 is still 44.) Thanks to Fireflame241 for saving a byte!

P=input();i=P/3
while i*10%P-1:i-=1
print i

Try it online!

There is exactly one number between 0 and P-1 which is an inverse of 10. But if that inverse u happens to be greater than P/2, then (u-P) is also an inverse, and has a smaller absolute value than u. So it turns out that we're really looking for the unique number x between -P/2 and P/2 which is an inverse of 10.

The code above does exactly that, starting at (the floor of) P/2, and stepping downward until an inverse is reached. This must happen for some number greater than -P/2 so long as P is a prime greater than 10. More precisely, it will terminate if and only if P is coprime to 10.

Edit: It actually turns out that x is guaranteed to be between -P/3 and P/3, so the current version starts at P/3 and steps down from there. See the section labeled Improved Bound for an explanation of this.

Mathematical explanation

It was not immediately obvious to me why the divisibility test worked. Here's an explanation, in case anyone else was wondering.

Let P be a prime, greater than 10, whose last digit is b. Thus

P = 10a + b

where a > 0, and 0 <= b < 10. In fact b is either 1, 3, 7, or 9, because a prime greater than 10 must end in one of these digits.

Now suppose bx + a = 0 (mod P). Then

a = -bx (mod P)

10a + b = 10(-bx) + b (mod P)

0 = 10(-bx) + b (mod P)

0 = b(1 - 10x) (mod P)

Since P is prime, the integers mod P are an integral domain. So either b = 0 (mod P), or 1 - 10x = 0 (mod P).

We know 0 <= b < 10 < P, so if b = 0 (mod P) then b = 0. But we said b is either 1, 3, 7, or 9, so this is impossible. Therefore 1 - 10x = 0 (mod P), so 10x = 1 (mod P). In other words, x is the inverse of 10, modulo P.

Now suppose N is a nonnegative integer whose last digit is d, so N = 10c + d. We have a chain of equivalent statements:

10c + d = 0 (mod P)

<==> 10xc + dx = 0 (mod P)

<==> c + dx = 0 (mod P)

QED.

Usefulness?

I was also wondering whether the divisibility test (given N = 10c + d, replace N by dx + c) would actually be productive in practice. Or at least, does it reliably replace N by a number smaller than N (in absolute value)?

Suppose N = 10c + d, where c >= 0 and 0 <= d < 10. Therefore 10c = N - d <= N. By the triangle inequality,

|c + dx| <= |c| + |dx| = c + d|x| <= N/10 + d|x|

< N/10 + 10|x| <= N/10 + 10P/2 = N/10 + 5P

Thus if 5P <= 9N/10, then |c + dx| < N.

In particular, if N >= 6P, then |c + dx| < N. Thus, given P we begin by calculating 2P, 3P, ..., 6P, along with x. Then given N, we run the divisibility test repeatedly until we reach a number less than or equal to 6P, and check whether the result is any of the numbers 0, P, 2P, ..., 6P.

(Of course, whenever we reach a negative number, we replace it by its absolute value, which is fine since q is divisible by P if and only if (-q) is.)

Improved Bound

I noticed that |x|/P never seemed to be close to 1/2. In fact it seemed like it was always less than 1/3...or upon closer examination, it was always very close to either 1/10 or 3/10. The biggest it ever got seemed to be 4/13 (which happens when P=13 and x=4). Why would this be?

Let u be an integer and suppose that 10u = kP + 1 for some integer k, so u is an inverse of 10, modulo P. Then we also know that k is relatively prime to 10, since k(-P) is equivalent to 1 modulo 10.

Now, we know that the inverses of 10 modulo P all differ by multiples of P, so we can take the integer u and either add or subtract multiples of P at will, and the result will always still be an inverse of 10 modulo P. Suppose we choose to subtract P from u: we get

10(u - P) = 10u - 10P = kP + 1 - 10P

10(u - P) = (k - 10)P + 1

In other words, decreasing (respectively, increasing) u by P corresponds to decreasing (increasing) k by 10. We wish to add/subtract multiples of P from u until the left-hand side is minimized in absolute value; but the left-hand side is minimized exactly when the right-hand side is minimized, and so we want to add/subtract 10 from k until the right-hand side is minimized in absolute value.

But we know that this will happen when k is between -5 and 5, and therefore (since k is relatively prime to 10) this means k is either -3, -1, 1, or 3. (This is the content of @Neil's comment under the OP. Thanks, Neil!)

Thus when |u| is minimized (i.e., u=x), we'll have x/P = u/P = k/10 + 1/(10P), where k is either -3, -1, 1, or 3. Therefore |x|/P <= 3/10 + 1/(10P). Equivalently, |x| <= (3P + 1)/10.

Further, this inequality is strict at P=11, because at P=11 we have x=-1 and k=-1. The smallest P for which equality holds is P=13 (where x=4 and k=3).

Therefore the largest that |x|/P ever gets is 3/10 + 1/(10*13), because P=13 is the first prime for which we have k=3, and among those with k=3, the 1/(10P) term is largest when P is smallest (i.e., at P=13). Therefore, for all P, we also have |x|/P <= 3/10 + 1/130 = 4/13 < 1/3. This explains why in the above code we can initialize at i = P/3 rather than having to start at P/2.

Further, the bounds in the Usefulness section above can now be improved.

Lemma: Let N = 10c + d where c > 0 and 0 <= d <= 9. Then c + d|x| < N/10 + 9(3P + 1)/10. (Note the strict inequality.)

Proof of Lemma: by cases. Case I: d = 0, so N = 10c. Then c + d|x| = c = N/10 < N/10 + 9(3P + 1)/10.

Case II: 0 < d <= 9. Then 10c = N - d < N, so c < N/10. Therefore c + d|x| < N/10 + d|x| <= N/10 + 9|x| <= N/10 + 9(3P + 1)/10. QED.

Thus, if N > 3P (and N = 10c + d as before), then

3P + 1 <= N

9(3P + 1)/10 <= 9N/10

N/10 + 9(3P + 1)/10 <= N

c + d|x| < N/10 + 9(3P + 1)/10 <= N

So, if N > 3P then c + d|x| < N.

Therefore, we only have to find P, 2P and 3P, along with x. Given N > 0, while N > 3P, we replace N by |c + dx|, which decreases N. Eventually we'll get N <= 3P; at that point we stop and check whether N is equal to any of the numbers 0, P, 2P, or 3P.

We can't do better than 3P in general. For example suppose P = 13 and N = 39, so x = 4. Then replacing N by dx + c = 9(4) + 3 leaves N unchanged.

Answer 13

Whitespace, 92 bytes

Note that this language's syntax consists of only whitespace, so each whitespace character has been prefixed here with S, T, or L (corresponding to Space, Tab, and Linefeed, respectively). These can be removed without losing functionality, but they are included here in order to display it correctly.

S S S L
T   L
T   T   S S S L
T   T   T   S L
S S S S T   T   L
T   S S L
S L
T   S S S T S T L
T   S T T   S L
S T S S S S S S T   S T L
T   S S T   T   S T S S S S T   L
T   S S S S S S T   S T S L
T   S T S T L
S T L
L
L
.

Try it online!

Answer 14

Pyke, 10 bytes

~IIT*tR%)h

Try it here!

~I         -   Integers
  I     )  -  filter(^, not v)
   T*t     -    ^ *10 -1
      R%   -   input % ^
         h - ^[0]

Answer 15

Excel, 27 bytes

=0.3/(MOD(A1,5)*2-5)*A1+0.1

Could be entered into Cell as

=.3/(MOD(A1,5)*2-5)*A1+.1

for 25 bytes, but Excel auto-updates.