# Project Euler #133: Repunit nonfactors

# Project Euler #133: Repunit nonfactors

divya_singh05 + 1 comment what should be the value of n.. please find my login below and let me know what improvemnet can I make:

sum=0 for i in range(1,l+1): if checkPrime(i): //for checking prime number total=0 for j in range(1,6): digits=10**j repunit = (int('1'*digits))

`if repunit%i==0: total=total+1 if total==0: sum=sum+i`

print(sum)

cantonios + 0 comments There potentially is no maximum value of n. That's part of the problem.

yagya_471 + 1 comment what should be the maximum value of n??

Aditya76Asked to answer + 1 comment [deleted]NiakTheWizard + 0 comments Not sure that such a bound should be published here (and, by the way, your "bound" is too small).

julio_c_p_rocha + 1 comment Please explain me the logic about this problem.

narendrabtechcse + 0 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.

spariwan + 0 comments please explain me the logic about this problem

spariwan + 0 comments can any one please help me out regarding logic.

No more comments

Sort 5 Discussions, By:

Please Login in order to post a comment