EulerProject.png

56 幂的数字和

  一古戈尔( 10^100 )是一个巨大的数字：1后面跟着100个0。100^100则更是无法想像地巨大：1后面跟着200个0。尽管这两个数如此巨大，各位的数字和却都只有1。
  若a, b < 100，所有a^b中，最大的数字和是。

Python3解答

sumb=0
for i in range(1,100):
    for j in range(1,100):
        d=sum([int(i) for i in list(str(i ** j))])
        if sumb<d:
            sumb=d
            dishu = i
            mi = j
print(dishu, mi)
print(sumb)
答案：99^95， 数字和是972

57 平方根逼近

  2的平方根可以用一个无限连分数表示：
      √ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + … ))) = 1.414213…
  将连分数计算取前四次迭代展开式分别是：
      1 + 1/2 = 3/2 = 1.5
      1 + 1/(2 + 1/2) = 7/5 = 1.4
      1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666…
      1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379…
   接下来的三个迭代展开式分别是99/70、239/169和577/408，但是直到第八个迭代展开式1393/985，分子的位数第一次超过分母的位数。
  在前一千个迭代展开式中，有多少个分数分子的位数多于分母的位数。

Python3解答

#第一次迭代的初始值
a=2#分母
b=3#分子
er=0#记录代数
count=0#记录超过的次数
while er<1000:
    a,b=a+b,2*a+b#迭代表达式
    if (len(str(b)))>len(str(a)):
        count+=1
    er+=1
print(count)
答案：153

58 螺旋素数

  从1开始逆时针螺旋着摆放自然数，构造出一个边长为7的螺旋数阵(如下所示)。

spiral.png

  可以发现，所有的奇数平方都在这个螺旋方针的右下对角线上，更有趣的是，在所有对角线上一共有8个素数(红色数字)，比例达到8/13 ≈ 62%。
  在这个方阵外面完整地再加上一层，就能构造出一个边长为9的螺旋方阵。如果不断重复这个过程，当对角线上素数的比例第一次低于10%时，螺旋数阵的边长是。

Python3解答

def JudgePrime(number):#判断素数
    if number == 1:
        return False
    elif number == 2:
        return True
    for ip in range(2, int(number ** 0.5) + 1):
        if number % ip == 0:
            return False
    return True
def Judge(exlist):#判断素数的个数
    pcount = 0
    for ip in exlist:
        if JudgePrime(ip):
            pcount += 1
    return pcount

percent = 1
#利用start 和 per 得到增加的对角线数字
start = [1, 1, 1, 1]
per = [2, 4, 6, 8]
times = 1
primecount = 0
c = 1

while percent >= 0.1:
    exli = []#边长每增加2， 对角线元素增加的数字
    for j in range(len(start)):
        exli.append(start[j] + per[j])
    primecount += Judge(exli)#累积的素数个数
    percent = primecount / (1 + c * 4)#素数比例
    times += 2#边长
    c += 1
    start = exli.copy()
    for ia in range(len(per)):
        per[ia] += 8
print(times)
答案：26241

59 异或解密

  计算机上的每个字符都被指定了一个独特的代码，其中被广泛使用的一种是ASCII码(美国信息交换标准代码)。例如: 大写字母A = 65，星号（*） = 42，小写字母k = 107。
  一种现代加密方法是将一个文本文档中的符号先转化为ASCII码，然后将每个字节异或一个根据密钥确定的值。使用异或进行加密的好处在于，只需对密文使用相同的密钥再加密一次就能得到明文，例如，65 XOR 42 = 107，而107 XOR 42 = 65。
  为了使加密难以破解，密钥要和明文一样长，由随机的字节构成。用户会把加密过的信息和密钥放置在不同的地方，解密时二者缺一不可。
  不幸的是，这种方法对大多数人来说并不实用，因此一个略有改进的方法是使用一个密码作为密钥。密码的长度很有可能比信息要短，这时候就循环重复使用这个密码进行加密。这种方法需要达到一种平衡，一方面密码要足够长才能保证安全，另一方面需要充分短以方便记忆。
  你的破解任务要简单得多，因为密钥只由三个小写字母构成。在文本cipher.txt中包含了加密后的ASCII码，并且已知明文包含的一定是常见的英文单词，解密这条消息并求出原文的ASCII码之和。

Python3解答

#读取文件
with open(r'C:\Users\GWT9\Desktop\p058_cipher.txt') as f:
    data = f.read()
f.closed
#因为密钥只由三个小写字母构成
zimu1 = []#使用第一个字母加密的
zimu2 = []#使用第二个字母加密的
zimu3 = []#使用第三个字母加密的

listzi = data.split(',')
for hu in range(len(listzi)):
    if hu % 3 == 0:
        zimu1.append(int(listzi[hu]))
    elif hu % 3 == 1:
        zimu2.append(int(listzi[hu]))
    else:
        zimu3.append(int(listzi[hu]))

# 十进制转二进制
def DeToBs(number):
    if number == 0:
        return '0'
    else:
        hu = ''
        while number != 0:
            if number % 2 == 0:
                hu += '0'
            else:
                hu += '1'
            number = int(number / 2)
    uh = hu[::-1]
    return uh

# 二进制转十进制
def BsToDe(binary):
    nu = 0
    for i in range(len(binary)):
        nu += int(binary[i]) * (2 ** (len(binary) - 1 - i))
    return nu

# 异或运算
def Trans(bs1, bs2):
    bbs1 = DeToBs(bs1)
    bbs2 = DeToBs(bs2)
    if bs1 >= bs2:
        while len(bbs2) < len(bbs1):
            rebbs2 = bbs2[::-1]
            rebbs2 += '0'
            bbs2 = rebbs2[::-1]
    else:
        while len(bbs1) < len(bbs2):
            rebbs1 = bbs1[::-1]
            rebbs1 += '0'
            bbs1 = rebbs1[::-1]
    # 进行异或
    xor = ''
    for dd in range(len(bbs1)):
        if bbs1[dd] == bbs2[dd]:
            xor += '0'
        else:
            xor += '1'
    return BsToDe(xor)

#解密后的ASCII码除了是[大小写字母，英文逗号,空格,句点]之外的越少，说明是密钥的可能性越大。
def JudeMiyue(milist, st):
    dd = []
    for im in milist:
        if Trans(im, st) >= 65 and Trans(im, st) <= 122:#
            pass
        else:
            #加上这个判断是必须的， 因为如果不加，无法判断真正的密钥是什么。
            if Trans(im, st) not in [32, 44, 46]:
                # 除去英文逗号,空格,句点。
                dd.append(Trans(im, st))
    return len(set(dd))

def Last(milist):
    du = {}
    st = 97#代表a的ASCII码
    while st <= 122:#代表z的ASCII码，遍历循环，找到最小的对应的字母
        gu = JudeMiyue(milist, st)
        du[st] = gu
        st += 1
    mink = min(du.items(), key=lambda x: x[1])[0]#判断最小的
    return mink

sumd = 0#存储ASCII码的和
yuanwen = ''#加密前的明文

names = locals()
for i in [1, 2, 3]:#三个加密文件
    names['fr%d'%i] = Last(eval('zimu%d' % i))
    print('第%d个字母密钥为：%s'%(i, chr(eval('fr%d'%i))))

for iz, jz, hz in zip(zimu1, zimu2, zimu3):
    number1 = Trans(fr1, iz)
    number2 = Trans(fr2, jz)
    number3 = Trans(fr3, hz)
    sumd += number3 + number1 + number2
    yuanwen += chr(number1) + chr(number2) + chr(number3)

print('原文为:%s'%(yuanwen + chr(Trans(fr1, zimu1[-1]))))#因为字母1多一个
print('所有的ASCII码的和为:%d'%(sumd + Trans(fr1, zimu1[-1])))
答案：第1个字母密钥为：g
第2个字母密钥为：o
第3个字母密钥为：d
原文为:(The Gospel of John, chapter 1) 
1 In the beginning the Word already existed. He was with God, and he was God. 
2 He was in the beginning with God. 
3 He created everything there is. Nothing exists that he didn't make. 
4 Life itself was in him, and this life gives light to everyone. 
5 The light shines through the darkness, and the darkness can never extinguish it. 
6 God sent John the Baptist 
7 to tell everyone about the light so that everyone might believe because of his testimony. 
8 John himself was not the light; he was only a witness to the light. 
9 The one who is the true light, who gives light to everyone, was going to come into the world. 
10 But although the world was made through him, the world didn't recognize him when he came. 
11 Even in his own land and among his own people, he was not accepted. 
12 But to all who believed him and accepted him, he gave the right to become children of God. 
13 They are reborn! This is not a physical birth resulting from human passion or plan, this rebirth comes from God.
14 So the Word became human and lived here on earth among us. He was full of unfailing love and faithfulness. And we have seen his glory, the glory of the only Son of the Father.
所有的ASCII码的和为:107359

60 特殊素数组

  3、7、109和673是特别的一组素数。任取其中的两个并且以任意顺序连接起来，其结果仍然是个素数。例如:：选择7和109，任意连接得到的7109和1097均为素数。这组素数的和是792，这是满足这个性质的一组四个素数的最小和。
  若有一组包含五个素数，任取其中的两个并且以任意顺序连接起来，其结果仍是个素数，求这样一组素数的最小和。

Python3解答

# 判断素数
def an_prime(number):
    if number == 1 or number == 0:
        return False
    for i in range(2, int(number ** 0.5) + 1):
        if number % i == 0 and number > i:
            return False
    return True

# 判断组合是否为素数
def Combine(listex):
    for i in range(len(listex) - 1):
        for j in range(i + 1, len(listex)):
            if not an_prime(int(str(listex[i]) + str(listex[j]))) or not \
                    an_prime(int(str(listex[j]) + str(listex[i]))):
                return False
    return True

# 得到nunm以内的素数集合
def PrimeSet(nunm):
    anset = []
    fan = 3
    while fan < nunm:
        if an_prime(fan):
            anset.append(fan)
        fan += 1
    return anset

# 暴力搜索函数
def Violence(num):
    dd = PrimeSet(num)
    for jj in range(len(dd)):
        for ii in range(jj + 1, len(dd)):
            if Combine([dd[ii], dd[jj]]):
                for gg in range(ii + 1, len(dd)):
                    if Combine([dd[ii], dd[gg], dd[jj]]):
                        for hh in range(gg + 1, len(dd)):
                            if Combine([dd[ii], dd[hh], dd[gg], dd[jj]]):
                                for cc in range(hh + 1, len(dd)):
                                    if Combine([dd[ii], dd[cc], dd[gg], dd[hh], dd[jj]]):
                                        return [dd[ii], dd[jj], dd[gg], dd[hh], dd[cc]]


primelist = Violence(10000)
print(primelist)
print(sum(primelist))
答案：满足条件的一组素数：[5197, 13, 5701, 6733, 8389]
和为：26033

持续更新，欢迎讨论，敬请关注！！！