首页 > Project Euler > Project Euler个人解答(Problem 61~70)

Project Euler个人解答(Problem 61~70)

2014年1月4日 发表评论 阅读评论

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

本来说好乖乖写论文的。。但是我一无聊,就想找人打麻将,一旦找不到人打麻将。。我就去刷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 (P3,127=8128), square (P4,91=8281), and pentagonal (P5,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.

翻译:
三角形数,四角形数,五角形数,六角形数,七角形数和八角形数都是定形数,他们分别由以下公式产生:

三角形数 P3,n=n(n+1)/2 1, 3, 6, 10, 15, ...
四角形数 P4,n=n2 1, 4, 9, 16, 25, ...
五角形数 P5,n=n(3n-1)/2 1, 5, 12, 22, 35, ...
六角形数 P6,n=n(2n-1) 1, 6, 15, 28, 45, ...
七角形数 P7,n=n(5n-3)/2 1, 7, 18, 34, 55, ...
八角形数 P8,n=n(3n-2) 1, 8, 21, 40, 65, ...

三个四位数形成的有序集合: 8128, 2882, 8281,有三个有趣的性质:

  1. 这个集合是循环的:每个数的后两位数是下一个数的前两位数,包括第三个和第一个的关系。
  2. 三种定形数中的每一种都能被这三个数中的一个不同的数代表:三角形数 (P3,127=8128), 四角形数 (P4,91=8281), 和五角形数 (P5,44=2882)。
  3. 这是唯一具有以上性质的四位数的集合。

找出唯一的一个六个四位数的循环集合,使得从三角形数到八角形数中的每一种都能由该集合中的一个不同的数代表。

求这个集合中元素之和。

思路:
这种题目一般要扫描搜索的话,一般都是从步进幅度最大的作为起点的,这里显然是\(3n^2\)的数量级的八角数作为起点啦,反正我就是写了一个递归调用,对于每一个四位数abcd,然后扫描cd10到cd99,如果满足它是m角数,然后就继续递归;这里从10开始而不是00开始是因为如果cd07通过的话,那么下一次递归不就变成从07XX开始了么?这不是四位数;

几点要说,第一自然不用说,用一个简单的test函数可以快速判断是不是m角数,这个之前题目用过几次了;其次,递归检测我也是先检测是不是八角数,然后七角数。。。最后才是三角数;

下面python代码0.2s出结果。

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 (3453), can be permuted to produce two other cubes: 56623104 (3843) and 66430125 (4053). 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.

翻译:
立方数 41063625 (3453) 通过排列可以得到两个另外的立方数: 56623104 (3843) 和 66430125 (4053)。 实际上41063625是最小的三个(不多不少)排列是立方数的立方数。

找出最小的立方数,其五个(不多不少)排列是立方数。

思路:
其实这是数据结构的胜利!!论一门支持字典的编程语言的优越性~

思路很简单,每次对于i3,将其排好序后作为一个字典的key,如果两个数排好序后完全一样,那么说明这两个数是有相同的数字组成的。

字典里面每一项存储两个值,出现次数和最小的i3,也就是说不断增加i3,算出key,在字典里面查询,如果这个键值有了,那么出现次数加1,如果没出现,那么新建一个项,出现次数为1,然后把这个i3记录下来;

直到某一个出现次数为5的时候,把最小的那个i3显示出来就是了~

下面代码0.08s完成。

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=75, is also a fifth power. Similarly, the 9-digit number, 134217728=89, is a ninth power.

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

翻译:
五位数16807=75 同时也是一个数的五次方。类似的,九位数 134217728=89,同时也是一个数的九次方。

有多少n位正整数同时也是某个数的n次方?

思路:
这种题目。。。手算都行。。。根本没必要编程

一个n位数k必然满足:

\(10^{n-1}\leq k=a^{n}<10^{n}\)

所以有:

10^\((\dfrac{n-1}{n})\)≤a<10

所以为了让a至少存在一个值,可以计算出来10^(20/21)=8.96151, 10^(22/22)=9.00628,所以也就确定出n的范围来了;

下面代码只要0.0001秒就可以算完了。。

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?

翻译:
所有的平方根写作连分数的时候都是周期性的,并且可以写成如下形式:

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

例如\(\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}}\)

如果继续下去我们得到如下展开式:

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

这个过程可以被总结如下:

\(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\)

可以看出这个序列是重复的。简明起见,我们用 \(\sqrt{23}\) = [4;(1,3,1,8)], 来表示(1,3,1,8)这个部分不断重复出现。

前十个无理平方根的连续分数表示为:
\(\sqrt{2}\)=[1;(2)], 周期=1
\(\sqrt{3}\)=[1;(1,2)], 周期=2
\(\sqrt{5}\)=[2;(4)], 周期=1
\(\sqrt{6}\)=[2;(2,4)], 周期=2
\(\sqrt{7}\)=[2;(1,1,1,4)], 周期=4
\(\sqrt{8}\)=[2;(1,4)], 周期=2
\(\sqrt{10}\)=[3;(6)], 周期=1
\(\sqrt{11}\)=[3;(3,6)], 周期=2
\(\sqrt{12}\)= [3;(2,6)], 周期=2
\(\sqrt{13}\)=[3;(1,1,1,1,6)], 周期=5

可以看出对于 N ≤ 13, 有四个连分数的周期是奇数。

对于 N ≤ 10000,有多少连分数的周期是奇数?

思路:
这道题一种很简单的思路就是,我们可以把\(\sqrt{S}\)看成\(a+b\sqrt{S}\),然后不断迭代,从\(a_n+b_n\sqrt{S}\)推导出\(a_{n+1}+b_{n+1}\sqrt{S}\),方法如下:

本质上递归过程是:\(a_{n}+b_{n}\sqrt{S}=\underbrace{\lfloor a_{n}+b_{n}\sqrt{S}\rfloor}_{k} + \frac{1}{a_{n+1}+b_{n+1}\sqrt{S}}\)

所以:
\(\begin{eqnarray*}a_{n+1}+b_{n+1}\sqrt{S} & = &\dfrac{1}{a_{n}+b_{n}\sqrt{S}-k} \\& = & \dfrac{a_{n}-k-b_{n}\sqrt{S}}{(a_n-k)^2-b^2_nS}\\& = & \dfrac{a_{n}-k}{(a_n-k)^2-b^2_nS}+\dfrac{-b}{(a_n-k)^2-b^2_nS}\sqrt{S}\end{eqnarray*}\)
所以有:
\(\left\{\begin{array}{ll}a_{n+1}=\dfrac{a_{n}-k}{(a_n-k)^2-b^2_nS}\\b_{n+1}=\dfrac{-b}{(a_n-k)^2-b^2_nS}\end{array}\right.\)

所以只要不断这么迭代,记录下三元组\(\left\{k,a_n,b_n\right\}\),直到出现重复,那么说明循环节出现;

但是上述方法有一个很致命的缺陷,就是这里的\(a_n,b_n\)不是整数,所以你存下来结果,由于计算精度,越往后面计算迭代会让误差变大,之后你怎么说15.00000023就是15呢?那么你又怎么告诉计算机三元组开始重复了呢?是吧;

后来我在维基娘那里又找到了答案~它的思想是:

我们不把每次迭代的数看成\(a_n+b_n\sqrt{S}\),而是:\(\dfrac{\sqrt{S}+m_n}{d_n}\),也就是一开始初始化的时候\(m_0=0\)\(d_0=1\)而已,然后再定义每次迭代的整数部分为\(a_n=\lfloor\dfrac{\sqrt{S}+m_n}{d_n}\rfloor\),所以有:\(a_0=\lfloor\sqrt{S}\rfloor\),这样做有什么好处呢?好处有两个,第一个,这里可以保证\(m_n\),\(d_n\),\(a_n\)全是整数,第二个我们等一下再讲;

所以迭代就变成:

\(\begin{eqnarray*}\dfrac{\sqrt{S}+m_n}{d_n} & = &a_n+\dfrac{\sqrt{S}+m_n}{d_n}-a_n \\& = & a_n+\dfrac{\sqrt{S}+m_n-a_nd_n}{d_n}\\&=&a_n+\dfrac{1}{\dfrac{d_n}{\sqrt{S}+m_n-a_nd_n}}\end{eqnarray*}\)

其中:

\(\begin{eqnarray*}\dfrac{d_n}{\sqrt{S}+m_n-a_nd_n} & = &\dfrac{d_n(\sqrt{s}-m_n+a_nd_n)}{S-(m_n-a_nd_n)^2} \\& = & \dfrac{\sqrt{s}+(a_nd_n-m_n)}{\dfrac{S-(m_n-a_nd_n)^2}{d_n}}=\dfrac{\sqrt{S}+m_{n+1}}{d_{n+1}}\end{eqnarray*}\)

所以得到迭代公式(也就是维基娘上面那个):
\(\left\{\begin{array}{ll}m_{n+1}=a_nd_n-m_n\\d_{n+1}=\dfrac{S-(m_n-a_nd_n)^2}{d_n}=\dfrac{S-m_{n+1}^2}{d_n}\end{array}\right.\)

好处二是啥?其实维基娘上面有说,根据这篇论文里面的推论3.3(Corollary 3.3)证明了,迭代停止的条件是:当出现\(a_i=2a_0\)的时候,所以这里就不用像上面那个方法一样存下三元组,还要用判断是否存在这种慢函数。。

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.

翻译:
2的平方根可以写作无限连分数:

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

这个无限连分数可以写作, √2 = [1;(2)], (2) 表示2无限循环出现。类似的,√23 = [4;(1,3,1,8)]。

事实证明平方根的连分数序列提供了最好的有理数近似值。让我们考虑√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}\)

因此 √2 的收敛项中的前十项是:

1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, ...
更令人惊奇的是一个重要的数学常数:
e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...].

e 的收敛项序列中的前十项是:

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

其中第十项的分子各位数之和是1+4+5+7=17.
找出 e 的收敛项序列中第100项的分子上各位之和。

思路:
老师曾经教导我们,题目超长的都是纸老虎。。。

如果题目没告诉我们自然常数e的连分数是[2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...],那这道题就需要再去查找资料,但是告诉了,而且只算第100项,直接暴解;

首先获得所有的连分数系数r,然后从连分数的最里面一层算起,不断迭代,对于\(\dfrac{a}{b}\),将其变成:\(\dfrac{1}{r(i)+\dfrac{a}{b}}=\dfrac{b}{br(i)+a}\)

下面代码只要0.0004秒就可完成。

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:

x2 – Dy2 = 1

For example, when D=13, the minimal solution in x is 6492 – 13×1802 = 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:

32 – 2×22 = 1
22 – 3×12 = 1
92 – 5×42 = 1
52 – 6×22 = 1
82 – 7×32 = 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.

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

x2 – Dy2 = 1

例如当 D=13时, x 的最小解是 6492 – 13×1802 = 1.

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

通过寻找当D = {2, 3, 5, 6, 7}时 x 的最小解,我们得到:
32 – 2×22 = 1
22 – 3×12 = 1
92 – 5×42 = 1
52 – 6×22 = 1
82 – 7×32 = 1

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

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

思路:
这道题昨晚发现是科普题。。。感觉不在网上找资料,暴解的人全都死了。。。反正我一开始暴力解决,然后发现尼马根本算不出来吗,即便只是算1到1000。。。
pellfunction
然后上网找丢潘图方程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)

翻译:
从以下三角形的顶端开始,向下一行的相邻数字移动,从顶端到底端的最大总和是23。

3
7 4
2 4 6
8 5 9 3

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

也就是 3 + 7 + 4 + 9 = 23.

triangle.txt(右键另存为)是一个文本文件,包含了一个一百行的三角形,找出这个三角形中从顶到底的最大和。

注意:这是题目18的更难的一个版本。穷举每一种可能的路径是不可行的,因为一共有299条可能的路径。就算每秒钟能处理1012条路径,也需要200亿年来处理完所有的路径。存在一个高效的方法来处理这道题。

思路:

我18题就是按这题难度来写的,所以代码思路和18题完全一样。。。动态规划秒杀之~

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.
p_068_1

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?
p_068_2

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

p_068_1

按照顺时针顺序,从外部节点最小的三个为一组的组开始(该例中为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位的字符串是什么?

p_068_2

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

其实根据题目要求可以推出好一些性质的,诸如最外边五个数的和必然是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.

翻译:
欧拉函数φ(n)(有时也叫做phi函数)可以用来计算小于n 的数字中与n互质的数字的个数。例如,因为1,2,4,5,7,8全部小于9并且与9互质,所以φ(9)=6。

n 互质数 φ(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

可以看出对于n ≤ 10,n=6时 的n/φ(n)取到最大值。

找出 n ≤ 1,000,000 的 n 中使得n/φ(n)取到最大的 n 值。

思路:
之前在研究这道题的时候专门狠狠地研究过欧拉函数的种种性质,所以这道题,如果要计算,肯定不会像题目所说那样去计算有多少个数与n互质这么蠢的方法,完全没碰过欧拉函数的孩子,稍微动一下手,问一下维基娘,就可以知道欧拉函数有这么一个简单的计算公式:

\(\phi (n)=n\prod\limits_{p|n}(1-\dfrac{1}{p})\)

一句话说,就是找出所有能被n整除的质数p,然后计算出\(1-\dfrac{1}{p}\)的连乘,再乘以n就可以了;

下面代码是Mathematica暴力计算这个解,有点花时间;

事实上,这道题有一个很容易想到的纯手算方法,从上面计算\(\phi (n)\)的公式我们就可以得到:

\(\dfrac{n}{\phi (n)}=\prod\limits_{p|n}\dfrac{p}{p-1}\)

注意这里p是质数,而\(\dfrac{p}{p-1}>1\),所以一个数n,含有的可以整除的质数越多,那么这个数的的\(\dfrac{n}{\phi (n)}\)就越大,所以可以得到2×3×5×7×11×13×17=510510<1,000,000 是最大的解!!

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 < 107 , for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

翻译:
欧拉函数φ(n)(有时也叫做phi函数)可以用来计算小于等于n 的数字中与n互质的数字的个数。例如,因为1,2,4,5,7,8全部小于9并且与9互质,所以φ(9)=6。

数字1被认为与每个正整数互质,所以 φ(1)=1。

有趣的是,φ(87109)=79180,可以看出87109是79180的一个排列。

对于1 < n < 107,并且φ(n)是 n 的一个排列的那些 n 中,使得 n/φ(n) 取到最小的 n 是多少?

思路:
为什么每次的最后一题都这么难!!!(╯‵□′)╯︵┻━┻摔

这道题,其实某种意义上也不算完整解决,但是我做完看了一下官方论坛,里面各种几分钟,十几分钟,几十分钟的做法,还有一些虽然秒出,但是实验性太强。。。

分析一下这道题,从上一题的反面得知,我们想要n/φ(n)尽可能小,那么n的质因数的个数要尽可能少!但是n可以是质数么?不行的,因为如果n是质数,那么φ(n)就等于n-1了,而φ(n)和n-1是不可能由相同的数字组成的;

那么我们就试一下下一种情况咯,有两个质因数的情况,我下面的算法就是基于此设计出来的,为了提高计算速度,做了一下一些优化:

首先,必然就是我们先筛选出小于10 7 的质数;然后历遍两两组合(i,j),查看φ(ij)是否和ij是由相同的数组成的;但是我们可以设定j>i,顺便得出i必然小于\(\sqrt{10000000}=3162.28\),而k取值是\(i\)\(\dfrac{10000000}{i}\);在另外,因为i,j是质数,所以搜索步进可以设成2;

再然后,可以很容易推出来只拥有两个质因数的n的欧拉函数:

\(\begin{eqnarray*}\phi (n) & = &n(1-\dfrac{1}{p})(1-\dfrac{1}{q}) \\& = & pq(1-\dfrac{1}{p})(1-\dfrac{1}{q})\\& = & (p-1)(q-1)\end{eqnarray*}\)

然后我就一时半会儿想不到什么更好的优化方法了。。囧。。下面代码要13秒,是目前为止需要时间最长的一个EP解答。。

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

  • 额,好吧,完全看不懂,好像很牛逼!

    • 其实好像除了代码,数学部分应该是初中水平的。。。不过现在好像做网站的人对数学都兴趣不大。。

  • 你这更新的速度略快啊,少年我看的速度完全跟不上这个节奏

    • 你个渣渣。。。不过接下来就不弄了。。。至少论文搞完才会弄。。

      • 我期待着传说中的剁手

        • 我都立下此誓了,就是铁了心好好水论文的节奏。。虽然要先把北京那破事给搞定。。

          • 我那边也要快点水一篇才行啊,要不然年不好过啊

            • 你可是说了春节前交初稿的。。。虽然我是交终稿。。

              • 我是为自己留个后路啊,要不然回不了家怎么办

  • Yu

    好赞,不过为啥用python写呢。一直只刷过poj和hdu的题目(自己渣学校的不说也罢)

    • 因为python简单。。。只要算法不是太糟糕,我一般就Mma或者Python解决,反正运行时间控制在几秒内,而且python写起来快,可读性上感觉也比较好(我是来分享算法思想的,对于代码怎么写其实不是很要紧。。如果算法设计不出来,python这一类语言太慢的话,我就马上转战C++,因为那个是本命。。

      • Yu

        你们都说python好看,果然我审美观奇葩么。。。我最喜欢看的是C/C++了,看它写的算法思路特别明晰,如果哪天我居然写python的东西了,一定是迁就哪个讨厌的同僚

        • 真爱是C++,但是这种题如果每道题都用C++的话,需要写的代码会很长一般统计表示实现相同的功能Py的长度是C的五分之一。Python也没那么差吧。。

          • Yu

            糟糕的印象来源于这个: https://github.com/DionyBudy/svd_with_parse/blob/master/svd.c 这是我直译的C代码,原文python忘了在哪了...没有任何的优化,就语言本身把运行时间减少了数十乃至上百倍。

          • Yu

            十万条数据貌似,python原文同学跑了快一小时,然后让我翻译下来试试看,20秒搞定。这不是扯淡么 -- 从此我只把这东西当成演示用语言。。

            • 速度慢确实就是python的一个致命问题和C比,据我印象好像相同的算法速度差也是100倍左右,所以我不会用python去做高速计算的问题,也没人会这么做;而做ACM这种题,如果python能秒出,那么说明C必然秒出,而ACM的精华本身也在于算法的设计,而不是怎么编程实现;

            • 不过有时算法有了也会必须用C++,因为指针这种神器可以做更加复杂的数据结构,而数据结构越复杂,就可以让算法越简单~

    • 我一般是在PE上还有lightoj上玩。。反正选定一个一直玩就是了,OJ平台这么多,根本玩不完。。。

      • Yu

        以前老一輩的学长传下来过一堆资料,其中包括不错的ACM OJ列表, 我很多都上去玩过 -- 话说几年下来,好多网站已经关门或者改域名了,真是物是人非啊 http://argcv.com/articles/49.c

  • 真正不明觉厉,点32个赞先~~~

  • 传说中的学霸?

    • 当然不是。。。除去代码都是初中生就能看得懂的题目。。

  • 不明觉厉    ╯     ╰     ●      ●     "    ^    "

  • 真不好意思,让你记住我了

    • 啥?没懂。。

      • 你猜

        • 虽然没懂,但是我记得的是这是你第二次在我博客回我“你猜”了。。。【别这样亲。。

          • 你记性真不错,我自己都忘了

            • 所以我还是没懂你一开始那句意义不明的话。。。

              • 不需要明白,没有意义

  • 高级,看不懂。

  • 专业性很强啊,我表示没看完。

    • 其实我也没指望有人看完,就是个人笔记性质

  • 貌似很牛逼的样子

    • 其实不是。。连微积分都没用上,就是初中数学。。

  • 好专业的博客看不懂

  • 学霸啊

  • 佩服!以后想写跟数论问题有关的代码可以请教你吗?好佩服你!!!

  • 好久没来了,过来转转