일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- Navier-Stokes
- python3
- 프로그래머스
- Fluids
- heap
- Boundary Layers
- Crank-Nicolson
- Blasius
- Laminar
- 우선순위큐
- Fluid Dynamics
- Python
- 이중우선순위큐
- Heat Equation
- 프로젝트오일러
- Statistics
- programmers
- 파이썬
- Turbulent
- 힙
- 회귀
- regression
- 통계학
- FTCS
- 예제
- Compressible Flow
- 디스크 컨트롤러
- Finite Difference Method
- projecteuler
- 유체역학
- Today
- Total
Sudal's Garage
Project Euler 14 본문
Question:
The following iterative sequence is defined for the set of positive integers:
n → n/2 (n is even)
n → 3n + 1 (n is odd)Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.
문제:
다음과 같이 양의 정수에 대해 재귀적으로 정의된 수열이 있다고 하자:
n → n/2 (n이 짝수일 때)
n → 3n + 1 (n이 홀수일 때)위의 정의에 따라 13부터 시작하면 다음과 같은 수열을 얻을 수 있다:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1이 수열은 총 10개의 항으로 구성된다. (13으로 시작해서 1로 끝나는) 증명되지는 않았지만 (콜라츠 문제), 어떠한 숫자로 시작해도 1로 끝나는 것을 알 수 있다.
그렇다면 100만보다 작은 수 중 어떤 숫자로 시작해야 가장 긴 콜라츠 수열을 얻을 수 있을까?
주의: 시작하는 숫자만 100만보다 작으면 된다. 콜라츠 수열 중간에 100만 이상이 되는 것은 문제없다.
Solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | import time start = time.time() num = 5 result = [0,0] while num < 1e6: nextnum = num chain = list([num]) while chain[-1] != 1: if chain[-1] % 2 == 0: nextnum /= 2 elif chain[-1] % 2 == 1: nextnum = 3*nextnum + 1 chain.append(nextnum) if len(chain) > len(result): result = chain num += 2 print('The longest chain starts with: {}\nFound in {}s'.format(result[0],time.time() - start)) | cs |
5 부터 시작해서 홀수 항으로 시작되는 수열들만 판별했다.
걸린 시간은 35.6s
'Programming > Project Euler - python' 카테고리의 다른 글
Project Euler 16 (0) | 2019.03.04 |
---|---|
Project Euler 15 (0) | 2019.03.03 |
Project Euler 13 (0) | 2019.02.28 |
Project Euler 12 (0) | 2019.02.27 |
Project Euler 11 (0) | 2019.02.26 |