小练习：20171016 强循环单位数

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。

其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。

什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html

我们欧拉板块现已给出了200余题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。

如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives

这里已经有了500余题。

                               
登录/注册后可看大图

要求：

以python语言完成，如果是python2请注明。

程序以代码文字格式发帖。

注重程序效率和创意。

答题在一周内完成，即10.23 10：00之前，其后将公开大家的答案，并评比成绩。

另程序和答案可以在网上搜到，希望大家独立完成。题目不难，大家看看谁的效率高。

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

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

                               
登录/注册后可看大图

346

jerryxjr1220

这题其实蛮简单的，我们先分析一下解题过程。
毫无疑问，一个1的b进制 N1 = 1（不算）；
两个1的b进制 N2 = b + 1 = N1 * b + 1
三个1的b进制 N3 = b**2 + b + 1 = N2 * b + 1
m个1的b进制 Nm = b**(m-1) + b**(m-2) +...+ b + 1 = N(m-1)*b + 1
这样就有了递推关系。
再来看范围，由于这个单位循环数至少要满足2种进制，所以至少三个1的b进制 N3 = b**2 + b + 1 < 10**12，也就是 b < 10**6.
剩下的程序就好写了，对了，为了避免重复，我用了集合去重。

1. result = set([1])
   
2. for b in range(2, 10**6):
   
3.     num = b*b + b + 1
   
4.     while num < 10**12:
   
5.         result.add(num)
   
6.         num = num*b + 1
   
7. print(sum(result))

复制代码

336108797689259276
[Finished in 1.0s]

用arrdio编写，做了个有界面的，看起来舒服多了，用arrdio做界面真的是比python省心多了。

1. import win.ui;
   
2. import time;
   
3. /*DSG{{*/
   
4. /*}}*/
   
5. 
   
6. var calc = function (limit) {
   
7.         var tab = {1};
   
8.         for b=2;limit**0.5 {
   
9.                 var num = b*b+b+1;
   
10.                 while num<limit {
    
11.                         table.push(tab,num);
    
12.                         num = num*b+1;
    
13.                 }
    
14.         }
    
15.         table.sort(tab);
    
16.         for i=1;#tab-1 if tab[i]==tab[i+1] tab[i]=null;
    
17.         var sum=math.size64(0);
    
18.         for i in tab sum+=tab[i];
    
19.         return sum;
    
20. }
    
21. winform.button.oncommand = function(id,event){
    
22.         //winform.msgbox( winform.button.text );
    
23.         var st = time.tick();
    
24.        
    
25.         winform.edit.text = calc ( eval(winform.limit.text) );
    
26.         winform.time_calc.text = string.format('Total time used: %d ms',time.tick()-st);
    
27. }
    
28. winform.show()
    
29. win.loopMessage();

复制代码

xindong

循环不断去找不同长度的1111对应的数值，一直找到 111对应的不同进制下的数值就可以了。这些数都可以在11的长度下找到对应的值，这样大大简化了算法虽然10xe12比较大，还是在10多秒内求出结果。

1. # -*- coding: utf-8 -*-
   
2. """
   
3. Created on Tue Oct 17 12:13:20 2017
   
4. 
   
5. """
   
6. 
   
7. import math
   
8. import datetime
   
9. 
   
10. #将指定长度的全1数，根据进制转换为十进制
    
11. def toDec(UnitNum, base):
    
12.     number=0
    
13.     for i in range(UnitNum):
    
14.         number=number+base**(i)
    
15.     return number
    
16. 
    
17. 
    
18. starttime = datetime.datetime.now()
    
19. # 10--12
    
20. number=1000000000000
    
21. 
    
22. # 10--10
    
23. #number=10000000000
    
24. 
    
25. # 10--8
    
26. #number=100000000
    
27. 
    
28. # 10--6
    
29. #number=1000000
    
30. 
    
31. #number=1000
    
32. #number=50
    
33. 
    
34. 
    
35. #找到所求的数的最长全1的长度，应该是二进制是最长的， B2_length为全1的长度
    
36. B2_length=int(math.log(number,2))
    
37. 
    
38. dec_value=0
    
39. 
    
40. StrongRepUnits=[]
    
41. base_num=2
    
42. while(B2_length>2):           #不计算各个进制下 11的情况，
    
43.     while(dec_value<=number):       #如果计算出的值 < number
    
44.         for i in range(2,B2_length):     
    
45.             tmp=toDec(B2_length-i+2,base_num)    #固定进制，计算不同长度全1对应的十进制值
    
46.             if (tmp<number):                     #小于 number,加入列表
    
47.                 StrongRepUnits.append(tmp)
    
48.         base_num=base_num+1                      #计算下一个进制
    
49.         dec_value=toDec(B2_length,base_num)      #判断下一个进制下的全1值是否超过number,如果超过，退出
    
50.     B2_length=B2_length-1             #全1长度减1     
    
51.     dec_value=toDec(B2_length,base_num)
    
52. 
    
53. #所有列表中的数都是可以在长度为11的不同进制下成为最长单位循环数的，再加上1
    
54. 
    
55. StrongRepUnits.append(1)
    
56. #print(StrongRepUnits)
    
57. #set函数去除重复项
    
58. final_list=list(set(StrongRepUnits))
    
59. #打印和
    
60. print(sum(final_list))
    
61. 
    
62. endtime = datetime.datetime.now()
    
63. print((endtime - starttime).seconds);
    

复制代码

结果：336108797689259276

gunjang

336108797689259276
1-n之间，除了1和2，都可以表示成11（x-1）的形式，所以只要找到另一个b，实现111 or 1111 or。。。就行

1. import time
   
2. def getStrongRepunits(maxn): #b = d-1 #11(d-1)
   
3.         r = set([])
   
4.         for d in range(2, int(maxn**0.5)):
   
5.                 step = d*d
   
6.                 curr = 1 + d + step
   
7.                 while curr < maxn:
   
8.                         r.add(curr)
   
9.                         step *= d
   
10.                         curr += step
    
11.         #print(r)
    
12.         return sum(r) + 1 #1 is strong Repunits
    
13. 
    
14. st = time.time()
    
15. print(getStrongRepunits(10**12)) #336108797689259276
    
16. print('cost %fs'%(time.time()-st)) #0.66s

复制代码

雨水

太多了，我太懒

wc365

1. fun1 = lambda x,y:[x**n for n in range(y)]
   
2. fun2 = lambda x,y:sum(fun1(x,y))
   
3. fun3 = lambda x,z:[sum(fun1(x,y)) for y in range(1,z+1)]
   
4. 
   
5. def fun4(x,y):
   
6.     i = 1
   
7.     while fun2(x,i)<y:
   
8.         i = i + 1
   
9.     return fun3(x,i-1)
   
10.         
    
11. def fun5(y):
    
12.     a = [1]
    
13.     for x in range(2,y):
    
14.         if len(fun4(x,y)) < 3:
    
15.             break
    
16.         a += fun4(x,y)[2:]
    
17.     return sorted(list(set(a)))
    
18. 
    
19. print("50以内的强制循环单位数有",fun5(50))
    
20. print("1000以内的强制循环单位数的和为",sum(fun5(1000)))
    
21. print("10**12以内的强制循环单位数的和为",sum(fun5(10**12)))

复制代码

运行结果如下：
50以内的强制循环单位数有 [1, 7, 13, 15, 21, 31, 40, 43]
1000以内的强制循环单位数的和为 15864
10**12以内的强制循环单位数的和为 336108797689259276

ym767967540

好腻害的说