嗯~总算搞完了，其实发现复习以前做过的题也挺有意思的，至少很多题我现在拿来写博客的时候就会静下心来想会不会有更高的方法呢~什么的。。。【其实我才不会告诉你中间有几题我以前的代码找不到了，现在被迫重写。。】

嘛~第四弹，离赶上我自己原有进度还有两弹~而且现在博文这里不写完实在不好意思去EP上刷题。。。

题目这里开始明显和前面有难度上的分界线了，但是虽然这么说，但是这10道题目顶多还是只能称之为值得讨论研究，还不能算难。。只要你多思考一点点，就可以让你的程序结果很快的跑出来，因为这里开始题目暴搜解法已经开始表示吃紧了。。

Problem 31:Coin sums

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

Code：Python

def Sol(money,coinlist):
    if len(coinlist) == 1:
        return 1
    sum = 0;
    for i in range(len(coinlist)):
        if money-coinlist[i] == 0:
            sum += 1
        elif money-coinlist[i] > 0:
            sum += Sol(money-coinlist[i],coinlist[:i+1])
    return sum
print Sol(200,[1,2,5,10,20,50,100,200])

Problem 32:Pandigital products

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, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

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 cal(ml):
    a = 10*ml[0]+ml[1];
    b = 100*ml[2]+10*ml[3]+ml[4];
    c = 1000*ml[5]+100*ml[6]+10*ml[7]+ml[8];
    return a*b == c

def cal2(ml):
    a = ml[0];
    b = 1000*ml[1]+100*ml[2]+10*ml[3]+ml[4];
    c = 1000*ml[5]+100*ml[6]+10*ml[7]+ml[8];
    return a*b == c

sum = 0;
prolist = [];
for pql in QPL([1,2,3,4,5,6,7,8,9]):
    if cal(pql) == True:
        t = 1000*pql[5]+100*pql[6]+10*pql[7]+pql[8];
        if t not in prolist:
            sum += t;
            prolist.append(t)
    if cal2(pql) == True:
        sum += 1000*pql[5]+100*pql[6]+10*pql[7]+pql[8];
        if t not in prolist:
            sum += t;
            prolist.append(t)
print sum

Problem 33:

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.

Code：Python

result_list = [];
for i in range(11,100):
    for j in range(i+1,100):    
        if mod(i,10)==0 or mod(j,10)==0 :
            continue
        a = i // 10
        b = mod(i,10)
        c = j // 10
        d = mod(j,10)
        if (i/j == a/c and b == d) or\
           (i/j == a/d and b == c) or\
           (i/j == b/c and a == d) or\
           (i/j == b/d and a == c):
            result_list.append([i,j])
print reduce(lambda x,y:x*y,map(lambda x:x[1]/x[0],result_list))

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.

翻译：
145 是一个奇怪的数字, 因为 1! + 4! + 5! = 1 + 24 + 120 = 145.

找出所有等于各位数字阶乘之和的数字之和。

注意: 因为 1! = 1 和 2! = 2 不是和的形式，所以它们不算在内。

思路:
之前也用过类似的方法，说先要找到历遍的上限，n位数最大值为10ⁿ-1，而其各个数字阶乘和最大可能为n9!=362880n，所以：

最高位数为7位。

Code：Mathematica

Select[Range[10, n*9! /. %],Plus @@ (#! & /@ IntegerDigits[#]) == # &]//Total

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?

Code：Mathematica

(*判断是否是循环质数：*)
IsCircularPrimes[t_] := 
  Count[PrimeQ@FromDigits[#] & /@ (RotateLeft[IntegerDigits[t], #] & /@
        Range[0, Length[IntegerDigits[t]] - 1]), False] == 0;
(*法一：*)
Select[Range[1, 1000000], IsCircularPrimes] // Length
(*法二：*)
SieveFun[t_] := Count[IntegerDigits[t], Except[1 | 3 | 7 | 9]] == 0

tSieve = Select[Range[1, 1000000], SieveFun];
Select[tSieve, IsCircularPrimes] // Length + Length[{2,5}]

Problem 36:Double-base palindromes

The decimal number, 585 = 1001001001₂ (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.)

Code：Mathematica

(*法一*)
Select[Range[1, 1000000], 
       IntegerDigits[#, 2] == Reverse[IntegerDigits[#, 2]] && 
       IntegerDigits[#] == Reverse[IntegerDigits[#]] &
      ]
Total[%]

(*法二*)
(*扫描1~1024的二进制数*)
t = IntegerDigits[#, 2] & /@ Range[1024];
(*判断十进制数是不是回文数*)
IsPalindromes[n_] := IntegerDigits[n] == Reverse[IntegerDigits[n]];
(*筛选ab->abba情况*)
Select[t, IsPalindromes[FromDigits[#~Join~Reverse[#], 2]] && #[[1]] == 1 &];
FromDigits[#~Join~Reverse[#], 2] & /@ %;
r1 = Total[%];
(*筛选ab->aba情况*)
Select[t,IsPalindromes[FromDigits[#[[;; -2]]~Join~Reverse[#], 2]] && #[[1]] == 1 &];
FromDigits[#[[;; -2]]~Join~Reverse[#], 2] & /@ %;
r2 = Total[%];
(*计算总和*)
r1 + r2

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.

Code：Mathematica

GetTruncate[n_] :=
         (Take[IntegerDigits@n, {#, -1}] & /@ Range[Length@IntegerDigits@n])~Join~
         (Take[IntegerDigits@n, {1, #}] & /@ Range[Length@IntegerDigits@n - 1])

IsTruncatablePrimes[n_] := 
      (Select[FromDigits /@ GetTruncate[n], ! PrimeQ[#] &] // Length) == 0
(*法一*)
Counter = 0;
L = {};
i = 11;
While[Counter < 11,
      If[IsTruncatablePrimes[i], Counter += 1; AppendTo[L, i]];
      i += 1;
      ]
(*法二*)
SieveFun[t_] := Count[IntegerDigits[t][[2 ;; -2]], Except[1 | 3 | 7 | 9]] == 0
Counter = 0;
L = {};
i = 11;
While[Counter < 11,
      If[SieveFun[i] && IsTruncatablePrimes[i], Counter += 1; 
      AppendTo[L, i]];
      i += 1;
     ]
(*法三*)
Counter = 0;
L = {};
i = 3;
While[Counter < 7,
      t = Select[FromDigits /@ Tuples[{1, 3, 7, 9}, i], 
      IsTruncatablePrimes];
      Counter += Length[t];
      AppendTo[L, t];
      i += 1;
      ]

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?

Code：Mathematica

Select[Range[9234, 9487],Sort@(IntegerDigits[#]~Join~IntegerDigits[2 #]) == Range[1,9] &]
Max[%]

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?

翻译：
如果p是一个直角三角形的周长，三角形的三边长{a,b,c}都是整数。对于p = 120一共有三组解：

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

对于1000以下的p中，哪一个能够产生最多的解？

思路:
这个是之前第九题里面推出来的结论，下面将其一般化：
所以代码就比较简单了~

Code：Python

maxp = -1;
max_counter = 0;
for p in range(1,1001):
    counter = 0;
    for a in range(1,int(p-p/sqrt(2))):
        b = p/2*(p-2*a)/(p-a);
        if b == int(b):
            counter += 1;
    if max_counter < counter:
        maxp = p;
        max_counter = counter
print maxp

Problem 40:Champernowne’s constant

An irrational decimal fraction is created by concatenating the positive integers:

0.12345678910 1112131415161718192021…

It can be seen that the 12^th digit of the fractional part is 1.

If d_n represents the n^th digit of the fractional part, find the value of the following expression.

d₁ × d₁₀ × d₁₀₀ × d₁₀₀₀ × d₁₀₀₀₀ × d₁₀₀₀₀₀ × d_1000000

Code：Mathematica

t = ToString@FromDigits@Flatten@IntegerDigits@Range[1, 1000000];
Times @@ ToExpression@(StringTake[t, {#}] & /@ Table[10^i, {i, 0, 6}])

【完】

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