태그 보관물: 오일러 프로젝트

오일러 프로젝트 26 번

오일러 프로젝트 26 번

분자가 1인 분수를 단위분수라고 합니다. 분모가 2에서 10까지의 단위분수는 아래와 같습니다.



숫자 위에 찍힌 점은 순환마디를 나타내는데, 1/6의 경우 순환마디는 "6"으로 0.166666...처럼 6이 무한히 반복됨을 뜻합니다. 같은 식으로 1/7은 6자리의 순환마디(142857)를 가집니다.

d 를 1000 이하의 정수라고 할 때, 단위분수 1/d 의 순환마디가 가장 긴 수는 무엇입니까?

http://euler.synap.co.kr/prob_detail.php?id=26

1을 분모로 나누고 그 목과 나머지의 쌍이 반복될 때까지 이를 반복한 횟수가 순환마디의 길이가 된다. 이를 이용해서 풀이.

def circ(num):
    d = 1
    divideds = []
    while 1:
        (q, r) = (d // num, d % num)
        #print q, r
        if d in divideds:
            return len(divideds[divideds.index(d):])
        else:
            divideds.append(d)
        d = r * 10


def e26():
    max = 0
    maxLength = 0
    for i in range(1, 1001):
        l = circ(i)
        if maxLength < l:
            max = i
            maxLength = l
    print(max)

%time e26()

오일러 프로젝트 25 번

오일러 프로젝트 25 번

피보나치 수열은 아래와 같은 점화식으로 정의됩니다.

Fn = Fn-1 + Fn-2  (단, F1 = 1, F2 = 1).
이에 따라 수열을 12번째 항까지 차례대로 계산하면 다음과 같습니다.

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
수열의 값은 F12에서 처음으로 3자리가 됩니다.

피보나치 수열에서 값이 처음으로 1000자리가 되는 것은 몇번째 항입니까?

http://euler.synap.co.kr/prob_detail.php?id=25

자리수는 밑을 10으로 하는 로그를 이용해서 바로 구할 수 있다. log10math 모듈에 포함되어 있다.

from math import log10

def e25():
    a, b = 0, 1
    n = 1
    while 1:
        if log10(b) >= 999:
            print(n)
            return
        a, b = b, (a+b)
        n += 1

%time e25()
#4782
#Wall time: 6 ms