mu chance or much chance ?

日々の戯れ言

Project Euler 50

  • 問題

Problem 50:Consecutive prime sum
The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

  • 解答例
def primeNum(num):
    prime = [2]
    i = 3
    while len(prime) < num:
        for n in prime:
            if i % n == 0:
                break
        else:
            prime.append(i)
        i += 2
    return prime[-1]

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

temp = 0
i = 1
while temp < 1000000:
    temp += primeNum(i) 
    i += 1
prime = sieveEratosthenes(primeNum(i - 2))

# 前の要素から削る
temp1 = sum(prime)
prime1 = list(prime)
for p in prime:
    temp1 -= p
    prime1.pop(0)
    if isPrime(temp1):
        break

# 後ろの要素から削る
temp2 = sum(prime)
prime = prime[::-1]
prime2 = list(prime)
for p in prime:
    temp2 -= p
    prime2.pop(0)
    if isPrime(temp2):
        break

# 結果を出力
if len(prime1) > len(prime2):
    print(temp1, prime1)
else:
    print(temp2, prime2)

Project Euler 49

  • 問題

Problem 49:Prime permutations
The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

  • 解答例
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

prime1 = sieveEratosthenes(1000)
prime2 = sieveEratosthenes(10000)
prime = sorted(list(set(prime2) - set(prime1)))

for p in prime:
    for d in range(1, (9999 - p) // 2 + 1):
        if isPrime(p + d) and isPrime(p + 2 * d):
            temp = []
            list1 = sorted(list(str(p)))
            list2 = sorted(list(str(p + d)))
            list3 = sorted(list(str(p + 2 * d)))
            if list1 == list2 and list2 == list3:
                print(str(p) + str(p + d) + str(p + 2 * d))

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