Project Euler 39

• 問題

Problem 39：Integer right triangles
If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?

• 解答例

limit = 1000
maxId = 0
maxCount = 0

for p in range(2, limit + 1, 2):
    count = 0
    for a in range(2, p // 3 + 1):
        if (p * (p - 2 * a)) % (2 * (p - a)) == 0:
            b = (p * (p - 2 * a)) // (2 * (p - a))
            c = p - a - b
            if a <= b and b <= c:
                count += 1
    if maxCount < count:
        maxCount = count
        maxId = p

print(maxId, maxCount)

Project Euler 38

• 問題

Problem 38：Pandigital multiples
Take the number 192 and multiply it by each of 1, 2, and 3:

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?

• 解答例

max = 0
for i in range(1, 10000):
    tempStr = []
    j = 1
    while True:
        tempStr.extend(list(str(i * j)))
        if len(tempStr) >= 9:
            if "".join(sorted(tempStr)) == '123456789':
                if max < int("".join(tempStr)):
                    max = int("".join(tempStr))
                    print(i)
            break
        j += 1

print(max)

Project Euler 37

• 問題

Problem 37：Truncatable primes
The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

• 解答例

def isPrime(num):
    if num <= 1:
        return False
    elif num == 2 or num == 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False
    if not(num % 6 == 1) and not(num % 6 == 5):
        return False
    i = 5
    while i * i <= num:
        if num % i == 0 or num % (i + 2) == 0:
            return False
        i += 6
    return True

ans = []
num = 21
while True:
    if not isPrime(num):
        num += 1
        continue
    # check left side
    tempLeft = num
    isLeftPrime = True
    temp = list(str(tempLeft))
    l = len(temp)
    for i in range(l - 1):
        temp.pop(0)
        tempNum = int("".join(temp))
        if not isPrime(tempNum):
            isLeftPrime = False
            break
    if not isLeftPrime:
        num += 1
        continue
    # check right side
    tempRight = num
    isRightPrime = True
    temp = list(str(tempRight))
    l = len(temp)
    for i in range(l - 1):
        temp.pop()
        tempNum = int("".join(temp))
        if not isPrime(tempNum):
            isRightPrime = False
            break
    if not isRightPrime:
        num += 1
        continue

    ans.append(num)
    num += 1

    if len(ans) == 11:
        break

print(sum(ans))

Project Euler 36

• 問題

Problem 36：Double-base palindromes
The decimal number, 585 = 10010010012 (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

• 解答例

sum = 0

for i in range(1, 1000000):
    strNum = str(i)
    strBinaryNum = str(format(i, 'b'))
    if(strNum == strNum[::-1] and strBinaryNum == strBinaryNum[::-1]):
        print(strNum, strBinaryNum)
        sum += i

print(sum)

Project Euler 35

• 問題

Problem 35：Circular primes
The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

• 解答例

def sieveEratosthenes(num):
    isPrime = [True] * (num + 1)
    isPrime[0] = False
    isPrime[1] = False
    primes = []
    for i in range(2, (num + 1)):
        if isPrime[i]:
            primes.append(i)
            for j in range(2 * i, (num + 1), i):
                isPrime[j] = False
    return primes

def isPrime(num):
    if num <= 1:
        return False
    elif num == 2 or num == 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False
    if not(num % 6 == 1) and not(num % 6 == 5):
        return False
    i = 5
    while i * i <= num:
        if num % i == 0 or num % (i + 2) == 0:
            return False
        i += 6
    return True

prime = sieveEratosthenes(999999)
circularPrime = []

for n in prime:
    temp = list(str(n))
    l = len(temp)
    isCircularPrime = True
    for i in range(l - 1):
        tempChar = temp.pop(0)
        temp.append(tempChar)
        tempNum = int("".join(temp))
        if not isPrime(tempNum):
            isCircularPrime = False
            break
    
    if isCircularPrime:
        circularPrime.append(n)

print(len(circularPrime))

Project Euler 34

• 問題

Problem 34：Digit factorials
145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

• 解答例

import math

sum = 0
for i in range(3, math.factorial(9) * 7 + 1):
    temp = 0
    strNum = list(str(i))
    for n in strNum:
        temp += math.factorial(int(n))
    if i == temp:
        sum += temp
print(sum)

Project Euler 33

• 問題

Problem 33：Digit cancelling fractions
The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.<<

• 解答例

def gcd(m, n):
    while n:
        m, n = n, m % n
    return m

tempNumerator = 1
tempDenominator = 1
for a in range(1, 10):
    for b in range(1, 10):
        for c in range(1, 10):
            if a < b and not a == c and not b == c:
                if (10 * a + c) * b ==  (10 * c + b) * a:
                    temp1 = 10 * a + c
                    temp2 = 10 * c + b
                    tempNumerator *= temp1
                    tempDenominator *= temp2
                if (10 * c + a) * b ==  (10 * b + c) * a:
                    temp1 = 10 * c + a
                    temp2 = 10 * b + c
                    tempNumerator *= temp1
                    tempDenominator *= temp2

print(tempDenominator // gcd(tempNumerator, tempDenominator))