好吧，我又来写这种没人看的东西了。。。。

本来说好乖乖写论文的。。但是我一无聊，就想找人打麻将，一旦找不到人打麻将。。我就去刷Euler题，然后刷着刷着。。。有人我搞出10道题了。。。好，这次说好了。。。乖乖写论文。。。而且我已经预感到后面的题好像继续变难了。。所以决定论文写完之前，不再碰Euler题了。。。再做剁手！

Problem 61:Cyclical figurate numbers

Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:

Triangle	P3,n=n(n+1)/2	1, 3, 6, 10, 15, …
Square	P4,n=n2	1, 4, 9, 16, 25, …
Pentagonal	P5,n=n(3n-1)/2	1, 5, 12, 22, 35, …
Hexagonal	P6,n=n(2n-1)	1, 6, 15, 28, 45, …
Heptagonal	P7,n=n(5n-3)/2	1, 7, 18, 34, 55, …
Octagonal	P8,n=n(3n-2)	1, 8, 21, 40, 65, …

The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.

1. The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first).
2. Each polygonal type: triangle (P_3,127=8128), square (P_4,91=8281), and pentagonal (P_5,44=2882), is represented by a different number in the set.
3. This is the only set of 4-digit numbers with this property.

Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.

Code：Python

def test(num,idx):
    if   idx == 3:t = (sqrt(1+8*num)-1)/2
    elif idx == 4:t = sqrt(num)
    elif idx == 5:t = (sqrt(1+24*num)+1)/6
    elif idx == 6:t = (sqrt(1+8*num)+1)/4
    elif idx == 7:t = (sqrt(9+40*num)+3)/10
    return t == int(t)
    
def figure(num,flag,idx):
    flag[idx] = num;
    if flag.count(0) == 0 and mod(num,100)==(flag[5]//100):
        print flag,sum(flag)
        return
    for mowei in range(10,100):
        nn = mod(num,100)*100+mowei
        for i in range(7,2,-1):
            if flag[i-3] == 0 and test(nn,i):
                figure(nn,flag,i-3)
                flag[i-3]=0
                
for i in range(21,22):
    Octagonal = i*(3*i-2)
    if mod(Octagonal,100) >= 10:
        figure(Octagonal,[0,0,0,0,0,0],5)

Problem 62:

The cube, 41063625 (345³), can be permuted to produce two other cubes: 56623104 (384³) and 66430125 (405³). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

Code：Python

db =  {};
i = 1;
while True:
    key = list(str(i**3))
    key.sort()
    key = ''.join(key)
    if db.get( key ) == None:
        db[key] = [1,i**3]
    else:
        db[key][0] += 1
        if db[key][0] == 5:
            print db[key][1]
            break
    i += 1

Problem 63:Powerful digit counts

The 5-digit number, 16807=7⁵, is also a fifth power. Similarly, the 9-digit number, 134217728=8⁹, is a ninth power.

How many n-digit positive integers exist which are also an nth power?

Code：Python

counter = 0
for n in range(1,22):
    counter += 10-int(ceil(10**((n-1)/n)))
print counter

Code：Mathematica

Total@Table[10 - Ceiling[10^((n - 1)/n)], {n, 1, 21}]

Problem 64:Odd period square roots

【卧槽，这题目能再长再难敲一点？！英文有毛线人看啊！！】

All square roots are periodic when written as continued fractions and can be written in the form:

\(\sqrt{N}=a_0+\dfrac{1}{a_1+\dfrac{1}{a_2+\dfrac{1}{a_3+…}}}\)

For example, let us consider \(\sqrt{23}\):

\(\sqrt{23}=4+\sqrt{23}-4=4+\dfrac{1}{\dfrac{1}{\sqrt{23}-4}}=4+\dfrac{1}{1+\dfrac{\sqrt{23}-3}{7}}\)

If we continue we would get the following expansion:

\(\sqrt{23}=4+\dfrac{1}{1+\dfrac{1}{3+\dfrac{1}{1+\dfrac{1}{8+…}}}}\)

The process can be summarised as follows:

\(a_0=4,\dfrac{1}{\sqrt{23}-4}=\dfrac{\sqrt{23}+4}{7}=1+\dfrac{\sqrt{23}-3}{7}\)

\(a_1=1,\dfrac{7}{\sqrt{23}-3}=\dfrac{7(\sqrt{23}+3)}{14}=3+\dfrac{\sqrt{23}-3}{2}\)

\(a_2=3,\dfrac{2}{\sqrt{23}-3}=\dfrac{2(\sqrt{23}+3)}{14}=1+\dfrac{\sqrt{23}-4}{7}\)

\(a_3=1,\dfrac{7}{\sqrt{23}-4}=\dfrac{7(\sqrt{23}+4)}{7}=8+\sqrt{23}-4\)

\(a_4=8,\dfrac{1}{\sqrt{23}-4}=\dfrac{\sqrt{23}+4}{7}=1+\dfrac{\sqrt{23}-3}{7}\)

\(a_5=1,\dfrac{7}{\sqrt{23}-3}=\dfrac{7(\sqrt{23}+3)}{14}=3+\dfrac{\sqrt{23}-3}{2}\)

\(a_6=3,\dfrac{2}{\sqrt{23}-3}=\dfrac{2(\sqrt{23}+3)}{14}=1+\dfrac{\sqrt{23}-4}{7}\)

\(a_7=1,\dfrac{7}{\sqrt{23}-4}=\dfrac{7(\sqrt{23}+4)}{7}=8+\sqrt{23}-4\)

It can be seen that the sequence is repeating. For conciseness, we use the notation \(\sqrt{23}\) = [4;(1,3,1,8)], to indicate that the block (1,3,1,8) repeats indefinitely.

The first ten continued fraction representations of (irrational) square roots are:

\(\sqrt{2}\)=[1;(2)], period=1
\(\sqrt{3}\)=[1;(1,2)], period=2
\(\sqrt{5}\)=[2;(4)], period=1
\(\sqrt{6}\)=[2;(2,4)], period=2
\(\sqrt{7}\)=[2;(1,1,1,4)], period=4
\(\sqrt{8}\)=[2;(1,4)], period=2
\(\sqrt{10}\)=[3;(6)], period=1
\(\sqrt{11}\)=[3;(3,6)], period=2
\(\sqrt{12}\)= [3;(2,6)], period=2
\(\sqrt{13}\)=[3;(1,1,1,1,6)], period=5

Exactly four continued fractions, for N ≤ 13, have an odd period.

How many continued fractions for N ≤ 10000 have an odd period?

Code：Python

#方法一：API
def GetLength(n):
    if int(sqrt(n))==sqrt(n):
        return 0
    a = 0
    b = 1
    a0 = int(a+b*sqrt(n))
    temp = []
    while True:
        k = int(a+b*sqrt(n))
        if [k,round(a,4),round(b,4)] in temp:
            idx = temp.index([k,round(a,4),round(b,4)])
            return len(temp)-idx
        temp.append([k,round(a,4),round(b,4)])     
        a,b = (a-k)/((a-k)**2-b**2*n),-b/((a-k)**2-b**2*n)

Code：Python

#方法二：
def GetLength(S):
    m = 0
    d = 1
    a0 = int(sqrt(S))
    a = int(sqrt(S))
    length = 0
    while a != a0*2:
        m = a*d-m
        d = (S-m*m)/d
        a = int((m+sqrt(S))/d)
        length += 1
    return length
    

counter = 0
for i in range(2,10000+1):
    if int(sqrt(i)) != sqrt(i):     
        if mod(GetLength(i),2)==1:
            counter += 1
print counter

Problem 65:Convergents of e

【为毛这些题目都那么难敲！！】

The square root of 2 can be written as an infinite continued fraction.

\(\sqrt{2}=1+\dfrac{1}{2+\dfrac{1}{2+\dfrac{1}{2+\dfrac{1}{2+…}}}}\)

The infinite continued fraction can be written, √2 = [1;(2)], (2) indicates that 2 repeats ad infinitum. In a similar way, √23 = [4;(1,3,1,8)].

It turns out that the sequence of partial values of continued fractions for square roots provide the best rational approximations. Let us consider the convergents for √2.

\(1+\dfrac{1}{2}=\dfrac{2}{3}\)

\(1+\dfrac{1}{2+\dfrac{1}{2}}=\dfrac{7}{5}\)

\(1+\dfrac{1}{2+\dfrac{1}{2+\dfrac{1}{2}}}=\dfrac{17}{12}\)

\(1+\dfrac{1}{2+\dfrac{1}{2+\dfrac{1}{2+\dfrac{1}{2}}}}=\dfrac{41}{29}\)

Hence the sequence of the first ten convergents for √2 are:

1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, …
What is most surprising is that the important mathematical constant,
e = [2; 1,2,1, 1,4,1, 1,6,1 , … , 1,2k,1, …].

The first ten terms in the sequence of convergents for e are:

2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, …

The sum of digits in the numerator of the 10th convergent is 1+4+5+7=17.

Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e.

Code：Python

def getxunhuanjie(n):
    result = []
    k = 2
    while len(result) < n:
        result += [1,k,1]
        k += 2
    return result[0:n]

result = getxunhuanjie(99)
a,b = 1,result[-1]
for i in range(len(result)-2,-1,-1):
    a,b=b,a+b*result[i]
    
print sum(map(int,list(str(a+2*b))))

Problem 66:Diophantine equation

Consider quadratic Diophantine equations of the form:

x² – Dy² = 1

For example, when D=13, the minimal solution in x is 649² – 13×180² = 1.

It can be assumed that there are no solutions in positive integers when D is square.

By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we obtain the following:

3² – 2×2² = 1
2² – 3×1² = 1
9² – 5×4² = 1
5² – 6×2² = 1
8² – 7×3² = 1

Hence, by considering minimal solutions in x for D ≤ 7, the largest x is obtained when D=5.

Find the value of D ≤ 1000 in minimal solutions of x for which the largest value of x is obtained.

翻译：
考虑如下形式的二次丢番图方程：

x² – Dy² = 1

例如当 D=13时, x 的最小解是 649² – 13×180² = 1.

可以认为当D时平方数时方程无正整数解。

通过寻找当D = {2, 3, 5, 6, 7}时 x 的最小解，我们得到：
3² – 2×2² = 1
2² – 3×1² = 1
9² – 5×4² = 1
5² – 6×2² = 1
8² – 7×3² = 1

因此对于D ≤ 7, x 的最小解的最大值在D=5时取到。

找出D ≤ 1000中使得 x 的最小值取到最大的D的值。

思路:
这道题昨晚发现是科普题。。。感觉不在网上找资料，暴解的人全都死了。。。反正我一开始暴力解决，然后发现尼马根本算不出来吗，即便只是算1到1000。。。

然后上网找丢潘图方程Diophantine equation的解的资料，然后找到了很多很多东西，发现原来有硕士毕设论文就是做这个的(相关的)，有兴趣的可以去找找；反正知道我找到了Pell方程，我看到求解的过程，马上就知道我肯定找对了！！因为我看到要利用\(\sqrt{n}\)的连分数形式来求解的方法了！！！所以前面的题中的方法终于要用上了！！

先把资料先上吧，英文维基娘和中文维基娘，虽然我知道包括我在内的人都喜欢看中文的，还虽然看中文的足够解决这道题了，但是你们看一下两家的进度条就知道根本不是一个信息量。。所以我后来又去补完了英文维基娘。。。

说正题，反正根据维基娘所讲，要解题目中这个方程，我们先要解出\(\sqrt{D}\)的连分数下的各个逼近值\(\dfrac{p_i}{q_i}\)【为此我们需要求的循环节，然后不断增加连分数的深度，得到更高精度的\(\sqrt{D}\)的分数表示形式】，然后前人告诉我们，只要找到第一组\(p_i,q_i\)满足题目中的丢潘图公式，我们就可以停止计算了，因为这个必然就是x最小的那组解，而后面的所有解的递归方法虽然维基娘也给出，但是跟我们这道题没关系了。

最后还是再说一句，有兴趣的同学真的可以去看看丢潘图和佩尔方程的资料，这里面好多有意思的东西，搞到我都想为其专门写一篇博文了。。。如果水不深，也不至于有硕士靠此毕业啊~

下面代码只要0.3秒即可完成计算。

Code：Python

#获取连分数循环节
def GetXHJ(S):
    m,d = 0,1
    a = a0 = int(sqrt(S))
    result = [a0]
    while a != a0*2:
        m = a*d-m
        d = (S-m*m)/d
        a = int((m+sqrt(S))/d)
        result += [a]
    return result

#生成器，不断返回渐进的连分数
def GetJianjin(LFS):
    idx = 1
    result = [LFS[0]]
    while True:
        a,b = 1,result[idx-1]
        for i in range(idx-2,-1,-1):
            a,b=b,a+b*result[i]
        yield [a,b]
        idx += 1
        result += [LFS[mod(idx-2,len(LFS)-1)+1]]

def GetMinx(D):
    for k in GetJianjin(GetXHJ(D)):
        if k[1]*k[1]-D*k[0]*k[0] == 1:
            return k[1]
    
#main
maxp = -1
maxD = 1
for D in range(5,1001):
    if sqrt(D)==int(sqrt(D)):
        continue
    t = GetMinx(D)
    if t > maxp:
        maxp = t
        maxD = D
print maxD

Problem 67:

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom in triangle.txt (right click and ‘Save Link/Target As…’), a 15K text file containing a triangle with one-hundred rows.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 299 altogether! If you could check one trillion (1012) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

Code：Mathematica

tri = {读入数据};
tri2 = StringSplit[tri, "\n"][[1]];
tri3 = ToExpression[StringSplit[#, " "] & /@ tri2];
For[i = Length[tri3] - 1, i >= 1, i -= 1,
  For[j = 1, j < = Length[tri3[[i]]], j += 1, 
   tri3[[i]][[j]] += Max[{tri3[[i + 1]][[j]], tri3[[i + 1]][[j + 1]]  }]]];
tri3 // Column

Problem 68:Magic 5-gon ring

Consider the following "magic" 3-gon ring, filled with the numbers 1 to 6, and each line adding to nine.

Working clockwise, and starting from the group of three with the numerically lowest external node (4,3,2 in this example), each solution can be described uniquely. For example, the above solution can be described by the set: 4,3,2; 6,2,1; 5,1,3.

It is possible to complete the ring with four different totals: 9, 10, 11, and 12. There are eight solutions in total.

Total	Solution Set
9	4,2,3; 5,3,1; 6,1,2
9	4,3,2; 6,2,1; 5,1,3
10	2,3,5; 4,5,1; 6,1,3
10	2,5,3; 6,3,1; 4,1,5
11	1,4,6; 3,6,2; 5,2,4
11	1,6,4; 5,4,2; 3,2,6
12	1,5,6; 2,6,4; 3,4,5
12	1,6,5; 3,5,4; 2,4,6

By concatenating each group it is possible to form 9-digit strings; the maximum string for a 3-gon ring is 432621513.

Using the numbers 1 to 10, and depending on arrangements, it is possible to form 16- and 17-digit strings. What is the maximum 16-digit string for a "magic" 5-gon ring?

翻译：
考虑如下的“魔术”三角环：该环被1到6的数字填充，并且每一行的和为9。

按照顺时针顺序，从外部节点最小的三个为一组的组开始（该例中为4,3,2），每一组解都可以被唯一描述。例如，上图所示的解可以被描述为集合： 4,3,2; 6,2,1; 5,1,3。

这个环还可以被用四个不同的和来完成。一共有八组解。

和	解
9	4,2,3; 5,3,1; 6,1,2
9	4,3,2; 6,2,1; 5,1,3
10	2,3,5; 4,5,1; 6,1,3
10	2,5,3; 6,3,1; 4,1,5
11	1,4,6; 3,6,2; 5,2,4
11	1,6,4; 5,4,2; 3,2,6
12	1,5,6; 2,6,4; 3,4,5
12	1,6,5; 3,5,4; 2,4,6

将每组解的数字连接起来，可以得到一个9位的字符串；三角环所能形成的最大字符串为432621513。

使用数字1到10，通过不同的安排，可以得到16位或17位的字符串。五角环所能形成的最大的16位的字符串是什么？

思路:
为了方便说明，下面代码中存储10个数的数组下标如下图所示【图懒，手绘别在意】：

其实根据题目要求可以推出好一些性质的，诸如最外边五个数的和必然是5的倍数之类的，但是这些性质对代码优化没啥帮助，故不提；

我们要找出最大的16位字符串，但是我们根本不需要检测全部排列方式或者找出全部符合条件的排列，然后再找出最大的；思考的出发点是，我们可以用Python的生成器生成1~10的全排列，而且我们以前写的全排列生成器是按字典序生成的，所以我们只要让生成器对[9,8,7,6,5,4,3,2,1,10]这个序列按字典序输出，然后逐个检测是否满足题目要求，只要找到一个，那么必然就是最大的！因为可以参考我上图序号的设计，每生成一种全排列，然后按0~9填进数组，那么得到的16位字符串必然也是从大到小排序的！

但是这样其实很不科学，因为我们知道第一位是外圈5个数里面最小的，所以第一位必然小于等于6，加上这个判断条件【在全排列生成器函数里面判断】，算法可以在1秒完成；

但是事实上，其实这道题手算也不是很难的事，因为为了得到最大的16位数，可以假设让最大的6，7，8，9，10放在最外边，然后可以算出每一行的和一概都等于14，填上6后，就可以发现6这一列剩下两个数的和要等于8，只剩下5+3这一可能了，3出现了，然后10就必然要出现了，因为对于10，要得到14只有10+3+1这一种可能，然后顺藤摸瓜就可以得到一组解；虽然这个方法不严谨，但是未尝不是一个锻炼脑子的好方法。。

Code：Python

def QPL(m_list):
    if len(m_list) == 1:
        yield m_list
    for i in range(len(m_list)):
        if len(m_list) == 10 and m_list[i] > 6:
            continue
        restlist = m_list[0:i]+m_list[i+1:]
        for subres in QPL(restlist):
            yield [m_list[i]]+subres;

for k in QPL([9,8,7,6,5,4,3,2,1,10]):
    #k[0]是外圈最小
    if k[0]>k[3] or k[0]>k[5] or k[0]>k[7] or k[0]>k[9]:
        continue

    sum = k[0]+k[1]+k[2]
    if sum == k[3]+k[2]+k[4] and\
       sum == k[5]+k[4]+k[6] and\
       sum == k[7]+k[6]+k[8] and \
       sum == k[9]+k[8]+k[1]:
        print ''.join(map(str,[k[0],k[1],k[2],\
                               k[3],k[2],k[4],\
                               k[5],k[4],k[6],\
                               k[7],k[6],k[8],\
                               k[9],k[8],k[1]]))
        break

Problem 69:Totient maximum

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.

n	Relatively Prime	φ(n)	n/φ(n)
2	1	1	2
3	1,2	2	1.5
4	1,3	2	2
5	1,2,3,4	4	1.25
6	1,5	2	3
7	1,2,3,4,5,6	6	1.1666...
8	1,3,5,7	4	2
9	1,2,4,5,7,8	6	1.5
10	1,3,7,9	4	2.5

It can be seen that n=6 produces a maximum n/φ(n) for n ≤ 10.

Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.

Code：Mathematica

fai[n_] := n*Times @@ ((1 - 1/#) & /@ First /@ FactorInteger[n])
SortBy[ParallelTable[{n, n/fai[n]}, {n, 2, 1000000}], Last]//Last

Problem 70:Totient permutation

Euler’s Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.

The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.

Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

Find the value of n, 1 < n < 10⁷ , for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

Code：Python

#判断乘积是不是符合条件
def test(i,j):
    k1 = sorted(list(str((i-1)*(j-1))))
    k2 = sorted(list(str(i*j)))
    return k1 == k2

#筛选质数    
T = 10000000
primelist = [1]*T
primelist[0]=primelist[1]=0
for i in range(2,T):
    if primelist[i] != 1:
        continue
    for j in range(i*2,T,i):
        primelist[j] = 0
    
idx = -1
minn = 9999999
for i in xrange(3,T,2):
    if i > 3162:
        break
    if primelist[i] != 1:
        continue
    for j in range(i+2,int(T/i),2):
        if primelist[j] != 1:
            continue
        if test(i,j):
            if i*j/(i-1)/(j-1) < minn:
                minn = i*j/(i-1)/(j-1)
                idx = i*j
print idx

【完】

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