We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I have found two methods for solving this. Both build upon the same principle. From previous problems we know that a repunit can be written on the form
\displaystyle R(k) = \frac{10^k - 1}{9}
We will use this in our solution. The next thing we need is to know that if we have a number k = am, where k, a and m are positive integers, then R(a) divides R(k). We can show that since we have
Then for a little trick since the first part 10^{am} can be rewritten as an expression of R(a), since we have that 10^a = 9R(a) 1 (simple rewrite of the definition of R(a). Using this we get that 10^{am} =(9R(a) 1)^m. This can be inserted into the previous equation
The upper part where we have that (9R(a) 1)^m can be expanded such that it will yield a whole lot of terms containing some power and multiplum of 9R(a) and then one term which will be a one. As an example if m = 2 we get (9R(a) 1)^2 = 9^2R(a)^2 2(9R(a)) 1. Thus if we expand the power the ones will cancel out and we can divide all the terms by 9, such that we are left with terms which contains R(a), therefore R(a) is divisible by this numbers.
What this means is that if p divides R(10^n) for some n then p also divides R(10^m) if n < m, since R(10^n) divides R(10^m) as we have just shown since we can write R(10^m) = R(10^a10^{n}) where a = m – n.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #133: Repunit nonfactors
You are viewing a single comment's thread. Return to all comments →
I have found two methods for solving this. Both build upon the same principle. From previous problems we know that a repunit can be written on the form
\displaystyle R(k) = \frac{10^k - 1}{9}
We will use this in our solution. The next thing we need is to know that if we have a number k = am, where k, a and m are positive integers, then R(a) divides R(k). We can show that since we have
\displaystyle R(a) = \frac{10^a - 1}{9}
and
\displaystyle R(k) = \frac{10^k - 1}{9} = \frac{10^{am} - 1}{9}
Therefore if we divide the two we get
\displaystyle \frac{R(am)}{R(a)} = \frac{\frac{10^{am} - 1}{9}}{R(a)}
Then for a little trick since the first part 10^{am} can be rewritten as an expression of R(a), since we have that 10^a = 9R(a) 1 (simple rewrite of the definition of R(a). Using this we get that 10^{am} =(9R(a) 1)^m. This can be inserted into the previous equation
\displaystyle \frac{\frac{(9R(a) 1)^m - 1}{9}}{R(a)}
The upper part where we have that (9R(a) 1)^m can be expanded such that it will yield a whole lot of terms containing some power and multiplum of 9R(a) and then one term which will be a one. As an example if m = 2 we get (9R(a) 1)^2 = 9^2R(a)^2 2(9R(a)) 1. Thus if we expand the power the ones will cancel out and we can divide all the terms by 9, such that we are left with terms which contains R(a), therefore R(a) is divisible by this numbers.
What this means is that if p divides R(10^n) for some n then p also divides R(10^m) if n < m, since R(10^n) divides R(10^m) as we have just shown since we can write R(10^m) = R(10^a10^{n}) where a = m – n.