문제 : 양의 정수 n에 대하여, 다음과 같은 계산 과정을 반복하기로 합니다.
n → n / 2 (n이 짝수일 때)
n → 3 n + 1 (n이 홀수일 때)
13에 대하여 위의 규칙을 적용해보면 아래처럼 10번의 과정을 통해 1이 됩니다.
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
아직 증명은 되지 않았지만, 이런 과정을 거치면 어떤 수로 시작해도 마지막에는 1로 끝나리라 생각됩니다.
(역주: 이것은 콜라츠 추측 Collatz Conjecture이라고 하며, 이런 수들을 우박수 hailstone sequence라 부르기도 합니다)
그러면, 백만(1,000,000) 이하의 수로 시작했을 때 1까지 도달하는데 가장 긴 과정을 거치는 숫자는 얼마입니까?
참고: 계산 과정 도중에는 숫자가 백만을 넘어가도 괜찮습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | def problem14(): cnt = 0 target = 0 for i in range(1000000, 0, -1): comp = i compCnt = 0 while comp!=1: if comp % 2== 0: comp = comp / 2 elif comp %2 ==1: comp = comp*3 +1 compCnt +=1 if compCnt > cnt: cnt = compCnt target = i print target problem14() | cs |
root@kali:/tmp# python test.py
837799
'* Computer Science > Project Euler' 카테고리의 다른 글
| project euler 16. problem (0) | 2016.07.26 |
|---|---|
| project euler 15. problem (0) | 2016.07.25 |
| project euler 13. problem (0) | 2016.07.23 |
| project euler 12. problem (0) | 2016.07.22 |
| project euler 11. problem (0) | 2016.07.21 |