小练习20170612 求(a-1)^n + (a+1)^n除以a^2的最大余数

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了200余题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题。

                               
登录/注册后可看大图

题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
注重程序效率和创意。
答题在一周内完成，即6.19 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。题目不难，大家看看谁的效率高。

----回帖需写明解题思路，鼓励在程序中加上注释


一些鱼油反映题目有些过难，为此略过一部分偏难的题目。





题目：

设 r 为 (a-1)ⁿ + (a+1)ⁿ 除以 a² 所得的余数

比如，如果 a=7，n=3，则 r =42: 6³+8³=728 728 mod 49 = 42.  n 变化的话，r 的值也会随着变化，但是我们发现，当 a=7 时，r 取到最大值 42。

请求出 a 从 3 到 1000 所得的 r 的最大值之和。

达锅

1. #(a-1)^n + (a+1)^n除以a^2的最大余数
   
2. import time
   
3. 
   
4. t=time.time()
   
5. print (sum([max([(n*2*a)%(a**2) for n in range(1,2*a,2)]) for a in range(3,1000)]))
   
6. 
   
7. print(time.time()-t)
   

复制代码

终于领会了python的简洁，虽然合并以后不太看得懂，答案也不一定对……
让我好好回忆了一把高中数学的n次方的二项式展开式……
(a-1)^n + (a+1)^n除以a^2
最终整理为2*a*n除以a^2的最大余数，其中n为奇数，且不大于2a
故在(1,2*a,)的范围内，以步长为2，列出所有余数并求最大值。
感觉n的取值应该还有别的算法，但是考虑到a不是很大，放弃了

jerryxjr1220

我觉得这题数学方面的分析会更多一些：
先来找规律：
当n=1时，（a-1）+（a+1）          = 2a                                 mod a^2 --> 2a
当n=2时，（a-1）^2+（a+1）^2 = 2a^2 + 2                      mod a^2 --> 2
当n=3时，（a-1）^3+（a+1）^3 = 2a^3 + 6a                    mod a^2 --> 6a
当n=4时，（a-1）^4+（a+1）^4 = 2a^4 + 12a^2 + 2       mod a^2 --> 2
当n=5时，（a-1）^5+（a+1）^5 = 2a^5 + 20a^3 + 10a   mod a^2 --> 10a
可以看到规律，
当n为奇数是 r = 2an，当n为偶数时r=2
所以，要使r为最大，n必须是奇数，并且2an<a^2（因为如果大于或等于就mod掉了），则n<a/2。

所以，暴力解法可以写成：

1. remainder = lambda a, n: ((a - 1)**n + (a + 1)**n) % a**2
   
2. print(sum((max((remainder(a, n) for n in range(1, 2 * a))) for a in range(3, 1001))))

复制代码

大约30多秒可以出结果。
333082500

另外，一种直接计算的方法：

1. print(sum((2 * a * ((a - 1) // 2) for a in range(3, 1001))))

复制代码

秒出答案。
333082500

keweel

版主大大  麻烦你这题也改下？  看标题跟下面的内容好像又不一样了。方便阅读理解。辛苦了

冬雪雪冬

keweel 发表于 2017-6-12 17:32
版主大大  麻烦你这题也改下？  看标题跟下面的内容好像又不一样了。方便阅读理解。辛苦了

已修改，这几天不知怎么了，老犯错误。

WelanceLee

1. s = 0
   
2. s = 0
   
3. for a in range(3, 1001):
   
4.     mm = 0
   
5.     for i in range(1, a, 2):
   
6.         if (2*i)%a > mm:
   
7.             mm = 2*i%a
   
8.     s += mm*a
   
9. print(s)
   

复制代码

答案是332833002

concrete

import math
num = []
for a in range(3,1001):
    for n in range(1,10):  #给n设定了范围
        r = ((a-1)**n + (a+1)**n)%(a**2)
        list1 = []
        list1.append(r)
        maxr = max(list1)
        num.append(maxr)
print('最大值之和是：%s' % sum(num))

lovesword

1. #!/usr/bin/env python
   
2. # coding=utf-8
   
3. # python 2.7
   
4. import time
   
5. start = time.time()
   
6. print 'res: ',sum([a*(a+a%2-2) for a in range(3,1001)])
   
7. print 'sec: ',time.time()-start
   

复制代码

=============================
res:  333082500
sec:  0.0002760887146

小剑剑

1. import math
   
2. def denum(num):
   
3.     rawnum=num
   
4.     dlist=[]
   
5.     for i in range(2,int(math.sqrt(num))+1):
   
6.         if not num%i:
   
7.             while not num%i:
   
8.                 num//=i
   
9.             dlist.append(i)
   
10.         if num==1:
    
11.             return dlist
    
12.     if rawnum!=num:
    
13.         dlist.append(num)
    
14.         return dlist
    
15. 
    
16. def find_euler(a,e,num,dlist):
    
17.     for i in dlist:
    
18.         while True:
    
19.             if e%i:
    
20.                 break
    
21.             e//=i
    
22.             if pow(a,e,num)!=1:
    
23.                 e*=i
    
24.                 break
    
25.     return e
    
26. mlist=[]
    
27. for a in range(3,1001):
    
28.     l=a-1
    
29.     r=a+1
    
30.     mo=a**2
    
31.     e=a*(a-1)
    
32.     tl=l
    
33.     tr=r
    
34.     leuler=find_euler(l,e,mo,denum(e))
    
35.     reuler=find_euler(r,e,mo,denum(e))
    
36.     lmolist=[]
    
37.     rmolist=[]
    
38.     for i in range(leuler):
    
39.         lmolist.append(l)
    
40.         l*=tl
    
41.         l%=mo
    
42.     for i in range(reuler):
    
43.         rmolist.append(r)
    
44.         r*=tr
    
45.         r%=mo
    
46.     g=leuler*reuler//math.gcd(leuler,reuler)
    
47.     lmolist=lmolist*(g//leuler)
    
48.     rmolist=rmolist*(g//reuler)
    
49.     mlist.append(max([(lmolist[i]+rmolist[i])%mo for  i in range(g)]))
    
50. print(sum(mlist))
    

复制代码

333082500



把mlist打印出来发现了这些数字是有规律的
增量是等差数列
所以方法二可以这样子

1. raw=0
   
2. su=0
   
3. inlist=[6, 2, 12, 4, 18, 6, 24, 8, 30, 10]
   
4. innum=(30,10)
   
5. for i in range(998):
   
6.     raw+=inlist[i%10]
   
7.     inlist[i%10]=inlist[i%10]+innum[i%2]
   
8.     su+=raw
   
9. print(su)
   

复制代码

超速无奈

想看看答案

小剑剑

jerryxjr1220 发表于 2017-6-12 10:18
我觉得这题数学方面的分析会更多一些：
先来找规律：
当n=1时，（a-1）+（a+1）          = 2a           ...

我做的时候发现增量是等差数列，一直从模的角度想，没搞明白。原来是这么一回事

jerryxjr1220

小剑剑 发表于 2017-6-20 10:01
我做的时候发现增量是等差数列，一直从模的角度想，没搞明白。原来是这么一回事

看明白了，这周的题目也就很容易解了。