NAIAHD

프로젝트 오일러

Problem 32

1~9 팬디지털 곱셈식을 만들 수 있는 모든 수의 합

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