Skip to content

Instantly share code, notes, and snippets.

@sooop

sooop/e041.py

Last active January 13, 2016 01:41
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save sooop/ae813cc3f8dc75e95fa8 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save sooop/ae813cc3f8dc75e95fa8 to your computer and use it in GitHub Desktop.
Download ZIP
Project Euler on Python(3) #004 (041~050)
Raw
e041.py
"""1부터 n까지의 숫자를 하나씩만 써서 만든 n자리 숫자를 팬디지털(pandigital)이라고 부릅니다.
2143은 4자리 팬디지털인데, 이 수는 동시에 소수이기도 합니다.
n자리 팬디지털 소수 중에서 가장 큰 수는 무엇입니까?"""
"""
9자리 펜디지털 수의 각 자리숫자 합은 45로 소수가 될 수 없다.
같은 원리로 8자리는 불가능.
따라서 답은 7자리 중에 나오게 되어 있으므로
7654321의 순열로부터 소수인지 검사한다.
역순으로 검사하여 가장 먼저 나오는 케이스가 답이 된다."""
from functools import reduce
def is_prime(n):
if n < 2:
return False
if n is 2 or n is 3:
return True
if n %2 == 0 or n % 3 == 0:
return False
if n < 9:
return True
k = 5
l = n ** 0.5
while k <= l:
if n % k == 0 or n % (k+2) == 0:
return False
k += 6
return True
def factorial(n):
if n < 2:
return 1
return reduce(lambda x,y: x*y, range(1, n+1), 1)
def perms(n, ls):
if n is 0:
return ls
l = len(ls)
n = n % factorial(l)
q, r = divmod(n, factorial(l-1))
return [ls[q]] + perms(r, ls[:q] + ls[q+1:])
def list_to_int(ls):
return reduce(lambda x,y: x*10 + y, ls, 0)
def e41():
a = [7,6,5,4,3,2,1]
l = factorial(7)
s = []
for i in range(l, 0, -1):
n = list_to_int(perms(i, a))
if is_prime(n):
print(n)
return
%time e41()
#7652413
#Wall time: 0 ns
Raw
e042.py
"""n번째 삼각수는 tn = ½ n (n + 1) 이라는 식으로 구할 수 있는데, 처음 10개는 아래와 같습니다.
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
어떤 영어 단어에 대해서, 각 철자의 알파벳 순서(A=1, B=2, ..., Z=26)를 모두 더한 값을 '단어값'이라 부르기로 합니다. 예를 들어 'SKY'의 단어값은 19 + 11 + 25 = 55가 되는데, 이것은 우연히도 t10과 같습니다.
이렇게 어떤 단어의 단어값이 삼각수일 경우에는 이 단어를 '삼각단어'라 부르기로 합니다.
약 16KB의 텍스트 파일 words.txt에는 2000개 정도의 영어 단어가 수록되어 있습니다. 이 중에서 삼각단어는 모두 몇 개입니까?"""
"""
삼각수 k = n(n-1)/2
이므로 (sqrt(2k) + 1) / 2 이 자연수인지 검사하는 방법도 있는데,
영단어 자체가 60자를 넘기 힘드므로,
60개 삼각수를 구해서 검사하는것도 방법이다.
"""
from urllib.request import urlopen
def e42():
def tri(n):
return n*(n+1)//2
def word_point(w):
nonlocal tris
p = sum((ord(x) - ord('A') + 1 for x in w))
return p in tris
tris = set([tri(x) for x in range(1, 100)])
s = urlopen("http://euler.synap.co.kr/files/words.txt").read().decode('utf-8')
words = list(map(lambda x:x.strip('"'), s.split(',')))
print(len(list(filter(word_point, words))))
%time e42()
#162
#Wall time: 57 ms
Raw
e043.py
"""숫자 1406357289은 0 ~ 9 팬디지털인데, 부분열에 관련된 재미있는 성질을 가지고 있습니다.
d1을 첫째 자리수, d2를 둘째 자리수...라고 했을 때, 다음과 같은 사실을 발견할 수 있습니다.
d2 d3 d4 = 406 → 2로 나누어 떨어짐
d3 d4 d5 = 063 → 3으로 나누어 떨어짐
d4 d5 d6 = 635 → 5로 나누어 떨어짐
d5 d6 d7 = 357 → 7로 나누어 떨어짐
d6 d7 d8 = 572 → 11로 나누어 떨어짐
d7 d8 d9 = 728 → 13으로 나누어 떨어짐
d8 d9 d10 = 289 → 17로 나누어 떨어짐
위와 같은 성질을 갖는 0 ~ 9 팬디지털을 모두 찾아서 그 합을 구하면 얼마입니까?"""
"""
모든 0-9 팬디지털 숫자에 대해서 검사하는 경우라하더라도 10!만큼 루프를 돌려야 하기 때문에
연산량이 상당히 많아진다.
결국 앞의 조건을 만족하지 않으면 뒤쪽 순열을 체크하지 않도록 해야 하고
이를 위해서는 반복해서 for, if를 네스팅해야하는데
이는 파이썬에서 예쁜 코드가 안된다.
따라서 list comprehension에서 for, if를 번갈아 쓰면서
조건을 정리해준다.
"""
from functools import reduce
def ls_to_int(*xs):
return reduce(lambda x, y: x*10 + y, xs, 0)
def e43():
r = []
for d1 in set(range(10)):
for d2 in set(range(10)) - {d1}:
for d3 in set(range(10)) - {d1, d2}:
for d4 in set(range(10)) - {d1, d2, d3}:
if (d2*100 + d3*10 + d4) % 2 == 0:
for d5 in set(range(10)) - {d1, d2, d3, d4}:
if (d3*100 + d4*10 + d5) % 3 == 0:
for d6 in set(range(10)) - {d1, d2, d3, d4, d5}:
if (d4*100 + d5*10 + d6) % 5 == 0:
for d7 in set(range(10)) - {d1, d2, d3, d4, d5, d6}:
if (d5*100 + d6*10 + d7) % 7 == 0:
for d8 in set(range(10)) - {d1, d2, d3, d4, d5, d6, d7}:
if (d6*100 + d7*10 + d8) % 11 == 0:
for d9 in set(range(10)) - {d1, d2, d3, d4, d5, d6, d7, d8}:
if (d7*100 + d8*10 + d9) % 13 == 0:
for d10 in set(range(10)) - {d1, d2, d3, d4, d5, d6, d7, d8, d9}:
if (d8*100+d9*10+d10) % 17 == 0:
r.append(ls_to_int(d1, d2, d3, d4, d5, d6, d7, d8, d9, d10))
print(sum(r))
# 성능은 동일하나 조금 더 깔끔(?)하게 작성한 코드
from functools import reduce
def check(x,y,z,a):
return (x*100+10*y+z) % a == 0
def ls_to_int(ls):
return reduce(lambda x,y:x*10+y, ls, 0)
def e43():
r = [[d1, d2, d3, d4, d5, d6, d7, d8, d9, d10]\
for d1 in range(1,10)\
for d2 in range(10)\
if d2 != d1\
for d3 in range(10)\
if d3 not in (d1, d2)\
for d4 in range(10)\
if d4 not in (d1, d2, d3)\
if check(d2, d3, d4, 2)\
for d5 in range(10)\
if d5 not in (d1, d2, d3, d4)\
if check(d3, d4, d5, 3)\
for d6 in range(10)\
if d6 not in (d1, d2, d3, d4, d5)\
if check(d4, d5, d6, 5)\
for d7 in range(10)\
if d7 not in (d1, d2, d3, d4, d5, d6)\
if check(d5, d6, d7, 7)\
for d8 in range(10)\
if d8 not in (d1, d2, d3, d4, d5, d6, d7)\
if check(d6, d7, d8, 11)\
for d9 in range(10)\
if d9 not in (d1, d2, d3, d4, d5, d6, d7, d8)\
if check(d7, d8, d9, 13)\
for d10 in range(10)\
if d10 not in (d1, d2, d3, d4, d5, d6, d7, d8, d9)\
if check(d8, d9, d10, 17)
]
print(sum(map(ls_to_int, r)))
%time e43()
#16695334890
#Wall time: 93 ms
""" 아래는 재귀를 이용해서푸는 버전.
1. 1~9 사이의 첫 숫자로부터 출발
2. 각 숫자에 다른 숫자를 붙여나가면서
3. 3글자가 되는 시점부터 위 조건들이 맞는 것만 필터링해나간다.
4. 최종적으로 남는 숫자들이 이를 만족하는 것.
이 버전에서는 숫자의 모음을 리스트로하면 에러가 나서 부득이하게 문자열을 이용했음."""
from functools import reduce
def check(xs:str, c:str) -> bool:
checkers = [1, 1, 1, 2, 3, 5, 7, 11, 13, 17]
l = len(xs)
a = int(xs[-2])
b = int(xs[-1])
return (a * 100 + b * 10 + int(c)) % checkers[l] == 0
def getValue(xs:str) -> int:
return reduce(lambda x, y: 10*x+y, [int(c) for c in xs], 0)
def test(xs:[str]) -> [str]:
depth = len(xs[0])
if depth > 9:
return xs
result = []
for x in xs:
for i in "0123456789":
if i not in x:
if len(x) > 2:
if check(x, i):
a = x + str(i)
result.append(a)
else:
a = x + str(i)
result.append(a)
return test(result)
def e43():
xs = [str(i) for i in range(1, 10)]
y = test(xs)
print(sum((getValue(i) for i in y)))
%time e43()
# 16695334890
# Wall time: 252 ms
Raw
e044.py
"""오각수는 Pn = n (3n − 1)/2 라는 공식으로 구할 수 있고, 처음 10개의 오각수는 다음과 같습니다.
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
위에서 P4 + P7 = 22 + 70 = 92 = P8이 됨을 볼 수 있습니다. 하지만 두 값의 차인 70 − 22 = 48 은 오각수가 아닙니다.
합과 차도 모두 오각수인 두 오각수 Pj, Pk 에 대해서, 그 차이 D = | Pk − Pj | 는 가장 작을 때 얼마입니까?"""
"""
> 오각수의 리스트를 늘려나가면서 새로운 오각수 - (오각수) 한 값이 오각수인지 (오각수의 리스트에 있는지)
그리고 새로운 오각수가 아닌 구 오각수 2개의 차가 오각수인지 검사한다.
> from_pentagonal 함수를 만들었으나, 지금까지 구한 오각수의 리스트를 set으로 만들어서 판별하는 방법이
훨씬 빠르다.
"""
def toPentagonal(n):
p = n * (3 * n - 1) / 2
return p
def e44():
ps = [toPentagonal(n) for n in range(1, 3)]
k = 3
while True:
pn = toPentagonal(k)
ts = set(ps)
for x in ps[::-1]:
y = pn - x
if y in ts:
d = abs(x-y)
if d in ts:
print(d)
return
ps.append(pn)
k += 1
%time e44()
#5482660.0
#Wall time: 931 ms
Raw
e045.py
def is_hexagonal(k):
n = (((8*k+1) ** 0.5) + 1 ) /4
return int(n) == n
"""삼각수, 오각수, 육각수는 아래 식으로 구할 수 있습니다.
삼각수 Tn = n (n + 1) / 2 1, 3, 6, 10, 15, ...
오각수 Pn = n (3n − 1) / 2 1, 5, 12, 22, 35, ...
육각수 Hn = n (2n − 1) 1, 6, 15, 28, 45, ...
여기서 T285 = P165 = H143 = 40755 가 됩니다.
오각수와 육각수도 되는, 그 다음으로 큰 삼각수를 구하세요."""
"""
모든 육각수는 삼각수이므로 오각수의 다음 항을 계속 찾으면서
이 오각수가 육각수인지를 검사한다. 육각수 검사를 위해 일반항식을 거꾸로 풀어서
그 해가 정수인지 검사함.
"""
def pn(n):
return n * ( 3 * n - 1) // 2
def e45():
k = 166
while True:
pk = pn(k)
if is_hexagonal(pk):
print(pk)
break
k += 1
%time e45()
#1533776805
#Wall time: 81 ms
Raw
e046.py
"""크리스티안 골드바흐는 모든 홀수인 합성수를 (소수 + 2×제곱수)로 나타낼 수 있다고 주장했습니다.
9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12
이 추측은 잘못되었음이 밝혀졌습니다.
위와 같은 방법으로 나타낼 수 없는 가장 작은 홀수 합성수는 얼마입니까?"""
"""
n보다 작은 소수와 n 보다 작은 제곱수를 구해서
그 합에서 n 이 있는지를 검사합니다.
"""
def memoize(f):
cache = {}
def inner(a):
if a in cache:
return cache[a]
result = f(a)
cache[a] = result
return result
return inner
@memoize
def is_prime(n):
if n < 2:
return False
if n is 2 or n is 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
if n < 9:
return True
k = 5
l = n **0.5
while k <= l:
if n % k == 0 or n % (k+2) == 0:
return False
k += 6
return True
def primes_up_to(n):
return [2] + [x for x in range(3, n, 2) if is_prime(x)]
def squared_up_to(n):
return [2*x*x for x in range(1, int(n**0.5) + 2)]
def test(n):
for p in primes_up_to(n)[::-1]:
for s in squared_up_to(n):
if p + s == n:
return True
return False
def e46():
k = 5
while True:
if not is_prime(k) and not test(k):
print(k)
break
k += 2
%time e46()
#5777
#Wall time: 1.32
Raw
e047.py
"""서로 다른 두 개의 소인수를 갖는 수들이 처음으로 두 번 연달아 나오는 경우는 다음과 같습니다.
14 = 2 × 7
15 = 3 × 5
서로 다른 세 개의 소인수를 갖는 수들이 처음으로 세 번 연속되는 경우는 다음과 같습니다.
644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19
서로 다른 네 개의 소인수를 갖는 수들이 처음으로 네 번 연속되는 경우를 찾으세요. 그 첫번째 숫자는 얼마입니까?"""
"""
set을 적극 활용한다. 예전에는 1분 이내에 들어오기가 참 힘들었는데,
Swift 보다 빠르다?
"""
def getFactors(n):
r = set()
a = n
while a > 1:
d = divide_helper(a)
r.add(d)
while a % d == 0:
a = a // d
return r
def divide_helper(n):
if n % 2 == 0:
return 2
if n % 3 == 0:
return 3
k = 5
l = n ** 0.5
while k <= l:
if n % k == 0:
return k
if n % (k+2) == 0:
return k+2
k += 6
return n
def e47():
s = 2 * 3 * 5 * 7
f0 = set()
c = 0
while True:
f1 = getFactors(s)
if len(f1) == 4 and f1.intersection(f0) == set():
c += 1
else:
c = 0
if c == 4:
print(s-3)
break
f0 = f1
s += 1
%time e47()
#134043
#Wall time: 1.7 s
Raw
e048.py
"""11 + 22 + 33 + ... + 1010 = 10405071317 입니다.
11 + 22 + 33 + ... + 10001000 의 마지막 10자리 숫자는 무엇입니까?"""
def e48():
print(str(sum((x**x for x in range(1, 1001))))[-10:])
%time e48()
#9110846700
#Wall time: 13 ms
Raw
e049.py
"""1487, 4817, 8147은 3330씩 늘어나는 등차수열입니다. 이 수열에는 특이한 점이 두 가지 있습니다.
세 수는 모두 소수입니다.
세 수는 각각 다른 수의 자릿수를 바꿔서 만들 수 있는 순열(permutation)입니다.
1자리, 2자리, 3자리의 소수 중에서는 위와 같은 성질을 갖는 수열이 존재하지 않습니다. 하지만 4자리라면 위엣것 말고도 또 다른 수열이 존재합니다.
그 수열의 세 항을 이었을 때 만들어지는 12자리 숫자는 무엇입니까?"""
"""
4자리 소수를 모두 구해서 같은 순열인 것끼리 그룹으로 묶은 다음,
원소가 3개 이상인 그룹에 대해서
등차수열이 존재하는지를 검사한다.
"""
def is_prime(n):
if n < 2:
return False
if n == 2 or n == 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
if n < 9:
return True
k = 5
l = n ** 0.5
while k <= l:
if n % k == 0 or n % (k+2) == 0:
return False
k += 6
return True
def make_key(n:int) -> int:
return int("".join(sorted(str(n))))
def find_seq(l):
for i, v in enumerate(sorted(l)):
remain = l[i+1:]
for s in remain:
dd = s + s - v
if dd in remain:
print("".join([str(x) for x in (v, s, s+dd)]))
def e49():
samples = [x for x in range(1000, 10000) if is_prime(x)]
d = {}
for p in samples:
k = make_key(p)
if k not in d:
d[k] = [p]
else:
d[k].append(p)
b = [x for x in d.values() if len(x) >= 3]
for x in b:
find_seq(x)
%time e49()
#2969629915928
#1487481712964
#Wall time: 23 ms
Raw
e050.py
"""
41은 소수이면서 다음과 같은 6개의 연속된 소수의 합으로도 나타낼 수 있습니다.
41 = 2 + 3 + 5 + 7 + 11 + 13
이것은 100 이하에서는 가장 길게 연속된 소수의 합으로 이루어진 소수입니다.
1000 이하에서는 953이 연속된 소수 21개의 합으로 가장 깁니다.
1백만 이하에서는 어떤 소수가 가장 길게 연속되는 소수의 합으로 표현될 수 있습니까?
"""
"""
성능 미달로 튜닝이 필요하다.
100만 이하의 소수의 리스트를 구해놓고
이를 이용해서 소수의 누적 합 리스트를 만든다. (S)
S[j] - S[i] 는 i+1 번째 소수로부터 j 번째 소수까지 (0 <= i < j) 까지의 순차합이 되므로
이 간격을 줄여가면서 각 오프셋에 대해서 이 값을 구해나가면
처음 만족하는 값이 정답이 될 가능성이 크다.
하지만 이 부분에 대해서도 범위가 매우 클 수 있는데 (100만 이하의 소수는 약 78000 여개)
2중으로 순회하려면 엄청난 양의 루프를 돌아야 한다.
결국 S의 배열에서 한계값인 백만의 두 배를 넘어서는 경우에는 S[j] - S[i]를 구해보는 것이
(어차피 백만을 넘을 것이므로) 의미가 없다고 판단하고,
그 범위를 줄여준다.
"""
def prime_sieve(bound):
"""
Return a list of prime numbers from 2 to n.
Very fast, (n < 10,000,000) in 0.4 sec.
----
Algorithm & Python source: Robert William Hanks
http://stackoverflow.com/questions/17773352/python-sieve-prime-numbers
"""
sieve = [True] * (bound//2)
for i in range(3, int(bound**.5)+1, 2):
if sieve[i//2]:
sieve[i*i//2::i] = [False] * ((bound-i*i-1)//(2*i)+1)
return [2] + [2*i+1 for i in range(1, bound//2) if sieve[i]]
limit = 1000000
def e50():
primes = prime_sieve(limit)
pset = set(primes)
l = len(primes)
sum_of_primes = [0] + [0] * l
for i in range(1, l+1):
sum_of_primes[i] = sum_of_primes[i-1] + primes[i-1]
sum_of_primes = [x for x in sum_of_primes if x <= limit * 2]
for i in range(len(sum_of_primes)):
for j in range(i):
k = sum_of_primes[- i + j - 1] - sum_of_primes[j]
if k <= limit and k in pset:
print(k, i, j)
return
%time e50()
# 997651 210 3
# Wall time: 151 ms
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment