Get the modulus of a Number N concatenated N times.

Question

I don't know if this is the right forum.

Is there a Mathematical approach to get the Modulus of a Number N which is concatenated N times?

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.

My question is: Can we reduce somehow this number or the only solution is to concatenate it 58184241583791680 times?.

Python? C++? Anyway, my first though was that maybe 58184241583791680 is a multiple of 2017, but when I put it to Wolfram Alpha, I didn't see 2017 in the list of prime factors. — Robert Soupe, Aug 21 '16 at 15:56

Asinomás · Accepted Answer · 2016-08-21T20:17:33.250

3

The concatenation of $K$ copies of $N$ is equal to:

$\sum\limits_{i=0}^{K-1}(10^{L\times i}N)$ where $L$ is the number of digits in $N$. This is because every copy can be thought of as adding $N$ with some zeros to the right.

We can rewrite this as: $N\times \sum\limits_{i=0}^{k-1}10^{L\times i}=N\times(10^{L\times K}-1)\times (10^L-1)^{-1}\equiv N\times(10^{L\times K}-1)\times(10^L-1)^{MOD-2}$ (given that the $MOD$ is prime, which is the case for $2017$)

complexity: $\mathcal O(\log(L)+\log(K)+\log(MOD))$

edited Aug 21 '16 at 20:17

answered Aug 20 '16 at 02:14

Asinomás

105,651

Hi. I tried the formula you posted, but it seems that only works when N<10. For N>=10 I'm getting incorrect results. – Orejano Aug 21 '16 at 14:25
you probably have overflows, you need to code it carefully – Asinomás Aug 21 '16 at 15:54
Actually I tried for the following range [5..10] wich I can also calculate "by hand" in Excel. Got the same results for 5,6,7,8 and 9. For 10, the correct value is 1197 and I'm getting 1032. Haven't tried larger numbers yet, I coded in JAVA. – Orejano Aug 21 '16 at 17:19
what is your value of K? – Asinomás Aug 21 '16 at 17:29
same as N, for N=10, K=10. – Orejano Aug 21 '16 at 17:37
Are you taking into account that $L=2$ when $N=10$ ? – Asinomás Aug 21 '16 at 17:41
wolframalpha gives me the correct answer when I plug in my formula – Asinomás Aug 21 '16 at 17:42

Get the modulus of a Number N concatenated N times.

1 Answers1