125874를 2배 하면 251748이 되는데, 이 둘은 같은 숫자로 이루어져 있고 순서만 다릅니다.
2배, 3배, 4배, 5배, 6배의 결과도 같은 숫자로 이루어지는 가장 작은 수는 무엇입니까?
from itertools import permutations
def isPermutation(i,j):
permutation_j = set("".join(x) for x in permutations(str(j),len(str(i))))
if str(i) not in permutation_j:
return False
return True
i = 1
result = []
while True:
nums_1 = 1 * i
nums_2 = 2 * i
nums_3 = 3 * i
nums_4 = 4 * i
nums_5 = 5 * i
nums_6 = 6 * i
if isPermutation(i, nums_1) and isPermutation(i, nums_2) and isPermutation(i, nums_3) and \
isPermutation(i, nums_4) and isPermutation(i, nums_5) and isPermutation(i, nums_6):
result.append(i)
break
i+=1
print(result)
Problem 53
1 ≤n≤ 100 일때nCr의 값이 1백만을 넘는 경우는 모두 몇 번?
def factorial(n):
if n == 0 or n ==1:
return n
else:
return n * factorial(n-1)
from tqdm.notebook import tqdm
cnt = 0
for n in tqdm(range(1,101)):
for r in range(1, n):
result = factorial(n) / (factorial(r)*factorial(n-r))
if result >1000000:
cnt +=1
print(cnt)
def is_fun(a):
alphaList = [chr(c) for c in range(ord('A'), ord('Z')+1)]
add=0
for i in a: add+=alphaList.index(i)+1
j=0
while add>0:
j+=1
add-=j
if add==0: return 1
else: return 0
with open('./project_euler/words.txt', 'r', encoding='utf-8') as f:
data=f.read()
f.close()
words=data.replace("\"","").replace(",", " ").split()
_total=0
for i in words:
_total+=is_fun(i)
print(_total)
#tengst
#dev용식
'''
삼각수 공식으로
X=1/2n(n+1)로부터
2*X = n^2 + n이 되고.. 여기에서
2*X의 sqrt를 적용한 값으로부터 탐색을 시작 할 수 있을 것 같았습니다.
'''
Problem 43
부분열에 관련된 특이한 성질을 가진 모든 팬디지털 수의 합
### 43
import itertools
#StolenByte
Total = 0
k = [2, 3, 5, 7, 11, 13, 17]
for i in itertools.permutations("".join([str(i) for i in range(0,10)])):
p = "".join(i)
isOK = 1
for n in range(len(k)):
nn = int(p[n+1:n+4])
if nn % k[n] != 0:
isOK = 0
break
if isOK == 1:
Total += int(p)
print('Total : '+str(Total))
#StolenByte
Problem 44
합과 차도 모두 오각수인 두 오각수 차의 최솟값은?
list_ = [int(n * (3*n-1)/2) for n in range(1,10000)]
from tqdm.notebook import tqdm
_result = []
for i in tqdm(range(len(list_))):
for j in range(i+1, len(list_)):
if ((list_[i]+list_[j]) in list_) and ((list_[i]-list_[j]) in list_):
_result.append(list_[j]-list_[i])
print(_result)
Problem 45
오각수와 육각수도 되는 40755 다음으로 큰 삼각수는?
list_t = [int(n * (n+1)/2) for n in range(1,100000)]
list_p = [int(n * (3*n-1)/2) for n in range(1,100000)]
list_h = [int(n*(2*n-1)) for n in range(1,100000)]
for i in list_t:
if (i in list_p) and (i in list_h):
print(i)
Problem 46
(소수 + 2×제곱수)로 나타내지 못하는 가장 작은 홀수인 합성수는?
import math
def isGolder(num):
print(num)
for i in _list:
temp = ( num - i ) /2
if math.sqrt(temp) %1 ==0:
return True
return False
num = 3
while True:
if (isPirmiray(num) == False) and (num % 2 != 0):
if isGolder(num) == False:
print(num)
break
num += 1
에러 나는 부분의 마지막이 답이다.
Problem 47
서로 다른 네 개의 소인수를 갖는 수들이 처음으로 네 번 연속되는 경우는?
Problem 48
_list = sum([n**n for n in range(1, 1000)])
str(_list)[-10:]
Problem 49
세 항이 소수이면서 다른 수의 순열이 되는 4자리 수의 등차수열 찾기
1487, 4817, 8147은 3330씩 늘어나는 등차수열입니다. 이 수열에는 특이한 점이 두 가지 있습니다.
세 수는 모두 소수입니다.
세 수는 각각 다른 수의 자릿수를 바꿔서 만들 수 있는 순열(permutation)입니다.
1자리, 2자리, 3자리의 소수 중에서는 위와 같은 성질을 갖는 수열이 존재하지 않습니다. 하지만 4자리라면 위엣것 말고도 또 다른 수열이 존재합니다.
그 수열의 세 항을 이었을 때 만들어지는 12자리 수는 무엇입니까?
def isPermutation(i,j,z):
permutation_j = set("".join(x) for x in permutations(str(j),4))
if str(i) not in permutation_j:
return False
permutation_z = set("".join(x) for x in permutations(str(z),4))
if str(i) not in permutation_z:
return False
return True
from tqdm.notebook import tqdm
_result = []
for i in tqdm(range(len(_list))):
for j in range(i+1,len(_list)):
for z in range(j+1, len(_list)):
if (_list[z] - _list[j]) == ( _list[j] - _list[i]) and (isPermutation(_list[i],_list[j],_list[z]) ):
_result.append([str(_list[i])+str(_list[j])+str(_list[z])])
print(_result)
Problem 50
1백만 이하의 소수 중 가장 길게 연속되는 소수의 합으로 표현되는 수는?
41은 소수이면서 다음과 같은 6개의 연속된 소수의 합으로도 나타낼 수 있습니다.
41 = 2 + 3 + 5 + 7 + 11 + 13
이것은 100 이하에서는 가장 길게 연속된 소수의 합으로 이루어진 소수입니다.
1000 이하에서는 953이 연속된 소수 21개의 합으로 가장 깁니다.
1백만 이하에서는 어떤 소수가 가장 길게 연속되는 소수의 합으로 표현될 수 있습니까?
Problem 51
일부 숫자를 치환했을 때 8개의 서로 다른 소수가 생기는 가장 작은 소수?
두 자리 수 *3의 첫번째 자리를 여러가지로 바꿨을 때 가능한 아홉 가지의 결과 중에서 13, 23, 43, 53, 73, 83의 여섯 개는 소수입니다.
56**3 의 3번째와 4번째 자리를 동일한 숫자로 바꿔서 만들어지는 10개의 다섯자리 수 중에서는 아래에서 보듯이 7개가 소수가 되며, 이것은 이런 식으로 7개의 소수가 만들어지는 첫번째 경우입니다. 이 소수 집단의 첫번째 수인 56003은 이런 성질을 갖는 가장 작은 소수입니다.
56003, 56113, 56333, 56443, 56663, 56773, 56993
위의 예처럼 원래의 일부를 동일한 숫자로 치환했을 때 8개의 소수 집단이 만들어지는 경우를 찾고, 그 집단에 속한 가장 작은 소수를 구하세요. 치환하는 자리는 인접하지 않아도 되고, 가장 앞부분을 치환하는 경우 거기에 0은 올 수 없습니다.
1부터n까지의 각 숫자를 한 번씩만 써서 만들 수 있는 수를 팬디지털(pandigital)이라고 합니다. 예를 들면 15234는 1부터 5의 숫자가 한 번씩만 쓰였으므로 1 ~ 5 팬디지털입니다.
7254라는 수는 그런 면에서 특이한데, 39 × 186 = 7254 라는 곱셈식을 만들 때 이것이 1 ~ 9 팬디지털이 되기 때문입니다.
이런 식으로a×b=c가 1 ~ 9 팬디지털이 되는 모든c의 합은 얼마입니까?
(참고: 어떤c는 두 개 이상의 (a,b)쌍에 대응될 수도 있는데, 이런 경우는 하나로 칩니다)
n = []
for a in range(1,100):
for b in range(1,10000):
if a <= b:
c = a * b
if (len(str(a)+str(b)+str(c)) == len(set(str(a)+str(b)+str(c))) == 9) \
& ('0' not in str(a)) & ('0' not in str(b)) & ('0' not in str(c)):
n.append(c)
n = list(set(n))
sum(n)
#ytung777
Problem 33
이상한 방법으로 약분할 수 있는 분수 찾기
_list = []
for i in range(10, 100):
for j in range(i+1, 100):
_list.append((i,j))
def sameNums(i,j):
if str(i)[1] == '0':
return
else:
if str(i)[0] == str(j)[0] or str(i)[0] == str(j)[1]:
return str(i)[0]
elif str(i)[1] == str(j)[0] or str(i)[1] == str(j)[1]:
return str(i)[1]
else :
return
result = []
for i, j in _list:
same = sameNums(i,j)
if (same != None) :
if int(str(j).replace(str(same),'',1)) != 0:
if (i/j) == (int(str(i).replace(str(same),'',1)) /int(str(j).replace(str(same),'',1))):
result.append((i,j))
print(result)
Problem 34
각 자릿수의 팩토리얼을 더했을 때 자기 자신이 되는 수들의 합은?
수 145는 신기한 성질이 있습니다. 각 자릿수의 팩토리얼(계승)을 더하면 1! + 4! + 5! = 1 + 24 + 120 = 145 처럼 자기 자신이 됩니다.
이렇게 각 자릿수의 팩토리얼을 더하면 자기 자신이 되는 모든 수의 합을 구하세요.
단, 1! = 1 과 2! = 2 의 경우는 덧셈이 아니므로 제외합니다.
def factory(n):
if n == 1 or n == 0:
return 1
return factory(n-1) * n
print(factory(0))
result = []
for i in range(10, 100000):
length = len(str(i))
_sum = 0
for a in range(0, length):
_sum += factory(int(str(i)[a]))
if _sum == i:
result.append(i)
print(result)
print(sum(result))
from math import factorial
factorial(0)
Problem 35
백만 미만인 원형 소수 개수 구하기
소수 중에서 각 자리의 숫자들을 순환시켜도 여전히 소수인 것을 원형 소수(circular prime)라고 합니다. 예를 들어 197은 971, 719가 모두 소수이므로 여기에 해당합니다.
이런 소수는 100 미만에 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97 처럼 13개가 있습니다.
그러면 1,000,000 미만에는 모두 몇 개나 있을까요?
######### 35
from tqdm.notebook import tqdm
def isPrime(n):
if n == 1 or n == 2 or n ==3:
return True
for i in range(2, n):
if n % i == 0:
return False
return True
def isAllPrime(n):
if not isPrime(n):
return False
if len(str(n)) != 1 and not isPrime(int(str(n)[::-1])):
return False
return True
#1000000
#print([i for i in tqdm(range(2, 100)) if isAllPrime(i)])
print(len([i for i in tqdm(range(2, 1000000 )) if isAllPrime(i)]))
Problem 36
10진법과 2진법으로 모두 대칭수인 1000000 미만 수의 합
############# 36
from tqdm.notebook import tqdm
# 대칭수 확인
def ispalindrome(n):
if (n == int(str(n)[::-1])) and (bin(n).replace('0b','') ==bin(n).replace('0b','')[::-1]):
return True
return False
print(sum([i for i in tqdm(range(1, 1000000 )) if ispalindrome(i)]))
Problem 37
왼쪽이나 오른쪽에서 한자리씩 없애가도 여전히 소수인 수의 합은?
소수 3797에는 왼쪽부터 자릿수를 하나씩 없애거나 (3797, 797, 97, 7) 오른쪽부터 없애도 (3797, 379, 37, 3) 모두 소수가 되는 성질이 있습니다.
이런 성질을 가진 소수는 단 11개만이 존재합니다. 이것을 모두 찾아서 합을 구하세요.
(참고: 2, 3, 5, 7은 제외합니다)
def isPrime(n):
if n ==1:
return False
if n == 2 or n ==3:
return True
for i in range(2, n):
if n % i == 0:
return False
return True
def isAllPrime(n):
if str(n)[-1] not in ('3','5','7','2'):
return False
if str(n).find('0') > 0:
return False
if not isPrime(n):
return False
for i in range(len(str(n))):
if not isPrime(int(str(n)[i:len(str(n))])):
return False
for i in range(len(str(n))):
if not isPrime(int(str(n)[:len(str(n))-i])):
return False
return True
result_ = []
i = 10
while True:
if isAllPrime(i):
result_.append(i)
print(result_)
if i % 100000 == 0:
print(i)
if len(result_) == 11:
break
i += 1
print(sum(result_))
Problem 38
어떤 수에 (1, 2, ... )를 곱해서 이어붙여 얻을 수 있는 가장 큰 1 ~ 9 팬디지털 수
from tqdm.notebook import tqdm
def is_pandigital(num_list):
pandigital_list = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
return all(num in num_list for num in pandigital_list)
list_= []
def pandigital_cal(start,end):
for num in tqdm(range(start, end)):
i = 1
result_list = []
result = ''
while len(result) < 9:
result = num * i
result_list.append(str(result))
result = ''.join(result_list)
i += 1
if len(result) == 9:
result_list = list(result)
if is_pandigital(result_list):
list_.append(int(result))
return list_
print(is_pandigital(['1','9', '2', '3', '8', '4', '5', '7', '6']))
list_ = pandigital_cal(2, 9999 )
print(max(list_))
Problem 39
가장 많은 직각삼각형이 만들어지는 둘레(≤ 1000)의 길이는?
def fun_(n):
result = []
for i in range(1, n):
for j in range(i+1, n):
z = 120 -i -j
if (i ** 2 + j ** 2 == z **2) and (i <j <z):
result.append([i,j,z])
return result
dict_ = {}
from tqdm.notebook import tqdm
for num in tqdm(range(1,1000)):
dict_[num] = len(fun_(num))
print(dict_)
Problem 40
어떤 무리수에서 소수점n번째 자리 숫자 알아내기
#0.123456789101112131415161718192021...
def get_name(num):
_list = [str(i) for i in range(1,100000)]
str_list = "".join(_list)
n = 1
_result = 1
while n <= num:
_result = _result * int(str_list[n-1])
n = n * 10
return _result
print(get_name(100000))
Problem 41
n자리 팬디지털 소수 중에서 가장 큰 수
1부터n까지의 숫자를 하나씩만 써서 만든n자리 숫자를 팬디지털(pandigital)이라고 부릅니다. 2143은 4자리 팬디지털인데, 이 수는 동시에 소수이기도 합니다.
n자리 팬디지털 소수 중에서 가장 큰 수는 무엇입니까?
############# 41
#https://soooprmx.com/%EC%98%A4%EC%9D%BC%EB%9F%AC-%ED%94%84%EB%A1%9C%EC%A0%9D%ED%8A%B8-41/
from functools import reduce
from itertools import permutations #순열 또는 치환은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다.
def is_prime(n):
if n < 2: return False
if n in (2, 3): return True
if n % 2 is 0 or n % 3 is 0: return False
if n < 10 : return True
l, k = n**0.5, 5
while k <= l:
if n % k is 0 or n % (k+2) is 0: return False
k += 6
return True
for i in permutations((7,6,5,4,3,2,1)):
j = reduce(lambda x, y: 10*x + y, i)
if is_prime(j):
print(j)
break
여기 5천개 이상의 영문 이름들이 들어있는 46KB짜리 텍스트 파일names.txt이 있습니다 (우클릭해서 다운로드 받으세요). 이제 각 이름에 대해서 아래와 같은 방법으로 점수를 매기고자 합니다.
먼저 모든 이름을 알파벳 순으로 정렬합니다.
각 이름에 대해서, 그 이름을 이루는 알파벳에 해당하는 수(A=1, B=2, ..., Z=26)를 모두 더합니다.
여기에 이 이름의 순번을 곱합니다.
예를 들어 "COLIN"의 경우, 알파벳에 해당하는 수는 3, 15, 12, 9, 14이므로 합이 53, 그리고 정렬했을 때 938번째에 오므로 최종 점수는 938 × 53 = 49714가 됩니다.
names.txt에 들어있는 모든 이름의 점수를 계산해서 더하면 얼마입니까?
result = []
with open ("names.txt") as f:
result = f.read().split(',')
result.sort()
from string import ascii_uppercase
print(ascii_uppercase.index('C')+ 1)
i = 0
total = 0
while i < len(result):
result_1 = 0
temp = result[i].strip('"')
for j in temp:
result_1 += (ascii_uppercase.index(j) + 1)
i += 1
total += (result_1 * i)
print(total)
Problem 23
두 과잉수의 합으로 나타낼 수 없는 모든 양의 정수의 합은?
자신을 제외한 약수(진약수)를 모두 더하면 자기 자신이 되는 수를 완전수라고 합니다. 예를 들어 28은 1 + 2 + 4 + 7 + 14 = 28 이므로 완전수입니다. 또, 진약수의 합이 자신보다 작으면 부족수, 자신보다 클 때는 과잉수라고 합니다.
12는 1 + 2 + 3 + 4 + 6 = 16 > 12 로서 과잉수 중에서는 가장 작습니다. 따라서 과잉수 두 개의 합으로 나타낼 수 있는 수 중 가장 작은 수는 24 (= 12 + 12) 입니다.
해석학적인 방법을 사용하면, 28123을 넘는 모든 정수는 두 과잉수의 합으로 표현 가능함을 보일 수가 있습니다. 두 과잉수의 합으로 나타낼 수 없는 가장 큰 수는 실제로는 이 한계값보다 작지만, 해석학적인 방법으로는 더 이상 이 한계값을 낮출 수 없다고 합니다.
그렇다면, 과잉수 두 개의 합으로 나타낼 수 없는 모든 양의 정수의 합은 얼마입니까?
def sum_of(number):
_sum= 0
for i in range(1, number):
if number % i ==0:
_sum += i
return _sum
result = []
for i in range(1, 28123):
if sum_of(i) > i:
result.append(i)
sum_set = set() #2개의 초과수 합을 저장하는 집합
for i in result:
for j in result:
if(i+j < 28123):
sum_set.add(i+j)
result = sum(range(1,28123)) - sum(sum_set)
print(result)
Problem 24
0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 1,000,000번째 사전식 순열은?
어떤 대상을 순서에 따라 배열한 것을 순열이라고 합니다. 예를 들어 3124는 숫자 1, 2, 3, 4로 만들 수 있는 순열 중 하나입니다.
이렇게 만들 수 있는 모든 순열을 숫자나 문자 순으로 늘어놓은 것을 사전식(lexicographic) 순서라고 합니다. 0, 1, 2로 만들 수 있는 사전식 순열은 다음과 같습니다.
012 021 102 120 201 210
0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 사전식 순열에서 1,000,000번째는 무엇입니까?
import itertools
def cal_lexicographic_permutation(range_to) :
seq = 1
num = '0123456789'
num_list = itertools.permutations(num)
for lexi_num in num_list :
if seq == range_to :
return "".join(lexi_num)
seq += 1
print(cal_lexicographic_permutation(1000000))
a = 1
b = 1
_sum = 2
while len(str(b)) != 1000:
_sum += 1
tmp = a
a = b
b += tmp
print(_sum)
Problem 26
1000 이하의d중에서 1/d이 가장 긴 순환마디를 갖는 수는?
분자가 1인 분수를 단위분수라고 합니다. 분모가 2에서 10까지의 단위분수는 아래와 같습니다.
숫자 위에 찍힌 점은 순환마디를 나타내는데, 1/6의 경우 순환마디는 "6"으로 0.166666...처럼 6이 무한히 반복됨을 뜻합니다. 같은 식으로 1/7은 6자리의 순환마디(142857)를 가집니다.
d를 1000 이하의 정수라고 할 때, 단위분수 1/d의 순환마디가 가장 긴 수는 무엇입니까?
y = 0
n = 0
p = [1]
for i in range(2, 1000+1):
r = []
t = 1
while True:
t = t * 10
#print(i, t)
if t in r:
break
r.append(t)
t = t % i
#print(t, r)
if (r[len(r)-1] == 0):
print(i, r, len(r), "순환소수 아님")
else:
print(i, r, "순환소수임 소숫점첫번째부터 순환소수끝까지 자리 합계 : ", len(r))
p.append(len(r))
print(p, max(p), p.index(max(p))+1)
jcbang의 답안 참조
Problem 27
연속되는n에 대해 가장 많은 소수를 만들어내는 이차식
절대값 주의하기
##### 27
def isPriminary(num):
for i in range(2, abs(num)):
if num % i ==0:
return False
return True
print(isPriminary(2))
print(isPriminary(3))
print(isPriminary(4))
max_a = 0
max_b = 0
def _fun(a, b):
n = 0
_result = []
while True:
_fun = n ** 2 + a*n + b
if isPriminary(_fun) == False:
break
_result.append(n)
n += 1
return _result
result = []
for a in range(-999, 1000):
for b in range(-999, 1000):
_result = _fun(a, b)
if len(_result) > len(result):
result = _result[::]
max_a = a
max_b = b
print(max_a, max_b)
print(max_a* max_b)
Problem 28
1001×1001 나선모양 행렬에서 대각선 원소의 합은?
수 1부터 시작해서 우측으로부터 시계방향으로 감아 5×5 행렬을 만들면 아래와 같이 됩니다.
여기서 대각선 상의 수를 모두 더한 값은 101 입니다.
같은 방식으로 1001×1001 행렬을 만들었을 때, 대각선 상의 수를 더하면 얼마가 됩니까?
_sum = 1
for i in range(3, 1002, 2):
count = 0
for j in reversed(range(1, i*i+1, i-1)):
count += 1
_sum += j
if count == 4:
break;
print(_sum)
그러면, 2 ≤a≤ 100 이고 2 ≤b≤ 100인a,b를 가지고 만들 수 있는ab는 중복을 제외하면 모두 몇 개입니까?
result = []
for a in range(2, 101):
for b in range(2, 101):
result.append(a** b)
print(len(set(result)))
Problem 30
각 자리 숫자를 5제곱해서 더했을 때 자기 자신이 되는 수들의 합은?
각 자리의 숫자를 4제곱해서 더했을 때 자기 자신이 되는 수는 놀랍게도 단 세 개밖에 없습니다.
(1 = 14의 경우는 엄밀히 말해 합이 아니므로 제외합니다)
위의 세 수를 모두 더하면 1634 + 8208 + 9474 = 19316 입니다.
그렇다면, 각 자리 숫자를 5제곱해서 더했을 때 자기 자신이 되는 수들의 합은 얼마입니까?
result = []
for num in range(2, 10000000):
num_str = str(num)
len_num_str = 5
num_sum = 0
for i in range(len(num_str)):
num_sum += int(num_str[i]) ** len_num_str
if num_sum == num:
result.append(num)
print(result)
print(sum(result))
Problem 31
영국 화폐 액면가를 조합하는 방법의 수
영국의 화폐 단위는 파운드(£)와 펜스(p)이고, 동전의 종류는 아래와 같습니다.
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), £2 (200p)
이 동전들을 가지고 2파운드를 만드는 방법은 다양할 것입니다. 예를 하나 들면 이렇습니다.
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
2파운드를 만드는 서로 다른 방법은 모두 몇 가지나 있습니까?
def f(x):
coins=[1,2,5,10,20,50,100,200]
dp=[0 for i in range(x+1)]
dp[0]=1
for coin in coins:
for cost in range(1,x+1):
if cost-coin>=0:
dp[cost]+=dp[cost-coin]
return dp[-1]
print(f(200))
#qeqioieq
key = 1
key1 = 0
while True:
keys = key+key1
print(keys)
value = []
for i in range(1,keys+1):
if keys % i ==0:
value.append(i)
if len(value) >= 500:
print(keys)
break
key1 = keys
key += 1
Problem 13
50자리 수 100개를 더한 값의 첫 10자리 구하기
아래에 50자리 수가 100개 있습니다. 이것을 모두 더한 값의 첫 10자리는 얼마입니까?
아직 증명은 되지 않았지만, 이런 과정을 거치면 어떤 수로 시작해도 마지막에는 1로 끝나리라 생각됩니다. (역주: 이것은 콜라츠 추측 Collatz Conjecture이라고 하며, 이런 수들을 우박수 hailstone sequence라 부르기도 합니다)
그러면, 백만(1,000,000) 이하의 수로 시작했을 때 1까지 도달하는데 가장 긴 과정을 거치는 수는 얼마입니까?
참고:계산 과정에는 백만을 넘어가는 수가 나와도 괜찮습니다.
dictnum = {}
values=[]
count= 0
for nums in range(1,1000001):
key = nums
while True:
if nums == 1:
values.insert(0,key)
dictnum[key] = values
if count < len(values):
count= len(values)
total = key
values= []
break
if nums%2 ==0:
nums = int(nums/2)
else:
nums = 3* nums +1
values.append(nums)
print("Answer: {:d}".format(total))
Problem 15
20×20 격자의 좌상단에서 우하단으로 가는 경로의 수
아래와 같은 2 × 2 격자의 왼쪽 위 모서리에서 출발하여 오른쪽 아래 모서리까지 도달하는 길은 모두 6가지가 있습니다 (거슬러 가지는 않기로 합니다).
그러면 20 × 20 격자에는 모두 몇 개의 경로가 있습니까?
def factory(n):
if n == 1:
return n
else:
return n * factory(n-1)
factory_40 = factory(40)
factory_20 = factory(20)
total = factory_40 / (factory_20 * factory_20)
print("Answer: {:d}".format(int(total)))
2x 2
4개중 2개 선택하는 방법
20x20은 40개중 20 개 선택하는 방법
Problem 16
21000의 각 자릿수를 모두 더하면?
data = 2**1000
_sum =0
for i in range(0,len(str(data))):
_sum += int(str(data)[i])
print(_sum)
Problem 17
1부터 1000까지 영어로 썼을 때 사용된 글자의 개수는?
1부터 5까지의 수를 영어로 쓰면one, two, three, four, five이고, 각 단어의 길이를 더하면 3 + 3 + 5 + 4 + 4 = 19 이므로 사용된 글자는 모두 19개입니다.
1부터 1,000까지 영어로 썼을 때는 모두 몇 개의 글자를 사용해야 할까요?
참고: 빈 칸이나 하이픈('-')은 셈에서 제외하며, 단어 사이의and는 셈에 넣습니다. 예를 들어 342를 영어로 쓰면three hundred and forty-two가 되어서 23 글자, 115 =one hundred and fifteen의 경우에는 20 글자가 됩니다.
numbers = { 1: "one",
2: "two",
3: "three",
4: "four",
5: "five",
6: "six",
7: "seven",
8: "eight",
9: "nine",
10: "ten",
11: "eleven",
12: "twelve",
13: "thirteen",
14: "fourteen",
15: "fifteen",
16: "sixteen",
17: "seventeen",
18: "eighteen",
19: "nineteen",
20: "twenty",
30: "thirty",
40: "forty",
50: "fifty",
60: "sixty",
70: "seventy",
80: "eighty",
90: "ninety",
100: "hundred",
1000: "thousand"}
def numberToEng(num):
if (num > 20 and num <100) and num %10 != 0:
nums = divmod(num,10)
return numbers[nums[0]*10]+" "+ numberToEng(nums[1])
elif num > 100 and num < 1000:
nums = divmod(num,100)
if nums[1] != 0:
if nums[1]<20 or nums[1]%10 ==0:
return numbers[nums[0]] +" "+numbers[100]+" and "+ numbers[nums[1]]
else:
nums2 = divmod(nums[1],10)
return numbers[nums[0]] +" "+numbers[100]+" and "+ numbers[nums2[0]*10] +"-"+ numbers[nums2[1]]
else:
return numbers[nums[0]] +" "+numbers[100]
else:
if num % 100 == 0:
return "one " + numbers[num]
return numbers[num]
_sum = 0
for i in range(1,1001):
_sum += len(numberToEng(i).replace(" ","").replace("-",""))
print(_sum)
Problem 18
삼각형을 따라 내려가면서 합이 최대가 되는 경로 찾기
다음과 같이 삼각형 모양으로 수를 배열했습니다.
삼각형의 꼭대기부터 아래쪽으로 인접한 수를 찾아 내려가면서 합을 구하면, 위의 그림처럼 3 + 7 + 4 + 9 = 23 이 가장 큰 합을 갖는 경로가 됩니다.
다음 삼각형에서 합이 최대가 되는 경로를 찾아서 그 합을 구하세요.
참고:여기서는 경로가 16384개밖에 안되기 때문에, 모든 경로의 합을 일일이 계산해서 답을 구하는 것이 가능합니다. 하지만 67번 문제에는 100층짜리 삼각형 배열이 나옵니다. 그런 경우에는 좀 더 현명한 풀이 방법을 찾아야겠지요.
다음은 달력에 관한 몇 가지 일반적인 정보입니다 (필요한 경우 좀 더 연구를 해 보셔도 좋습니다).
1900년 1월 1일은 월요일이다.
4월, 6월, 9월, 11월은 30일까지 있고, 1월, 3월, 5월, 7월, 8월, 10월, 12월은 31일까지 있다.
2월은 28일이지만, 윤년에는 29일까지 있다.
윤년은 연도를 4로 나누어 떨어지는 해를 말한다. 하지만 400으로 나누어 떨어지지 않는 매 100년째는 윤년이 아니며, 400으로 나누어 떨어지면 윤년이다
20세기 (1901년 1월 1일 ~ 2000년 12월 31일) 에서, 매월 1일이 일요일인 경우는 총 몇 번입니까?
import datetime
import numpy as np
data = np.arange('1901-01','2001-01', dtype='datetime64[D]')
count= 0
for i in data:
day = str(i).split("-")
if datetime.date(int(day[0]),int(day[1]),int(day[2])).weekday() ==6 and int(day[2]) ==1:
count+= 1
print(count)
Problem 20
100! 의 자릿수를 모두 더하면?
예를 들자면 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800 이 되는데, 여기서 10!의 각 자릿수를 더해 보면 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 입니다.
100! 의 자릿수를 모두 더하면 얼마입니까?
def fac(n):
if n == 1:
return 1
return n * fac(n-1)
result = fac(100)
_sum = 0
for i in str(result):
_sum += int(i)
print(_sum)
print(sum(map(int, str(fac(100)))))
# int 를 넣어주면 int로 반환한다.
Problem 21
10000 이하 모든 친화수(우애수)의 합은?
예를 들어 220의 약수는 자신을 제외하면 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 이므로 그 합은d(220) = 284 입니다. 또 284의 약수는 자신을 제외하면 1, 2, 4, 71, 142 이므로d(284) = 220 입니다. 따라서 220과 284는 친화쌍이 됩니다.
10000 이하의 친화수들을 모두 찾아서 그 합을 구하세요.
diction = {}
for i in range(2,10001):
values = []
for j in range(1, i-1):
if i % j == 0:
values.append(j)
diction[i] = values
diction_1= {}
for key in diction.keys():
diction_1[key] = sum(diction[key])
result = []
for key in diction_1.keys():
for key1 in diction_1.keys():
if key == diction_1[key1] and key1 == diction_1[key] and key != key1:
result.append(key)
print(result)
print(sum(result))
number = 1000
sumNumber = 0
for i in range(number):
if i % 3 == 0 or i % 5 == 0:
sumNumber += i
print(sumNumber)
sumNumber = sum([x for x in range(1000) if ((x % 5 == 0) or (x % 3 == 0))])
print(sumNumber)
Problem 2
피보나치 수열에서 4백만 이하이면서 짝수인 항의 합?
num1=0
num2=1
result=0
while num1<=4000000:
num1,num2=num2,num1+num2
if num1%2==0:
result+=num1
print(result)
Problem 3
00851475143의 소인수 중에서 가장 큰 수를 구하세요.
num = 600851475143
result = 0
i = 2
while i <= num:
if num % i == 0:
result = i
num = num / i
print(result)
else:
i += 1
Problem 4
세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?
*** s[::-1] 생각하기
def palindrome(s):
l = len(s)
if s != s[::-1]:
return False
return True
result= 0
for i in range(100,1000):
for j in range(100,1000):
mul = i * j
if palindrome(str(mul)):
if mul > result:
result = mul
print(result)
Probelm 5
그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?
result = 21
isSuc = False
while True:
isSuc = True
for i in range(1, 21):
if result % i != 0:
isSuc = False
break
if isSuc:
print(result)
break
result += 1
따라서 1부터 10까지 자연수에 대해 "합의 제곱"과 "제곱의 합" 의 차이는 3025 - 385 = 2640 이 됩니다.
그러면 1부터 100까지 자연수에 대해 "합의 제곱"과 "제곱의 합"의 차이는 얼마입니까?
def sqrt(number):
result = 0
for i in range(1,number+1):
result += i ** 2
return result
def sumsqrt(number):
result = int((number * (number + 1 ) )/ 2)
return result ** 2
num = 100
sumsqrt(num ) - sqrt(num)
sum(range(1, 101))**2 - sum([i**2 for i in range(1, 101)])
Probelm 7
소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, ... 과 같이 됩니다.
이 때 10,001번째의 소수를 구하세요.
num = 2
result = []
while True:
isAdd = True
for i in range(2, num):
if num % i == 0:
isAdd = False
break
if isAdd:
result.append(num)
if len(result) ==10001 :
break
num += 1
print(result[10000])
여기서 붉게 표시된 71112의 경우 연속한 5개 숫자 7, 1, 1, 1, 2를 모두 곱하면 14입니다. 또, 그 다음 연속한 5개 숫자 11121의 경우 1, 1, 1, 2, 1을 모두 곱하면 2입니다.
이런 식으로 맨 처음 (7 × 3 × 1 × 6 × 7 = 882) 부터 맨 끝 (6 × 3 × 4 × 5 × 0 = 0) 까지 연속한 5개 숫자의 곱을 구할 수 있습니다.
이렇게 구할 수 있는 연속한 5개 숫자의 곱 중에서 가장 큰 값은 얼마입니까?
a = '''
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450'''
a = a.strip().replace('\n','')
result = []
for i in range(0 ,len(a)-4):
result.append(int(a[i]) * int(a[i+1]) * int(a[i+2]) * int(a[i+3]) * int(a[i+4]))
max(result )
* max()함수 활용 하기
함수를 많이 활용해야 한다.
Problem 9 a+b+c= 1000 이 되는 피타고라스 수
a+b+c= 1000인 피타고라스 수a,b,c는 한 가지 뿐입니다. 이 때,a×b×c는 얼마입니까?
result= []
for a in range(1, 1000):
for b in range(a+1, 1000):
c = 1000 - a - b
if a ** 2 + b ** 2 == c ** 2 and b < c:
print(a, ",,,,,", b, ",,,", c)
result.append(a*b*c)
print(max(result))
Problem 10 이백만 이하 소수의 합
10 이하의 소수를 모두 더하면 2 + 3 + 5 + 7 = 17 이 됩니다.
이백만(2,000,000) 이하 소수의 합은 얼마입니까?
result= []
for x in range(2,2000001):
isPrime = True
for i in range(2,x):
if x % i == 0:
isPrime = False
break
if isPrime:
result.append(x)
print(sum(result))
Problem 11
20×20 격자에서 연속된 네 수의 곱 중 최댓값
아래와 같은 20×20 격자가 있습니다.
위에서 대각선 방향으로 연속된 붉은 수 네 개의 곱은 26 × 63 × 78 × 14 = 1788696 입니다.
그러면 수평, 수직, 또는 대각선 방향으로 연속된 수 네 개의 곱 중 최댓값은 얼마입니까?
