哟西~好的，这一P弄完，就把EP上第一页的题目全部搞完了~

这一P开始有个很明显的迹象就是。。。Python完成的任务逐渐增多，而Mathematica慢慢变少。。

其实也不是说Mathematica完成不了，只是确实有些问题用Mma来完成不能体现Mma的魅力！！而且我在想算法的时候，只要想到代码里面会有for语句什么的，我就会本能地打开Python；【C++比较繁琐，Matlab？for语句不是开玩笑的！！】不过如果涉及到字符串比较复杂的操作，或者分解质因数这一类比较数学的题目，不管怎么样，还是Mma走起吧。。话说Mma和Python在Euler Project上语言分数排名上是第二和第三诶。。

毕竟只要复杂度不是太恐怖或者算法太烂，还用不上C++这个最终兵器。。不过估计之后的趋势会变成，C++逐渐比重增加。。。这就当一个预言吧。。

到了这里，发现需要积累一些常用函数了，目前为止这里用个最多的几个就是Python生成器输出全排列，判断是否是质数，生成指定范围内的质数表这几个。

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?

Code：Python

#输出全排列
def QPL(m_list):
    if len(m_list) == 1:
        yield m_list
    for i in range(len(m_list)):
        restlist = m_list[0:i]+m_list[i+1:]
        for subres in QPL(restlist):
            yield [m_list[i]]+subres;

#判断质数
def isPrime(n):
    if n <= 1:
        return False
    for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True
    
for t in QPL(range(7,0,-1)):
    if t[-1] != 1 and t[-1] != 3 and t[-1] != 7:
        continue;
    k = int(''.join(map(str,t)));
    if isPrime(k):
        print k
        break

Problem 42:Coded triangle numbers

The n^th term of the sequence of triangle numbers is given by, t_n = ½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₁₀. 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?

Code：Mathematica

(*读取文件*)
namefile = Import["words.txt"];
(*提取双引号里面的单词*)
namelist = StringCases[namefile, "\"" ~~ (x : LetterCharacter ..) ~~ "\"" -> x];
(* 求每个单词的和*)
k = Plus @@ (Flatten[ToCharacterCode@Characters[#]] - 64) & /@ namelist;
(*统计每个单词出现次数*)
Count[k, #] & /@ Table[(n (n + 1))/2, {n, 1, 20}]
(*求和*)
Total@%

Problem 43:

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

• d₂d₃d₄=406 is divisible by 2
• d₃d₄d₅=063 is divisible by 3
• d₄d₅d₆=635 is divisible by 5
• d₅d₆d₇=357 is divisible by 7
• d₆d₇d₈=572 is divisible by 11
• d₇d₈d₉=728 is divisible by 13
• d₈d₉d₁₀=289 is divisible by 17

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

Code：Python

#法一
#输出全排列(yield)
def QPL(m_list):
    if len(m_list) == 1:
        yield m_list
    for i in range(len(m_list)):
        restlist = m_list[0:i]+m_list[i+1:]
        for subres in QPL(restlist):
            yield [m_list[i]]+subres;


sum = 0;
divide = [2,3,5,7,11,13,17]
for t in QPL(range(0,10)):
    flag = True
    for i in range(2,9):
        #判断这三位是否能被divide的对应数整除
        if mod(int(''.join(map(str,t[i-1:i-1+3]))),divide[i-2]) != 0:
            flag = False
            break;
    if flag:
        sum += int(''.join(map(str,t)))
print sum
#############################################################
#法二
####首先筛选出可以被各个指定数整除的不重复的三位数
divide = [2,3,5,7,11,13,17]
pool = [[] for i in range(0,7)]
for i in range(0,1000):
    a = i // 100
    b = mod(i//10,10)
    c = mod(i,10)
    if a != b !=c != a:
        for k in range(0,7):
            if mod(i,divide[k])==0:
                pool[k].append([a,b,c])

#迭代计算，采用生成器
def solve(curlist):
    #长度为9，说明全部这是满足条件的一组
    if len(curlist) == 9:
        yield curlist
        return
    next_idx = len(curlist)-2;
    #找出前两位和前面匹配的三位数
    next_pool = filter(\
          lambda x:x[0]==curlist[-2] and \
                   x[1]==curlist[-1],\
          pool[next_idx])
    #找出第三位和之前的数都没重复的三位数
    next_pool = filter(lambda x:x[-1] not in curlist,next_pool)
    for i in range(0,len(next_pool)):
        curlist.append(next_pool[i][-1])
        for temp in solve(curlist):
            yield temp
        curlist[-1:]=[]

sum = 0;
for i in range(0,len(pool[0])):
    for result in solve(pool[0][i]):
        #找出d1
        digist_left = filter(lambda x:x not in result,range(0,10));
        result[0:0] = digist_left
        sum += int(''.join(map(str,result)))

print sum

Problem 44:Pentagon numbers

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₄ + P₇ = 22 + 70 = 92 = P₈. 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 = |Pk – Pj| is minimised; what is the value of D?

Code：Python

#法一：
def IsPentagonNumber(n):
    k = (1+sqrt(1+24*n))/6;
    if k == int(k):
        return True
    else:
        return False

found = False;
i = 2;
while not found:
    t1 = i*(3*i-1)/2
    for j in range(1,i):
        t2 = j*(3*j-1)/2
        if IsPentagonNumber(t1+t2) and IsPentagonNumber(abs(t1-t2)):
            found = True
            print abs(t1-t2)
            break
    i += 1

#法二：
pre_list = [n*(3*n-1)/2 for n in xrange(1,3000)]
s = set(pre_list)#用集合！！
for i in s:
    for j in s:
        if j > i: continue
        if (i+j) in s and abs(i-j) in s:
            abs(i-j)

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 T₂₈₅ = P₁₆₅ = H₁₄₃ = 40755.

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

Code：Python

def IsPentagonNumber(n):
    k = (1+sqrt(1+24*n))/6;
    if k == int(k):
        return True
    else:
        return False

i = 144
while not IsPentagonNumber(i*(2*i-1)):
    i += 1    
print i*(2*i-1)

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²
15 = 7 + 2×2²
21 = 3 + 2×3²
25 = 7 + 2×3²
27 = 19 + 2×2²
33 = 31 + 2×1²

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?

Code：Mathematica

Goldbach[n_] := Length@Select[n - 2*Range[1, Sqrt[n/2]]^2, PrimeQ] != 0
NestWhile[# + 2 &, 35, Goldbach[#] || PrimeQ[#] &]

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² × 7 × 23

645 = 3 × 5 × 43

646 = 2 × 17 × 19.

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

Code：Mathematica

(*惰性编程，计算每个数有多少个不同的质因数*)
GetDistinFactor[n_] := GetDistinFactor[n] = Length@Select[FactorInteger[n], #[[1]] != n &]
(*暴力迭代*)
NestWhile[# + 1 &, 1, 
   GetDistinFactor[#]     != 4 || 
   GetDistinFactor[# + 1] != 4 || 
   GetDistinFactor[# + 2] != 4 || 
   GetDistinFactor[# + 3] != 4 &]

Problem 48:Self powers

The series, 1¹ + 2² + 3³ + … + 10¹⁰ = 10405071317.

Find the last ten digits of the series, 1¹ + 2² + 3³ + … + 1000¹⁰⁰⁰.

Code：Mathematica

IntegerDigits[Sum[i^i, {i, 1, 1000}]][[-10 ;;]] // FromDigits

Code：Python

sum = 0
for i in range(1,1001):
    sum += i**i
print mod(sum,10000000000)

Code：C++

for(int i = 1;i <= 1000;i++)
{
	unsigned long long product_t = 1;
	for(int j = 1;j <= i;j++)
	{
		product_t = (product_t*i)%10000000000;
	}
	sum = (sum+product_t)%10000000000;
}
cout<<sum;

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?

Code：Python

#判断是不是质数
def isPrime(n):
    if n <= 1:
        return False
    for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

#获取排好序的列表，比如1542就会返回1,2,4,5
def GetDigist(n):
    return sorted(list(str(n)))

#生成1000-9999的质数表    
primelist = []
for i in range(1000,10000):
    if isPrime(i):
        primelist.append(i)

#计算
for i in range(0,len(primelist)):
    for j in range(0,i):
        a = primelist[i]
        b = primelist[j]
        if GetDigist(a) != GetDigist(b):
            continue
        
        c = a + (a - b)
        if c > 9999 or not isPrime(c):
            continue
        
        if GetDigist(a)==GetDigist(c):
            print a,b,c

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?

Code：Python

#判断是不是质数
def isPrime(n):
    if n <= 1:
        return False
    for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True
#生成积分表
sum = 0
prime_list = []
for i in xrange(2,1000000):
    if isPrime(i):
        sum += i
        prime_list.append(sum)
    if sum > 1000000:
        break
#去掉最后一个大于1000000的值
prime_list[-1:]=[]

#生成器，只为取第一个值
def GetConsecutivePrimeSum():
    for span in xrange(len(prime_list)-1,0,-1):
        for begin_p in range(0,len(prime_list)-span):
            sum = prime_list[begin_p+span]-prime_list[begin_p];
            if isPrime(sum):
                yield sum
#取生成器的第一个值
answer = GetConsecutivePrimeSum();
print answer.next()

Code：Mathematica

(*maxidx=547*)
maxidx = NestWhile[# + 1 &, 1, Total@Table[Prime[i], {i, 1, #}] < = 1000000 &]
(*建立积分表*)
IntegrateList = FoldList[Plus, 2, Table[Prime[i], {i, 2, maxidx - 1}]];

Flag = False;
span = maxidx - 1;

While[!Flag,
 	For[ori = 1, ori <= maxidx - span - 1, ori++,
        If[PrimeQ[IntegrateList[[ori + span]] - IntegrateList[[ori]]],      
           Print[IntegrateList[[ori + span]] - IntegrateList[[ori]]]; 
            Flag = True]
    	  ]
       span--;
 ]

【完】

本文内容遵从CC版权协议，转载请注明出自http://www.kylen314.com