Tuesday, April 21, 2015

Long Division for Repunit

This is about a month from last I post blog.

I have to continuously to post something about programming or mathmatics
but these days I more concentrate on solving project euler problems and spending my whole time to think about how to solve it.

I solved it about 130 problems. solving 200 problems is my first plan.

Anyway 

Today I want to post about long division.
when we use computer language we just use division or remainder (/, %) so we don't have to know about how~ this is doing
...

when solving Project euler 129 I needed to long division.
Question is Below~

A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k; for example, R(6) = 111111.
Given that n is a positive integer and GCD(n, 10) = 1, it can be shown that there always exists a value, k, for which R(k) is divisible byn, and let A(n) be the least such value of k; for example, A(7) = 6 and A(41) = 5.
The least value of n for which A(n) first exceeds ten is 17.
Find the least value of n for which A(n) first exceeds one-million.

My step

if n is 7 
A(7) ???

to use long division 
I use below 

1
2
3
4
5
6
int x = 1;
int count = 1;
while(x != 0){
   x = (x *10 + 1) % n 
   count++;
}

this function follow below if n is 7
x:1
count:1
#############
x:4
count:2
#############
x:6
count:3
#############
x:5
count:4
#############
x:2
count:5
#############
x:0
count:6
#############

this is pencil and paper long division.


No comments:

Post a Comment