NAIAHD

프로젝트 오일러

Problem 22

영문 이름 점수 합계 구하기

여기 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))

#출처: https://yuda.dev/50 [YUDA't]

Problem 25

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

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

이에 따라 수열을 12번째 항까지 차례대로 계산하면 다음과 같습니다.

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)

Problem 29

2 ≤ a ≤ 100 이고 2 ≤ b ≤ 100인 a b로 만들 수 있는 ab의 개수

여기서 중복된 것을 빼고 크기 순으로 나열하면 아래와 같은 15개의 수가 됩니다.

4,  8,  9,  16,  25,  27,  32,  64,  81,  125,  243,  256,  625,  1024,  3125

그러면, 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