How to approach and understand a math related DSA question

Question

I found this question online and I really have no idea what the question is even asking. I would really appreciate some help in first understanding the question, and a solution if possible. Thanks!

To see if a number is divisible by 3, you need to add up the digits of its decimal notation, and check if the sum is divisible by 3. To see if a number is divisible by 11, you need to split its decimal notation into pairs of digits (starting from the right end), add up corresponding numbers and check if the sum is divisible by 11.

For any prime p (except for 2 and 5) there exists an integer r such that a similar divisibility test exists: to check if a number is divisible by p, you need to split its decimal notation into r-tuples of digits (starting from the right end), add up these r-tuples and check whether their sum is divisible by p.

Given a prime int p, find the minimal r for which such divisibility test is valid and output it.

The input consists of a single integer p - a prime between 3 and 999983, inclusive, not equal to 5.

Example

input

3

output

1

input

11

output

2

Answer 1

Thank you andrey tyukin.

Simple terms to remember:

1. When x%y =z then (x%y)%y again =z

2. (X+y)%z == (x%z + y%z)%z keep this in mind.

So you break any number into some r digits at a time together. I.e. break 3456733 when r=6 into 3 * 10 power(6 * 1) + 446733 * 10 power(6 * 0).

And you can break 12536382626373 into 12 * 10 power (6 * 2). + 536382 * 10 power (6 * 1) + 626373 * 10 power (6 * 0)

Observe that here r is 6.

So when we say we combine the r digits and sum them together and apply modulo. We are saying we apply modulo to coefficients of above breakdown.

So how come coefficients sum represents whole number’s sum?

When the “10 power (6* anything)” modulo in the above break down becomes 1 then that particular term’s modulo will be equal to the coefficient’s modulo. That means the 10 power (r* anything) is of no effect. You can check why it will have no effect by using the formulas 1&2.

And the other similar terms 10 power (r * anything) also will have modulo as 1. I.e. if you can prove that (10 power r)modulo is 1. Then (10 power r * anything) is also 1.

But the important thing is we should have 10 power (r) equal to 1. Then every 10 power (r * anything) is 1 that leads to modulo of number equal to sum of r digits divided modulo.

Conclusion: find r in (10 power r) such that the given prime number will leave 1 as reminder.

That also mean the smallest 9…..9 which is divisible by given prime number decides r.

Answer 2

This is an almost direct application of Fermat's little theorem.

First, you have to reformulate the "split decimal notation into tuples [...]"-condition into something you can work with:

to check if a number is divisible by p, you need to split its decimal notation into r-tuples of digits (starting from the right end), add up these r-tuples and check whether their sum is divisible by p

When you translate it from prose into a formula, what it essentially says is that you want

for any choice of "r-tuples of digits" b_i from { 0, ..., 10^r - 1 } (with only finitely many b_i being non-zero).

Taking b_1 = 1 and all other b_i = 0, it's easy to see that it is necessary that

It's even easier to see that this is also sufficient (all 10^ri on the left hand side simply transform into factor 1 that does nothing).

Now, if p is neither 2 nor 5, then 10 will not be divisible by p, so that Fermat's little theorem guarantees us that

, that is, at least the solution r = p - 1 exists. This might not be the smallest such r though, and computing the smallest one is hard if you don't have a quantum computer handy.

Despite it being hard in general, for very small p, you can simply use an algorithm that is linear in p (you simply look at the sequence

10    mod p 
100   mod p
1000  mod p
10000 mod p
...

and stop as soon as you find something that equals 1 mod p).

Written out as code, for example, in Scala:

def blockSize(p: Int, n: Int = 10, r: Int = 1): Int =
  if n % p == 1 then r else blockSize(p, n * 10 % p, r + 1)

println(blockSize(3))  // 1
println(blockSize(11)) // 2
println(blockSize(19)) // 18

or in Python:

def blockSize(p: int, n: int = 10, r: int = 1) -> int:
  return r if n % p == 1 else blockSize(p, n * 10 % p, r + 1)

print(blockSize(3))  # 1
print(blockSize(11)) # 2
print(blockSize(19)) # 18

A wall of numbers, just in case someone else wants to sanity-check alternative approaches:

11 -> 2
13 -> 6
17 -> 16
19 -> 18
23 -> 22
29 -> 28
31 -> 15
37 -> 3
41 -> 5
43 -> 21
47 -> 46
53 -> 13
59 -> 58
61 -> 60
67 -> 33
71 -> 35
73 -> 8
79 -> 13
83 -> 41
89 -> 44
97 -> 96
101 -> 4
103 -> 34
107 -> 53
109 -> 108
113 -> 112
127 -> 42
131 -> 130
137 -> 8
139 -> 46
149 -> 148
151 -> 75
157 -> 78
163 -> 81
167 -> 166
173 -> 43
179 -> 178
181 -> 180
191 -> 95
193 -> 192
197 -> 98
199 -> 99

Answer 3

I have no idea how they expect a random programmer with no background to figure out the answer from this.

But here is the brief introduction to modulo arithmetic that should make this doable.

In programming, n % k is the modulo operator. It refers to taking the remainder of n / k. It satisfies the following two important properties:

(n + m) % k = ((n % k) + (m % k)) % k
(n * m) % k = ((n % k) * (m % k)) % k

Because of this, for any k we can think of all numbers with the same remainder as somehow being the same. The result is something called "the integers modulo k". And it satisfies most of the rules of algebra that you're used to. You have the associative property, the commutative property, distributive law, addition by 0, and multiplication by 1.

However if k is a composite number like 10, you have the unfortunate fact that 2 * 5 = 10 which means that modulo 10, 2 * 5 = 0. That's kind of a problem for division.

BUT if k = p, a prime, then things become massively easier. If (a*m) % p = (b*m) % p then ((a-b) * m) % p = 0 so (a-b) * m is divisible by p. And therefore either (a-b) or m is divisible by p.

For any non-zero remainder m, let's look at the sequence m % p, m^2 % p, m^3 % p, .... This sequence is infinitely long and can only take on p values. So we must have a repeat where, a < b and m^a % p = m^b %p. So (1 * m^a) % p = (m^(b-a) * m^a) % p. Since m doesn't divide p, m^a doesn't either, and therefore m^(b-a) % p = 1. Furthermore m^(b-a-1) % p acts just like m^(-1) = 1/m. (If you take enough math, you'll find that the non-zero remainders under multiplication is a finite group, and all the remainders forms a field. But let's ignore that.)

(I'm going to drop the % p everywhere. Just assume it is there in any calculation.)

Now let's let a be the smallest positive number such that m^a = 1. Then 1, m, m^2, ..., m^(a-1) forms a cycle of length a. For any n in 1, ..., p-1 we can form a cycle (possibly the same, possibly different) n, n*m, n*m^2, ..., n*m^(a-1). It can be shown that these cycles partition 1, 2, ..., p-1 where every number is in a cycle, and each cycle has length a. THEREFORE, a divides p-1. As a side note, since a divides p-1, we easily get Fermat's little theorem that m^(p-1) has remainder 1 and therefore m^p = m.

OK, enough theory. Now to your problem. Suppose we have a base b = 10^i. The primality test that they are discussing is that a_0 + a_1 * b + a_2 * b^2 + a_k * b^k is divisible by a prime p if and only if a_0 + a_1 + ... + a_k is divisible by p. Looking at (p-1) + b, this can only happen if b % p is 1. And if b % p is 1, then in modulo arithmetic b to any power is 1, and the test works.

So we're looking for the smallest i such that 10^i % p is 1. From what I showed above, i always exists, and divides p-1. So you just need to factor p-1, and try 10 to each power until you find the smallest i that works.

Note that you should % p at every step you can to keep those powers from getting too big. And with repeated squaring you can speed up the calculation. So, for example, calculating 10^20 % p could be done by calculating each of the following in turn.

10 % p
10^2 % p
10^4 % p
10^5 % p
10^10 % p
10^20 % p

Answer 4

This is a very cool problem! It uses modular arithmetic and some basic number theory to devise the solution.

Let's say we have p = 11. What divisibility rule applies here? How many digits at once do we need to take, to have a divisibility rule?

Well, let's try a single digit at a time. That would mean, that if we have 121 and we sum its digits 1 + 2 + 1, then we get 4. However we see, that although 121 is divisible by 11, 4 isn't and so the rule doesn't work.

What if we take two digits at a time? With 121 we get 1 + 21 = 22. We see that 22 IS divisible by 11, so the rule might work here. And in fact, it does. For p = 11, we have r = 2.

This requires a bit of intuition which I am unable to convey in text (I really have tried) but it can be proven that for a given prime p other than 2 and 5, the divisibility rule works for tuples of digits of length r if and only if the number 99...9 (with r nines) is divisible by p. And indeed, for p = 3 we have 9 % 3 = 0, while for p = 11 we have 9 % 11 = 9 (this is bad) and 99 % 11 = 0 (this is what we want).

If we want to find such an r, we start with r = 1. We check if 9 is divisible by p. If it is, then we found the r. Otherwise, we go further and we check if 99 is divisible by p. If it is, then we return r = 2. Then, we check if 999 is divisible by p and if so, return r = 3 and so on. However, the 99...9 numbers can get very large. Thankfully, to check divisibility by p we only need to store the remainder modulo p, which we know is small (at least smaller than 999983). So the code in C++ would look something like this:

int r(int p) {
  int result = 1;
  int remainder = 9 % p;
  while (remainder != 0) {
    remainder = (remainder * 10 + 9) % p;
    result++;
  }
  return result;
}