计算三平方定理的 Python 代码

Question

一个正整数 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。）

Answer 1

你提到勒让德的三平方定理。这给出了一个数字 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()

Answer 2

我认为这是一个 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)

Answer 3

这可能有效：

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

Answer 4

它会起作用的

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

我正在使用勒让德的三平方定理