Project Euler 26

Question: 

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2	=	0.5
1/3	=	0.(3)
1/4	=	0.25
1/5	=	0.2
1/6	=	0.1(6)
1/7	=	0.(142857)
1/8	=	0.125
1/9	=	0.(1)
1/10	=	0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that ¹/₇ has a 6-digit recurring cycle.

Find the value of d < 1000 for which ¹/_d contains the longest recurring cycle in its decimal fraction part.

문제:

위 분수는 분자가 1이고 분모는 양의 정수인 분수이다. 분모가 2부터 10까지인 단위 분수를 나열하면 다음과 같다.

1/2	=	0.5
1/3	=	0.(3)
1/4	=	0.25
1/5	=	0.2
1/6	=	0.1(6)
1/7	=	0.(142857)
1/8	=	0.125
1/9	=	0.(1)
1/10	=	0.1

0.1(6) 은 0.166666...을 의미한다. 괄호안에 순환마디를 나타내는데, 순환마디란 순환소수에서 일정하게 되풀이 되는 한 부분을 말한다. ¹/₇ 은 순환마디의 길이가 6인 순환소수이다.

d < 1000 인 양의 정수 d 중 ¹/_d 의 순환마디가 가장 긴 것을 구하여라.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

from sympy import primerange import time longest = 0 longest_d = 0 start = time.time() for d in primerange(11,1000): cycle = False remainder = list() num_cycle = 0 nominator = 10 remainder.append(nominator // d) while not cycle: nominator = (nominator - d * remainder[-1])*10 remainder.append(nominator // d) if len(remainder) >= 3: for n in range(len(remainder)): if remainder[0:n] == remainder[n:]: cycle = True if int(len(remainder) / 2) > longest: longest = int(len(remainder) / 2) longest_d = d break elif len(remainder) == 2: if remainder[0] == remainder[1]: cycle = True if int(len(remainder) / 2) > longest: longest = int(len(remainder) / 2) longest_d = d break print('The longest cycle with: {}\nFound in {}s'.format(longest_d,time.time() - start))

첫번째로 작성했던 코드

먼저, 소수 (prime number) 를 역수 취했을 때에 순환소수가 됨으로, 소수들만 판별하기로 했다.

실제 나눗셈을 하는 것 처럼, 10부터 차례차례 나눠나가는 방식을 사용하고,

list에 나머지들을 저장해 넣었다. 후에, 일일이 slice 를 이용해 반복되는 문구가 있다면

cycle = True로 설정해 순환됨을 확인하고, 길이를 비교해넣었다.

하지만 숫자 하나당 list 가 너무 길어지고 slice하는 횟수도 많아져서 시간이 너무 오래 걸린다.

위 코드는 3분 정도 걸린다 ...

elif len(remainder) == 2:

이 라인은 1/3 = 0.3333... 과 1/101 = 0.00990099... 같은 차이를 구분하기 위해 넣었다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

from itertools import count from sympy import primerange import time longest = 0 longest_d = 0 start = time.time() for d in primerange(1,1000): r = 10 remainder = dict() for i in count(0): if r == 0: #무한소수가 아님 break elif r in remainder: if longest < i: longest = i longest_d = d break break remainder[r] = i r = 10 * (r % d) print('''The longest length of cycle: {0} The number has the longest cycle: {1} Found in ...{2:.2f}s'''.format(longest,longest_d,time.time() - start))

두번째로 작성한 코드.

itertools 안의 count 메소드를 이용했다.

방식은 비슷하지만, 나눈 나머지의 10배(r)를 dictionary에 저장한다.

만약 같은 r이 dictionary에 있다면 dictionary의 길이를 판별한다.

복잡한 과정없이 1/3 = 0.333... 1/101 = 0.00990099... 같은 케이스를 한 번에 구별할 수 있다.

0.02s 걸렸다! 9000배 빨라졌다!!

The longest length of cycle: 982

The number has the longest cycle: 983

Found in ...0.02s