Python code to compute three square theorum

Question

A positive integer m can be expresseed as the sum of three squares if it is of the form p + q + r where p, q, r ≥ 0, and p, q, r are all perfect squares. For instance, 2 can be written as 0+1+1 but 7 cannot be expressed as the sum of three squares. The first numbers that cannot be expressed as the sum of three squares are 7, 15, 23, 28, 31, 39, 47, 55, 60, 63, 71, … (see Legendre's three-square theorem).

Write a Python function squares(m) that takes an integer m as input and returns True if m can be expressed as the sum of three squares and False otherwise. (If m is not positive, your function should return False.)

Answer 1

You mention Legendre's three-square theorem. That gives a condition for a number n to be expressible as the sum of three squares: if n != 4^a(8b+7).

That gives a simple O(log(n)) test, used here to print the numbers less than 500 that aren't the sum of three squares.

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

I think this is an NPTEL Question. I found it tricky at the first now I'm through with it.

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

This might work:

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

You may create the list of an arbitrary size using a simple formula: 4^i(8j+7), i >= 0, j >= 0

Answer 4

def threesquares(m):
    for p in range(0, m):
        for q in range(0, m):
            for r in range(0, m):
                if p*p + q*q + r*r == m:
                    return True
    return False

Answer 5

def threesquares(m):
   if(m-7)%8==0 or (m-28)%8==0 :
      return(False)
   else:
      return(True)

Answer 6

it will work

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

i am using Legendre's three-square theorem