(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.
3A useful simplification: we're looking for the smallest
x
in absolute value where10*x-1
is divisible by the input. – xnor – 2017-08-19T20:31:16.833Can anybody provide a hint why
(3 / (n % 5 * 2 - 5) * n + 1) / 10
and(n % 5 * 2 - 5^2) * n / 10 + 1
are able to find a minimal absolute value for something like this? My first intuition would have been to calculate the least common multiple using the greatest common divisor calculated with Euclid's algorithm. – David Foerster – 2017-08-20T14:56:53.8071@DavidFoerster Given a number, you can remove the last digit, multiply it by a number
x
, add it on, and still get a number divisible byn
. If we then multiply the new number by 10 and subtract the original number it still remains divisible byn
. xnor's comment then follows from some algebra. The next step is to rearrange the formula so that it givesx
in terms ofn
: x =(k*n+1)/10
. We want the smallest absolutex
so therefore we want the smallest absolutek
, and this must be whichever one of-3
,-1
,1
or3
(depending onn
's last digit) that makes the division exact. – Neil – 2017-08-26T23:29:16.013