小练习：20170807 squarefree的二项式系数

冬雪雪冬

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

                               
登录/注册后可看大图

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

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


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



题目：

二项式系数 ⁿC_k 可以排成帕斯卡三角的形式，如下图：

                               
登录/注册后可看大图

可知，前 8 行中，总共有 12 个不同的数字 1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21 和 35。对于正整数 n，如果没有任何一个质数的平方可以整除 n，则 n 被叫做 squarefree 。
那么。帕斯卡三角的前 8 行得到的那 12 个不同的数字中，除了 4 和 20，其余都是 squarefree 的。所有 squarefree 数之和是 105。

请给出帕斯卡三角前 51 行中不同的 squarefree 数之和。

jerryxjr1220

这题计算逻辑应该挺简单的，完整按照题目要求写程序就行了，暴力解法速度也挺快。
C（n，k）有2种算法，一种是用阶乘n!//k!//(n-k)!，另一种就是利用杨辉三角形，上一行的2项之和，递归算法。

1. import time
   
2. st=time.time()
   
3. 
   
4. from math import factorial as f
   
5. def C(n,k):
   
6.         return f(n)//f(k)//f(n-k)
   
7. 
   
8. # from functools import lru_cache
   
9. # @lru_cache(maxsize=None)
   
10. # def C(n,k):
    
11. #         if k==0 or k==n: return 1
    
12. #         return C(n-1,k-1)+C(n-1,k)
    
13. 
    
14. def gen_prime_sqr(n):
    
15.         primes = [True]*n
    
16.         primes[:2] = [False]*2
    
17.         for i, prime in enumerate(primes):
    
18.                 if prime:
    
19.                         for j in range(i*i, n, i):
    
20.                                 primes[j] = False
    
21.         return [k*k for k, trueprime in enumerate(primes) if trueprime]
    
22. 
    
23. prime_sqr = gen_prime_sqr(int(C(50,25)**0.25)+1)
    
24. 
    
25. def is_sqrfree(n, prime_sqr=prime_sqr):
    
26.         for p in prime_sqr:
    
27.                 if n % p == 0:
    
28.                         return False
    
29.         return True
    
30. 
    
31. sqrfreelist = set()
    
32. for n in range(0, 51):
    
33.         for k in range(0, (n+1)//2+1):
    
34.                 if is_sqrfree(C(n,k)):
    
35.                         sqrfreelist.add(C(n,k))
    
36. print(sum(sqrfreelist))
    
37. print(time.time()-st)

复制代码

34029210557338
0.015608787536621094
[Finished in 0.1s]

小Q学Python

思路见注释。。。

1. # 得到三角图里的所有的数（去重）
   
2. def test1(n):
   
3.     a = [1,1]  # 第二列
   
4.     result = [1]  # 前两列都只有1
   
5.     for i in range(3,n+1):  # 从第三列开始计算
   
6.         b = []
   
7.         for j in range(len(a)-1):
   
8.             b.append(a[j]+a[j+1])  # 每个数字跟后面的数字相加
   
9.         result += b
   
10.         a = [1]+b+[1]  # 在新列两边各加1
    
11.     return list(sorted(set(result)))
    
12.    
    
13. # 质数清单
    
14. def zhishu(n):  #  求的小于n的所有质数
    
15.     a = [True]*(n+1)
    
16.     a[0],a[1]=False,False
    
17.     for index in range(2, len(a)):
    
18.         if a[index]==True:
    
19.             for i in range(index+index,len(a),index):
    
20.                 a[i]=False
    
21.     return [i for i, j in enumerate(a) if j==True]
    
22.    
    
23. # 结果
    
24. def test2(n):
    
25.     a = test1(n)  # 得到三角图里数字
    
26.     b = []  # 非squarefree数字
    
27.     m = int(max(a)**0.25)+1  # 能否为质数的平方整除，所以只需得到最大数的开4次方的质数序列
    
28.     z = [i**2 for i in zhishu(m)]
    
29.     for i in a:
    
30.         for j in z:
    
31.             if i%j==0:
    
32.                 b.append(i)
    
33.                 break
    
34.     return sum(set(a)-set(b))
    
35.             

复制代码

time test2(51)
Wall time: 15.6 ms
Out[16]: 34029210557338

plus

求杨辉三角的代码是百度找的，就凑个热闹
看看结果对不
input a number:51
34029210557338

import time

def YangHui (num):  #先要找到这个列表，来源百度杨辉三角
    LL = [[1]]
    for i in range(1,num):
        LL.append([(0 if j== 0 else LL[i-1][j-1])+ (0 if j ==len(LL[i-1]) else LL[i-1][j]) for j in range(i+1)])
    return LL

primes = [2,3]
nextp = 5

def is_prime(nextp, primes):
    for x in primes:
        if x > nextp**0.5:
            return True
        if nextp % x == 0:
            return False

num = 51 #int(input('input a number:')) #输入层数

tt=time.time()

m = {1}
for i in YangHui(num):m = m|set(i)
psk = list(m)
list.sort(psk) #生成对应层数杨辉三角并处理列表psk为三角中不重复的数字

while primes[-1] <= psk[-1]**0.25+1:
    if is_prime(nextp, primes):
        primes.append(nextp)
    nextp += 2

square=[]
for i in psk:
    for j in primes:
        if i % j**2==0:
            square.append(i)
            break

squarefree=list(set(psk)-set(square))

sum1 = 0
for i in squarefree:sum1 += i

print(sum1)
print(time.time()-tt)

suloman

自己都感觉过程复杂  
num=51
a=[[1,1]]
for i in range(1,num-1):
    a.insert(i,[1])
   
    for j in range(i):
        
        a[i].append((a[i-1][j]+a[i-1][j+1]))
        
    a[i].append(1)
#print(a)
dd=[]
for i in range(num-1):
    for each in a[i]:
        if each not in dd:
            dd.append(each)
#print (dd)
#print(max(dd))
def zhishu_list(number):
    a = [True]*(number+1)
    a[0], a[1] = False, False
    for i in range(2,len(a)):
        if a[i] == True:
            for j in range(i*i,len(a),i):
                a[j]=False
    b = [i for i,j in enumerate(a) if j==True]
    return b
ss=int(max(dd)**0.5)

zhi=zhishu_list(ss)
#print(zhi)
zhi1=[]
for i in zhi:
    zhi1.append(i*i)
#print(zhi1)
total=0
for i in dd:
    for j in zhi1:
        if j>i :
            break
        else:
            if i%j ==0:
                print(i)
                total+=1
                break
print(total)

小剑剑

1. import math
   
2. import time
   
3. def denum(num):
   
4.     rawnum=num
   
5.     dlist=[]
   
6.     for i in range(2,int(math.sqrt(num))+1):
   
7.         if not num%i:
   
8.             while not num%i:
   
9.                 num//=i
   
10.                 dlist.append(i)
    
11.         if num==1:
    
12.             return dlist
    
13.     if rawnum!=num:
    
14.         dlist.append(num)
    
15.         return dlist
    
16.     else :
    
17.         return [rawnum]
    
18. dnum={}
    
19. squarefree_nums=[1,2,3,5,6,7,10,15,21,35]
    
20. binomials=[[[3,7],[],21],[[5,7],[],35]]
    
21. n=7
    
22. while n<51:
    
23.     dlist=denum(n+1)
    
24.     if  n&1:
    
25.         temp=[]
    
26.         temp.append(binomials[-1][0][:])
    
27.         temp.append(binomials[-1][1][:])
    
28.         temp.append(binomials[-1][2])
    
29.     for i in range(len(binomials)):
    
30.         for j in dlist:
    
31.             if j in binomials[i][0]:
    
32.                 binomials[i][0].remove(j)
    
33.                 binomials[i][1].append(j)
    
34.             else:
    
35.                 binomials[i][0].append(j)
    
36.         if n-i-1 in dnum:
    
37.             templist=dnum[n-i-1]
    
38.         else:
    
39.             templist=denum(n-i-1)
    
40.             dnum[n-i-1]=templist
    
41.         for j in templist:
    
42.             if j in binomials[i][0]:
    
43.                 binomials[i][0].remove(j)
    
44.             else:
    
45.                 binomials[i][1].remove(j)
    
46.                 binomials[i][0].append(j)
    
47.         binomials[i][2]=(binomials[i][2]*(n+1))//(n-i-1)
    
48.         if not binomials[i][1] and binomials[i][2] not in squarefree_nums:
    
49.             squarefree_nums.append(binomials[i][2])
    
50.     if  n&1:
    
51.         temp[2]*=2
    
52.         if 2 in temp[0]:
    
53.             temp[0].remove(2)
    
54.             temp[1].append(2)
    
55.         else :
    
56.             temp[0].append(2)
    
57.             if not temp[1] and temp[2] not in squarefree_nums:
    
58.                 squarefree_nums.append(temp[2])
    
59.         binomials.append(temp)
    
60.     if n in dnum:
    
61.         temp=dnum[n]
    
62.     else:
    
63.         temp=denum(n)
    
64.         dnum[n]=temp
    
65.     if len(set(temp))==len(temp):
    
66.         squarefree_nums.append(n)
    
67.     n+=1
    
68. print(sum(squarefree_nums))
    
69. print(time.process_time())

复制代码

34029210557426
0.156001

hhhhhq

def combination(m,n):
    a, b= 1, 1
    for i in range(n):
        a = a*(i+1)
        b = b*(m-i)
    C = b/a
    return C



def find(number):
    j = 2
    while True:
        if j*j > number:
            d = number
            return d
            break
        elif number % (j*j) == 0:
            d = 0
            return d
            break
        j += 1



def squarefree():
    Sum = 0
    list = []
    for m in range(1,51):
        for n in range(1,26):
            if n > m/2:
                break
            C = combination(m,n)
            if C in list:
                continue
            number = C
            d = find(number)
            if d != 0:
                list.append(C)

    Sum = sum(list) + 1
#    list.sort()
#    print(list)
#    print(len(list))
    print(Sum)
   
squarefree()
#想不出来更好的算法了，结果是34029210557338#

达锅

解题越来越需要灵感了，一开始被大数误导，求除数被除数，发现数好大，算不下去……就耗了一周

答案是：34029210557338

1. def cc(r,n):
   
2.     n,r=zs[n][:],zs[r][:]+zs[n-r][:]#获得分子分母的质数列表
   
3.    
   
4.     for i in r:#去掉分母
   
5.         n.remove(i)
   
6.     #print(n)
   
7.     for i in set(n):
   
8.         if n.count(i)>=2:return 0#存在2个以上的相同质数，能整除，返回0
   
9.     temp=1#返回乘积
   
10.     for i in n:
    
11.         temp*=i
    
12.     return temp
    
13. 
    
14. c=1+51
    
15. lb=[i for i in range(c)]#生成质数列表
    
16. zs=[[] for i in range(c)]
    
17. lb[0],lb[1]=[],[]
    
18. for i in range(2,c):
    
19.     if lb[i]>1:
    
20.         for j in range(i+1,c):
    
21.             if lb[j]%lb[i]==0 :
    
22.                 zs[j].append(lb[i])
    
23.                 lb[j]//=lb[i]
    
24.         zs[i].append(lb[i])
    
25.         lb[i]=1
    
26.     zs[i]+=zs[i-1]#加上前一项，即生成在c范围内所有阶乘由质数构成的列表
    
27. 
    
28. 
    
29. summ=0
    
30. all=set()
    
31. for n in range(1,c-1):
    
32.     for r in range(n//2+1):
    
33.         temp=cc(r,n)#是，返回数，不是，返回0
    
34.         if temp and temp not in all:
    
35.             all.add(temp)
    
36.             summ+=temp
    
37. 
    
38. print(summ)

复制代码

夏天和大熊

      想破头也没想出什么巧妙的算法，想从满足条件的数所在的位置下手，因为这个三角数阵每一行的值都是从前一行继承而来的，不过想了半天还是无功而返，只能硬着头皮直接算，居然算出来了！！！！不知道答案对不对。
      最后的结果是628775518183470

1. # 给出卡帕斯三角中前n行中所有不同的数
   
2. def crt_list(n = 3):
   
3.     list_nums = [[1 for i in range(n)]]
   
4.     list_kap = [1]
   
5.     if n%2 :
   
6.         temp = n//2
   
7.     else:
   
8.         temp = n//2 - 1
   
9.     for i in range(temp):
   
10.         list_deff = list_nums[i]
    
11.         list_column = [1]
    
12.         for j in range(1, n-i-1):
    
13.             num = list_column[-1] + list_deff[j]
    
14.             list_column.append(num)
    
15.             if num not in list_kap:
    
16.                 list_kap.append(num)
    
17.         list_nums.append(list_column)
    
18.     return list_kap
    
19. 
    
20. # 给出i_end以内的素数表            
    
21. def crt_pri(i_end):
    
22.     mark_pri = [True for i in range(i_end + 1)]
    
23.     mark_pri[0], mark_pri[1] = False, False
    
24.     for i in range(2, i_end + 1):
    
25.         if mark_pri[i] == True:
    
26.             for j in range(i + i, i_end + 1, i):
    
27.                 mark_pri[j] = False
    
28.     nums_pri = [i for i,j in enumerate(mark_pri) if j == True]
    
29.     return nums_pri
    
30. 
    
31. # 将所给列表中的数进行平方
    
32. def list_square(list_og):
    
33.     list_aim = []
    
34.     for each in list_og:
    
35.         list_aim.append(each*each)
    
36.     return list_aim
    
37. 
    
38. # 将所给列表中不满足squarefree条件的数移除
    
39. def judge(list_og):
    
40.     list_pri = list_square(crt_pri(int(list_og[-1]**0.25) + 1))
    
41.     for each in list_og:
    
42.         for i in list_pri:
    
43.             if each%i:
    
44.                 continue
    
45.             else:
    
46.                 list_og.remove(each)
    
47.                 break
    
48.     return list_og
    
49. 
    
50. # 将满足条件的数加起来
    
51. def sqarefree_kap(n):
    
52.     t_start = t.time()
    
53.     sum_sqf = 0
    
54.     list_kap = judge(crt_list(n))
    
55.     for each in list_kap:
    
56.         sum_sqf += each
    
57.     t_end = t.time()
    
58.     print(t_end - t_start)
    
59.     return sum_sqf

复制代码