I had the following scenario today on an Interview for a Developer Job, this was one of the questions, and only one I fail to answer.
Concatenate the number N N times and then calculate his Modulus by 2017.
For example: for N=5 the number will be 55555 and the result will be Mod(55555,2017) = 1096 for N=10 the number will be 10101010101010101010 and the result Mod(10101010101010101010,2017) = 1197
Now the Number I had to calculate was 58184241583791680. The only hint I got was that the result of 58184241583791680 concatenated 58184241583791680 times modulus 2017 is a 4 digit number.
I posted this question on math.stackexchange and I got a mathematical approach to this problem, other than brute force.
I wrote the following code in JAVA
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
public class Puzzle {
final static BigInteger M = new BigInteger("2017");
public static void main(String [ ] args) {
for (long n : new long[] { 1L, 2L, 5L, 10L, 20L }) {
System.out.println(n + " --> " + bruteForce(n) + " --- " + formulaV2(n));
}
}
private static BigInteger bruteForce(long n) {
String s = "";
for (long i = 0; i < n; i++) {
s = s + n;
}
return new BigInteger(s.toString()).mod(M);
}
private static BigInteger formulaV2(long n) {
String aux = String.valueOf(n);
long L = aux.length();
long K = n;
double op1 = Math.pow(10,L*K);
BigDecimal minus1 = new BigDecimal(1);
BigDecimal p1 = new BigDecimal(op1).subtract(minus1);
double op2 = Math.pow(10,L);
BigDecimal p2 = new BigDecimal(op2).subtract(minus1).pow(-1,MathContext.DECIMAL64);
BigDecimal R = new BigDecimal(n).multiply(p1).multiply(p2);
R = R.setScale(0,BigDecimal.ROUND_UP);
BigInteger ret = R.toBigInteger();
return ret.mod(M);
}
}
I'm using BigInteger and BigDecimal because I want to get the value of really big numbers (16+ digits).
The bruteForce method will simply concatenate the number inside a loop, and the formulaV2 method will use the formula from the question asked in the math forum.
bruteForce method is just for validation.
However the formula method works well for N<10 but no for N>=10. At N=10 I'm getting incorrect results.
The coding seems to be consistent (to me at least, maybe there is something I'm missing) with the formula provided, and the formula is correct (I checked in Wolfram Alpha).
My guess is that I have precision problems, maybe BigDecimal is not the proper object in this case?.
I laid this all out in the comments on https://stackoverflow.com/questions/38988665/java-puzzle-whats-the-correct-answer#comment65349106_38988665, but you can take what @Anony-Mousse and others above say and work with it.
One key is to find 10^17 mod 2017 up front. Wolfram Alpha gets that right, anyway at 599, but on other platforms you may need to look at it as ((10^9 mod 2017)(10^8 mod 2017))mod 2017 to get the 599. You also need that 58184241583791680 mod 2017 is 2005 (again Wolfram gets this right, but lesser platforms may falter if you do not break it up into something like (((581842415 mod 2017)(10^8 mod 2017) mod 2017)+83791680)mod 2017.
So at each step of the (58184241583791680 but no fear) process you are taking your current number and multiplying it by 10^17 (to move it over to make room for the concatenation) and adding 58184241583791680. But we can do this all mod 2017. In the language of sequences a sub 1 = 2005 and a sub (n+1)=((a sub n)*599+2005) mod 2017. That is the key step in your for loop. I did the first 4040 or so terms in R (got to love that you can just lay them out on screen interactively and pore over them -- the language is growing on me), though it really would have sufficed to do about half that (the good old Pigeonhole principle at work). And they do not cycle until you actually get all the way out to a sub 2017 which is 2005 again. So is a sub 4033.
In general a sub n = a sub (n mod 2016). You want a sub 58184241583791680. 58184241583791680 mod 2016 is 224 says Wolfram Alpha [again on a lesser platform you may need to break it up into (((581842415 mod 2016)*(10^8 mod 2016) mod 2016)+83791680)mod 2016], so you want a sub 224.
If people want to check themselves or me, I got on R that that was 465. But as was pointed out above, the process is what the question is really interested in.