一個正整數 m 可以表示為三個平方的和，如果它的形式為 p + q + r 其中 p, q, r ≥ 0，并且 p, q, r 都是完全平方。例如，2 可以寫成 0+1+1，但 7 不能表示為三個平方和。第一個不能表示為三個平方和的數字是 7、15、23、28、31、39、47、55、60、63、71，……（參見勒讓德的三平方定理）。編寫一個 Python 函數 squares(m)，它以整數 m 作為輸入，如果 m 可以表示為三個平方和，則返回 True，否則返回 False。（如果 m 不是正數，您的函數應該返回 False。）
4 回答
qq_花開花謝_0
TA貢獻1835條經驗 獲得超7個贊
你提到勒讓德的三平方定理。這給出了一個數字 n 可以表示為三個平方和的條件：如果 n != 4^a(8b+7)。
這給出了一個簡單的 O(log(n)) 測試，用于打印小于 500 且不是三個平方和的數字。
def is_3square(n):
while n > 0 and n % 4 == 0:
n //= 4
return n % 8 != 7
for i in range(500):
if not is_3square(i):
print(i, end=', ')
print()
瀟瀟雨雨
TA貢獻1833條經驗 獲得超4個贊
我認為這是一個 NPTEL 問題。一開始我發現它很棘手，現在我已經完成了。
def threesquares(n):
list1=[]
flag=False
for i in range(0,100):
for j in range(0,100):
tempVar=(4^i)*(8*j)
list1.append(tempVar)
if n not in list1 and n > 0:
flag = True
else:
flag = False
return(flag)
largeQ
TA貢獻2039條經驗 獲得超8個贊
這可能有效：
failed = set( 7, 15, 23, 28, 31, 39, 47, 55, 60, 63, 71, 79, 87, 92, 95,
103, 111, 112, 119, 124, 127, 135, 143, 151, 156, 159, 167, 175, 183,
188, 191, 199, 207, 215, 220, 223, 231, 239, 240, 247, 252, 255, 263,
271, 279, 284, 287, 295, 303, 311, 316, 319, 327, 335, 343 )
def squares( m ) :
if m > 343 :
print( 'choose a smaller number' )
return m not in the failed
您可以使用一個簡單的公式創建任意大小的列表：4^i(8j+7), i >= 0, j >= 0
holdtom
TA貢獻1805條經驗 獲得超10個贊
它會起作用的
import math
def threesquares(m):
n=int(math.log10(m))
if n<1:
n=1
for a in range(n+1):
b=0
z=0
while z<=m:
z=((pow(4,a))*(8*b+7))
if z==m:
return False
b+=1
return True
我正在使用勒讓德的三平方定理
添加回答
舉報
0/150
提交
取消