Write a procedure which tests if given number is a sum of different squares in Scheme

Question

In our last exam we had to write procedure which find out if the given number can be written as a sum of square numbers of non equal numbers. smallest square must be 2^2, not an 1^2

e.g. - given number is 13 -> true because 13 be rewritten as 2^2 + 3^2 if given number is 8 -> false because 8 is 2^2 + 2^2 which is sum of equal squares.

I am stucked on finding the right algorithm. For example I will be given number 65. I have an idea to write helping procedure "squares" which always find sqr of given numbers (starting from 2^2) to given numbers or one more than 65. So for example 65 it will find 2^2 3^2 4^2 5^2 6^2 7^2 8^2 and now I do not know how to test the sum of all combination of squares if they will give the answer 65. Answer should be #true because 4^2 and 7^2 will give the result 65

edit 1:

I have written this code. It is not giving correct results (sum-sq 17) -> true

(define (sum-sq n)
  (sum-sq-help n 2))

(define (sum-sq-help n i)
  (if (or (= (sqr i) (/ n 2)) (= n 0))          
      #f
      (if (integer? (sqrt (- n (sqr i)))) #t (sum-sq-help n (+ 1 i)))))

edit 2: update - this is working fine

(define (sum-sq n)
  (sum-sq-help-2 n 2))

(define (sum-sq-help-2 n i)
    (cond ((= (sqr i) (/ n 2)) #f)
          ((< n (sqr i)) #f)
          ((= 1 (- n (sqr i))) #f)
          ((integer? (sqrt (- n (sqr i)))) #t)
          (else (sum-sq-help-2 n (+ 1 i)))))

Subtract successive squares from the number, and then check if that's a different perfect square. So when you subtract 65-4^2 you get 49, which is 7^2. — Barmar
Keep trying this for different n until n^2 is half the given number. — Barmar
@Barmar I have edited the description with an example. - when I call (sum-of.square-numbers 8) it will run in to infinite recursion :/ — stack93m

soegaard soegaard · Accepted Answer · 2019-02-06T11:06:10

Input: n
Output: Is n a sum of squares?

Algorithm:
1.  xs := {i^2 | 1<i^2<n}
2.  x  := n
3.  loop
      if  x<=1     then return false as the final result
      if  x in xs  then return true  as the final result
      x := x - (largest number in xs smaller than x)
    endloop

Write a procedure which tests if given number is a sum of different squares in Scheme

1 Answers