Project Euler 47

• 問題

Problem 47：Distinct primes factors
The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7
15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2^2 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?

• 解答例

import sympy

i = 2
while True:
    list1 = list(sympy.factorint(i).keys())
    list2 = list(sympy.factorint(i + 1).keys())
    list3 = list(sympy.factorint(i + 2).keys())
    list4 = list(sympy.factorint(i + 3).keys())

    temp1 = []
    temp1.extend(list1)
    temp1.extend(list2)
    temp1 = list(set(temp1))

    temp2 = []
    temp2.extend(list2)
    temp2.extend(list3)    
    temp2 = list(set(temp2))

    temp3 = []
    temp3.extend(list3)
    temp3.extend(list4)    
    temp3 = list(set(temp3))

    if len(list1) == 4 and len(list2) == 4 and len(list3) == 4 and len(temp1) == 8 and len(temp2) == 8 and len(temp3) == 8:
        print(i, i + 1, i + 2)
        break
    i += 1

Project Euler 46

• 問題

Problem 46：Goldbach's other conjecture
It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×1^2
15 = 7 + 2×2^2
21 = 3 + 2×3^2
25 = 7 + 2×3^2
27 = 19 + 2×2^2
33 = 31 + 2×1^2

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

• 解答例

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

ansList = []
num = 9
while len(ansList) < 1:
    isFound = False
    if isPrime(num):
        num += 2
        isFound = True
        continue
    i = 1
    while (num - 2 * i * i) > 0:
        if isPrime(num - 2 * i * i):
            isFound = True
            break
        i += 1
    if not isFound:
        ansList.append(num)
    num += 2

print(ansList)

Project Euler 45

• 問題

Problem 45：Triangular, pentagonal, and hexagonal
Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle：Tn=n(n+1)/2　1, 3, 6, 10, 15, ...
Pentagonal：Pn=n(3n−1)/2　1, 5, 12, 22, 35, ...
Hexagonal：Hn=n(2n−1)　1, 6, 15, 28, 45, ...
It can be verified that T285 = P165 = H143 = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

• 解答例

import math

def isPentagonalNum(n):
    x = (math.sqrt(24 * n + 1) + 1) / 6.0
    return x.is_integer()
    
def calcHexagonalNum(n):
    return n * (2 * n - 1)

ansList = []
num = 1

while len(ansList) < 3:
    if isPentagonalNum(calcHexagonalNum(num)):
        ansList.append(calcHexagonalNum(num))
    num += 1
    
print(ansList)

Project Euler 44

• 問題

Problem 44：Pentagon numbers
Pentagonal numbers are generated by the formula, Pn=n(3n−1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference are pentagonal and D = |Pk − Pj| is minimised; what is the value of D?

• 解答例

import math

def isPentagonalNum(n):
    x = (math.sqrt(24 * n + 1) + 1) / 6.0
    return x.is_integer()

ans = 0
isfound = False
k = 2
 
while not isfound:
    pk = k * (3 * k - 1) // 2
    j = k - 1
    while j > 0:
        pj = j * (3 * j - 1) // 2
        if isPentagonalNum(pk - pj) and isPentagonalNum(pk + pj):
            ans = pk - pj
            isfound = True
            break
        j -= 1
    k += 1

print(ans)

Project Euler 43

• 問題

Problem 43：Sub-string divisibility
The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

d2d3d4=406 is divisible by 2
d3d4d5=063 is divisible by 3
d4d5d6=635 is divisible by 5
d5d6d7=357 is divisible by 7
d6d7d8=572 is divisible by 11
d7d8d9=728 is divisible by 13
d8d9d10=289 is divisible by 17
Find the sum of all 0 to 9 pandigital numbers with this property.

• 解答例

import itertools

p = list(map("".join, itertools.permutations('0123456789')))

sum = 0
for n in p:
    if not int(n[1] + n[2] + n[3]) % 2 == 0:
        continue
    if not int(n[2] + n[3] + n[4]) % 3 == 0:
        continue
    if not int(n[3] + n[4] + n[5]) % 5 == 0:
        continue
    if not int(n[4] + n[5] + n[6]) % 7 == 0:
        continue
    if not int(n[5] + n[6] + n[7]) % 11 == 0:
        continue
    if not int(n[6] + n[7] + n[8]) % 13 == 0:
        continue
    if not int(n[7] + n[8] + n[9]) % 17 == 0:
        continue
    sum += int(n)
    print(n)

print(sum)

Project Euler 42

• 問題

Problem 42：Coded triangle numbers
The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

• 解答例

def listTriNum(num):
    list = [1]
    i = 2
    while i * (i + 1) // 2 <= num:
        list.append(i * (i + 1) // 2)
        i += 1
    return list

num = { "A":1,
        "B":2,
        "C":3,
        "D":4,
        "E":5,
        "F":6,
        "G":7,
        "H":8,
        "I":9,
        "J":10,
        "K":11,
        "L":12,
        "M":13,
        "N":14,
        "O":15,
        "P":16,
        "Q":17,
        "R":18,
        "S":19,
        "T":20,
        "U":21,
        "V":22,
        "W":23,
        "X":24,
        "Y":25,
        "Z":26}

f = open("p042_words.txt", "r")

name = []
for line in f:
    text = line.replace('\n', '')
    text = text.replace('\r', '')
    text = text.replace('"', '')
    name = text.split(",")
f.close()

maxLen = 0
for n in name:
    if maxLen < len(n):
        maxLen = len(n)

triangleNum = listTriNum(maxLen * 26)

count = 0
for n in name:
    score = 0
    temp = list(n)
    for x in temp:
        score += num[x]
    if score in triangleNum:
        count += 1
        print(n, score)

print(count)

• 用意したファイル（p042_words.txt）

https://projecteuler.net/project/resources/p042_words.txt

Project Euler 41

• 問題

Problem 41：Pandigital prime
We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

• 解答例

import itertools

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

p = list(map("".join, itertools.permutations('1234567')))

max = 0
for n in p:
    if isPrime(int(n)) and max < int(n):
        max = int(n)

print(max)