python小练习（036）：渐进的完全平方数

jerryxjr1220

python小练习（035），传送门

今天我们来研究一下：渐进的完全平方数

正整数 n 被 d 除所得的商和余数分别为 q 和 r。此外，d，q 和 r 是一个等比数列中的连续三项，但未必是有序的。

例如，58 除以 6，商为 9，余数为 4。可知 4，6，9 是公比为 3/2 的等比数列中的连续三项。

我们将这样的 n 成为渐近数。

有的渐近数同时也是完全平方数，比如 9 和 10404=102**2。

100以内只有9既是渐进数又是完全平方数，所以100以内的完全平方渐进数之和是9.

100000 以下所有的完全平方渐近数之和是 124657。

求 10**8 以下所有完全平方渐近数之和。

qaz123765

程序效率不行

1. d=[]
   
2. a=[]
   
3. b=0
   
4. for i in range(2,105):
   
5.     k=i**2
   
6.     for j in range(2,k):
   
7.         
   
8.         s=k//j
   
9.         y=k%j
   
10.         if y!=0:
    
11.             
    
12.             a.append([j,s,y])
    
13.             #print(a)
    
14.             a[b].sort()
    
15.             #print(a[b])
    
16.             if a[b][2]/a[b][1]==a[b][1]/a[b][0]:
    
17.                 d.append(k)
    
18.             b+=1
    
19. 
    
20. d=list(set(d))
    
21. print(d)
    

复制代码

qaz123765

程序效率不行

1. d=[]
   
2. a=[]
   
3. b=0
   
4. for i in range(2,105):
   
5.     k=i**2
   
6.     for j in range(2,k):
   
7.         
   
8.         s=k//j
   
9.         y=k%j
   
10.         if y!=0:
    
11.             
    
12.             a.append([j,s,y])
    
13.             #print(a)
    
14.             a[b].sort()
    
15.             #print(a[b])
    
16.             if a[b][2]/a[b][1]==a[b][1]/a[b][0]:
    
17.                 d.append(k)
    
18.             b+=1
    
19. 
    
20. d=list(set(d))
    
21. print(d)
    

复制代码

JAY饭

想想怎么优化

1. def sh():
   
2.     n = 1
   
3.     while True:
   
4.         yield n**2
   
5.         if n**2 >=100000000:
   
6.             break
   
7.         n += 1
   
8. 
   
9. def x():
   
10.     count = 0
    
11.     for i in sh():
    
12.         for j in range(2,int(i)//2+1):
    
13.             t = i%j
    
14.             t1 = i//j
    
15.             t2 = j
    
16.             if (t*t1 == t2**2 or t*t2 ==t1**2 or t1*t2 ==t**2):
    
17.                 count += i
    
18.                 break
    
19.     print('')
    
20.     print(count)
    
21. 
    
22. x()
    
23.         

复制代码

        

JAY饭

算了，是错的

jerryxjr1220

JAY饭 发表于 2018-2-5 12:46
想想怎么优化

正向算走不通，就试试反向算

1. res = 0
   
2. for q in range(10000):
   
3.         for r in range(1,q):
   
4.                 n = q**3/r+r
   
5.                 if n%1 !=0: continue
   
6.                 if (n**0.5)%1!=0: continue
   
7.                 if n<10**8: res += n
   
8. print(res)

复制代码

JAY饭

我想到过这一种解法，但怎么都缕不清

JAY饭

jerryxjr1220 发表于 2018-2-5 17:37
正向算走不通，就试试反向算

我的疑惑是 n = q**3/r +r,  我先理解q肯定是除数，r肯定要比q小，这个好理解，但是
商是(q*q/r)中，是否漏掉了一种可能，这里只涉及q和r直接成连续比，但如果商数是等比数中，
中间的那个，因为题目说， 序数不固定。   那是否  商  可以写成这样 math.sqrt(q*r)

JAY饭

看着法制节目,我改了下迭代，先睡觉，明天继续

1. import math
   
2. res = 0
   
3. for q in range(10000):
   
4.         for r in range(1,q):
   
5.                 n = q**3/r+r
   
6.                 print(n)
   
7.    
   
8.                 n = q*math.sqrt(q*r)+r
   
9.                 print(n)
   
10.                
    
11.                 n = q*(r*( r/q)) +r
    
12.                 print(n)
    
13.                

复制代码

JAY饭

因为按大神你之前的写法，我打印100以下的所有渐进数，暂不算平方，结果漏掉了 20 ，因为20应该是渐进数
20 / 8 ，2 ，4. 所以我改写了下。。。可能是我题目理解有误

JAY饭

我终于知道你为什么这么写了
第二种情况，我试了一下，输出为0 。

1. res = 0
   
2. for q in range(1,10000):
   
3.         for r in range(1,q):
   
4.                 #因为余数r无论如何要小于除数，所以等比数列中r总比q小
   
5.                 #1，先假设除数q小于商数，所以商数q可以表示为q*(q/r)，商数不断增大
   
6.                 #2，假设除数大于商数，此时再假设商数也大于余数，发现
   
7.                 #这个时候，这个等式和上面的等式其实是一种方式，
   
8.                 #所以这两者等式就是一个等式
   
9.                 n = q**3/r+r
   
10.                 if (n**0.5)%1 ==0 and n<100000000:
    
11.                         res += n
    
12.                         print(n)
    
13. 
    
14. for q in range(1,10000):
    
15.         for r in range(q+1,10000):
    
16.                 #这里假设的第二种情况，商数小于余数，除数此时最大
    
17.                 #等式表示为 n =q*（r*r/q）+r,简化如下
    
18.                 n = r*r + r
    
19.                 if (n**0.5)%1 ==0 and n<100000000:
    
20.                         res += n
    
21.                         print(n)
    
22. print(res)
    

复制代码

jerryxjr1220

JAY饭 发表于 2018-2-6 09:06
我终于知道你为什么这么写了
第二种情况，我试了一下，输出为0 。

“除数，商，余数”为等比数列组成的数 和 “商，除数，余数”为等比数列组成的数 不是一回事么？

JAY饭

jerryxjr1220 发表于 2018-2-6 17:18
“除数，商，余数”为等比数列组成的数 和 “商，除数，余数”为等比数列组成的数 不是一回事么？{:10_25 ...

之前没绕出来