Euler-Project(V)

发表于 | 分类于 | | 热度: ℃
字数统计: 2,550 | 阅读时长 ≈ 15

41. Pandigital prime

Problem Description

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?

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# What is the largest n-digit pandigital prime that exists?
# The maximum pandigital prime may be located in range 123456789 to 987654321
import sympy
from itertools import permutations

def getAllPermutations(n):
    original_list = list(permutations(range(1, n+1)))
    final_list = []
    for item in original_list:
        tmp_result = ''
        for tuple_object in item:
            tmp_result += str(tuple_object)
        final_list.append(tmp_result)
    return final_list

def findPrime(combinations_result):
    for item in reversed(combinations_result):
        if sympy.isprime(int(item)):
            return int(item)
    return 0

if __name__ == '__main__':
    max_result = 0
    # After some computation, we can find the aiming number is located in 7654321 to 1234567, which is a 7-digit pandigital prime
    combinations_result = getAllPermutations(7)
    final_result = findPrime(combinations_result)
    print final_result

42. Coded triangle numbers

Problem Description

The $ n^{th} $ term of the sequence of triangle numbers is given by, $ t_{n} = 1/2*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 = t_{10} $. 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?

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# How many are triangle words?

def generateTriangleNumbers(upper_bound):
    triangle_number_set = [1]
    generator_element = 1
    generatedNumber = triangle_number_set[0]
    while generatedNumber < upper_bound:
        generatedNumber = generator_element * (generator_element+1) / 2
        triangle_number_set.append(generatedNumber)
        generator_element += 1
    return triangle_number_set

def countWordValue(word_string):
    count_result = 0
    for item in word_string:
        count_result += ord(item) - 64
    return count_result

if __name__ == '__main__':
    triangle_word_count = 0
    triangle_number_set = generateTriangleNumbers(520)
    file_pointer = p042_word_path
    word_list = file_pointer.read().replace("\"", "").split(",")
    for word in word_list:
        if countWordValue(word) in triangle_number_set:
            triangle_word_count += 1
    print triangle_word_count

43. Sub-string divisibility

Problem Description

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 $ d_{1} $ be the $ 1^{st} $ digit,$ d_{2} $ be the $ 2^{nd} $ digit, and so on. In this way, we note the following:

  • $ d_{2}*d_{3}*d_{4} = 406 $ is divisible by 2
  • $ d_{3}*d_{4}*d_{5} = 063 $ is divisible by 3
  • $ d_{4}*d_{5}*d_{6}=635 $ is divisible by 5
  • $ d_{5}*d_{6}*d_{7}=357 $ is divisible by 7
  • $ d_{6}*d_{7}*d_{8}=572 $ is divisible by 11
  • $ d_{7}*d_{8}*d_{9} = 728 $ is divisible by 13
  • $ d_{8}*d_{9}*d_{10} = 289 $ is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

Solution

题解引入sympy.nextprime(n)函数以持续不断地获取素数，从而用于性质判断。该函数返回大于参数n的第一个素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# Find the sum of all 0 to 9 pandigital numbers with this property
import sympy
from itertools import permutations

def hasProperty(input_string):
    generated_prime = 1
    for index_number in range(1, 8):
        generated_prime = sympy.nextprime(generated_prime)
        if int(input_string[index_number: index_number+3]) % generated_prime != 0:
            return False
    return True

def getAllPermutations(n):
    original_list = list(permutations(range(n)))
    final_list = []
    for item in original_list:
        tmp_result = ''
        for tuple_object in item:
            tmp_result += str(tuple_object)
        final_list.append(tmp_result)
    return final_list

if __name__ == '__main__':
    sum_result = 0
    combination_result = getAllPermutations(10)
    for item in combination_result:
        if hasProperty(item):
            sum_result += int(item)
    print sum_result

44. Pentagon numbers

Problem Description

Pentagonal numbers are generated by the formula,$ P_{n} = 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 $ P_{4} + P_{7} = 22 + 70 = 92 = P_{8} $. However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, $ P_{j} $ and$ P_{k} $, for which their sum and difference are pentagonal and $ D = |P_{k} − P_{j}| $ is minimised; what is the value of D?

Solution

题解引入operator函数库，运用其中的底层函数提高运算效率，该库内函数说明如下：

operator库函数说明：https://docs.python.org/zh-cn/3/library/operator.html。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Find the pair of pentagonal numbers, Pj and Pk
# The sum of these two number and the difference of these are both pentagonal
# Output the minimum D = |Pk - Pj|

from itertools import combinations
from operator import *

def getPentagonalNumbers(upper_bound):
    return set(n*(3*n-1)//2 for n in range(1, upper_bound+1))

if __name__ == '__main__':
    result_list = []
    pentagonal_number_set = getPentagonalNumbers(3000)
    combination_result = combinations(pentagonal_number_set, 2)
    for item in combination_result:
        if add(item[0], item[1]) in pentagonal_number_set and abs(sub(item[0], item[1])) in pentagonal_number_set:
            result_list.append(abs(item[0]-item[1]))
    print min(result_list)

45. Triangular, pentagonal, and hexagonal

Problem Description

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

NumberType Formulae Example
Triangle $ T_{n} = n*(n+1) / 2 $ 1, 3, 6, 10, 15, …
Pentagonal $ P_{n} = n*(3*n-1) / 2 $ 1, 5, 12, 22, 35, …
Hexagonal $ H_{n} = n*(2*n-1) $ 1, 6, 15, 28, 45

It can be verified that $ T_{285} = P_{165} = H_{143} = 40755 $.

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

Solution1

根据题意，以1—60000为生成元构造三角形数、五边形数和六边形数对应的集合，随后求交集并输出大于40755的第一个数字即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Find the next triangle number bigger than 40755 that is also pentagonal and hexagonal
def getTriangleNumber(n):
    return set(generator*(generator+1)//2 for generator in range(1, n+1))
def getPentagonalNumber(n):
    return list(generator*(3*generator-1)//2 for generator in range(1, n+1))
def getHexagonalNumber(n):
    return list(generator*(2*generator-1) for generator in range(1, n+1))
if __name__ == '__main__':
    triangle_set = getTriangleNumber(60000)
    pentagonal_set = getPentagonalNumber(60000)
    hexagonal_set = getHexagonalNumber(60000)
    result = set(triangle_set) & set(pentagonal_set) & set(hexagonal_set)
    for item in result:
        if item > 40755:
            print item
            break

Solution2

通过观察这三类数字的生成表达式可以获得三角形数、五边形数和六边形数的判断方法：

  • 若数字x是一个三角形数，则$ (\sqrt{(8*x+1)}-1) / 2 $必为一个整数；
  • 若数字x是一个五边形数，则$ (\sqrt{(24*x+1)}+1) / 6 $必为一个整数；
  • 若数字x是一个六边形数，则$ (\sqrt{(8*x+1)}+1) / 4 $必为一个整数

同时，这三类数的生成过程满足性质：$ H(n) = T(2n-1) $，即生成元n得到的六边形数一定对应更大生成元得到的三角形数。于是可以从第144个六边形数开始逐个验证其是否可表示为五边形数即可。暴力代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Find the next triangle number bigger than 40755 that is also pentagonal and hexagonal
from __future__ import division
import math
 
def isPentagonalNumber(input_number):
    integer_n = (math.sqrt(24*input_number+1)+1) / 6
    if integer_n % 1 > 0 and integer_n % 1 < 1:
        return False
    return True
     
def getHexagonalNumber(n):
    return n*(2*n-1)

if __name__ == '__main__':
    origin_generator = 144
    hexagonal_number = getHexagonalNumber(origin_generator)
    while 1:
        print origin_generator
        if isPentagonalNumber(hexagonal_number):
            print hexagonal_number
            break
        origin_generator += 1
        hexagonal_number = getHexagonalNumber(origin_generator)

46. Goldbach’s other conjecture

Problem Description

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

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?

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
# odd_composite = odd_prime + 2 * square_number
from __future__ import division
import sympy
import math

def getPrimes(n):
    return sorted(list(sympy.primerange(3, n+1)))
# Get the odd composites
def getOddComposite(n):
    return sorted(list(set(list(i for i in range(3, n+1, 2))) - set(getPrimes(n))))

def isSquare(input_number):
    possible_square = math.sqrt(input_number / 2)
    if possible_square % 1 > 0 and possible_square % 1 < 1:
        return False
    return True

if __name__ == '__main__':
    odd_composite = getOddComposite(6000)
    prime_set = getPrimes(6000)
    for item in odd_composite:
        flag = 0
        for prime in prime_set:
            if prime >= item:
                break
            if isSquare(item - prime):
                flag = 1
        if flag == 0:
            print item
            break

47. Distinct primes factors

Problem Description

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

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

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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Find the first four consecutive integers to have four distinct prime factors each.
# What is the first of these numbers?
import sympy
def getPrimeFactorSet(a, b):
    return set(sympy.primerange(a, b+1))

def countPrimeFactors(n, factor_set, prime_set):
    for item in prime_set:
        if n % item == 0:
            factor_set.add(item)
            return countPrimeFactors(n/item, factor_set, prime_set)
    return factor_set

if __name__ == '__main__':
    prime_set = getPrimeFactorSet(1, 1000)
    for item_object in range(100000, 150000):
        if len(countPrimeFactors(item_object, set(), prime_set)) == 4 and len(countPrimeFactors(item_object+1, set(), prime_set)) == 4 and len(countPrimeFactors(item_object+2, set(), prime_set)) == 4 and len(countPrimeFactors(item_object+3, set(), prime_set)) == 4:
            print item_object
            break
# Program running time: The function run time is : 0.384 seconds.

48. Self powers

Problem Description

The series, $ 1^{1} + 2^{2} + 3^{3} + … + 10^{10} = 10405071317 $.

Find the last ten digits of the series, $ 1^{1} + 2^{2} + 3^{3} + … + 1000^{1000} $.

Solution

1
2
3
4
5
# Find the last ten digits of the series, sum(pow(n, n) for n in range(1, 1000))

if __name__ == '__main__':
    result_digits = str(sum(list(pow(i, i) for i in range(1, 1000))))[-10:]
    print result_digits

49. Prime permutations

Problem Description

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?

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# What 12-digit number do you form by concatenating the three terms in this sequence?
# Brute force in Python

import sympy
from itertools import *

def getPrimeSet(a, b):
    return list(sympy.primerange(a, b+1))

def getPermutations(input_list):
    result_list = []
    permutation_list = list(permutations(input_list, 4))
    for item in permutation_list:
        result_list.append(item[0]*1000+item[1]*100+item[2]*10+item[3])
    return set(permutations(result_list, 3))

def isPrimePermutations(input_item, prime_set):
    if input_item[0] == input_item[1]:
        return False
    if input_item[2] + input_item[0] != 2*input_item[1]:
        return False
    if input_item[0] not in prime_set or input_item[1] not in prime_set or input_item[2] not in prime_set:
        return False
    return True

def getEachDigitList(input_number):
    result_list = []
    for item in str(input_number):
        result_list.append(eval(item))
    return result_list

if __name__ == '__main__':
    prime_set = getPrimeSet(1000, 10000)
    for possible_number in prime_set:
        possible_number_list = getEachDigitList(possible_number)
        final_result_list = getPermutations(possible_number_list)
        for item in final_result_list:
            item = sorted(item)
            if isPrimePermutations(item, prime_set):
                print str(item[0]) + str(item[1]) + str(item[2])
                break

50. Consecutive prime sum

Problem Description

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?

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# Which prime, below one-million, can be written as the sum of the most consecutive primes?

import sympy

def getPrimeSet(a, b):
    return list(sympy.primerange(a, b+1))

def getAllSumResult(upper_bound, prime_set):
    result_list = []
    for index_number in range(len(prime_set)):
        sum_result = sum(prime_set[:index_number])
        if sum_result < upper_bound:
            result_list.append(sum_result)
        else:
            return result_list

def originalSumResultJudge(stored_dict, prime_set, sum_result):
    for index_number in range(len(sum_result)-1, 0, -1):
        if sum_result[index_number] in prime_set:
            stored_dict[index_number] = sum_result[index_number]
            break
    return stored_dict

def getConsecutivePrimeRange(prime_set, sum_result):
    stored_dict = {}
    first_processed_dict = originalSumResultJudge(stored_dict, prime_set, sum_result)
    for index_number1 in range(len(sum_result)-1, 0, -1):
        for index_number2 in range(len(sum_result)):
            if sum_result[index_number1] - sum_result[index_number2] in prime_set:
                first_processed_dict[index_number1-index_number2] = sum_result[index_number1] - sum_result[index_number2]
                return first_processed_dict

if __name__ == '__main__':
    prime_set = getPrimeSet(2, 1000000)
    result_list = getAllSumResult(1000000, prime_set)
    final_result = getConsecutivePrimeRange(prime_set, result_list)
    sorted_dict = sorted(final_result.iteritems(), key=lambda d: d[0], reverse=True)
    print sorted_dict[0]
请作者吃个小鱼饼干吧
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多