Longest Consecutive Sequence Of Squares
December 11, 2015
This is similar to our previous exercise to find the longest consecutive sequence of odd numbers that sums to a given number, and is solved the same way: Initialize lo, hi, and sum to 1. If sum is less than the target, increase hi and add its square to sum. If sum is greater than the target, increase lo and subtract its square from sum. If sum is equal to the target, you’re done. If the square of the hi value exceeds the target before you have found a solution, then there is no solution.
(define (squares n)
(define (square x) (* x x))
(let loop ((lo 1) (hi 1) (sum 1))
(cond ((< n (* hi hi)) (list))
((< sum n) (loop lo (+ hi 1) (+ sum (square (+ hi 1)))))
((< n sum) (loop (+ lo 1) hi (- sum (square lo))))
(else (list lo hi)))))
Here is the opposite function that takes the two bounds and returns the sum of the squares within those bounds; it uses the function for the sum of the squares of the first n integers:
(define (sum-squares lo hi) (define (sum-squares n) (* n (+ n 1) (+ n n 1) 1/6)) (- (sum-squares hi) (sum-squares (- lo 1))))
Here are some examples:
> (squares 595)
(6 12)
> (sum-squares 6 12)
595
And here is A034705, which shows all the numbers that can be written as the sum of consecutive squares:
> (map (lambda (xs) (sum-squares (car xs) (cadr xs)))
(filter pair? (map squares (range 300)))))
(1 4 5 9 13 14 16 25 29 30 36 41 49 50 54 55 61 64 77 81 85
86 90 91 100 110 113 121 126 135 139 140 144 145 149 169 174
181 190 194 196 199 203 204 221 225 230 245 255 256 265 271
280 284 285 289 294)
You can run the program at http://ideone.com/121NjK.
Programming Praxis 
in Python
In Python.
def longest_conseq_sq(target): lo = hi = hisq = sumsq = 1 while hisq <= target: if sumsq < target: hi += 1 hisq = hi ** 2 sumsq += hisq elif sumsq > target: sumsq -= lo ** 2 lo += 1 else: return lo, hi return Nonepackage programmingpraxis // https://programmingpraxis.com/2015/12/11/longest-consecutive-sequence-of-squares/ // Some numbers can be represented as the sum of a sequence of consecutive squares; // for instance, 595 = 6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2. Other numbers are not so representable. // Your task is to write a program that finds the longest consecutive sequence of squares that sums to a given number, or determines that no such sequence exists. object LongestConsecutiveSequenceOfSquares { def squares(start: Int = 0): Stream[Int] = Stream.cons(start * start, squares(start + 1)) //> squares: (start: Int)Stream[Int] def squaresSum(start: Int = 0, sum: Int = 0): Stream[Int] = Stream.cons(sum + start * start, squaresSum(start + 1, sum + start * start)) //> squaresSum: (start: Int, sum: Int)Stream[Int] def sum(from: Int, to: Int): Int = squaresSum(from, 0).take(to - from + 1).lastOption.getOrElse(-1) //> sum: (from: Int, to: Int)Int def find(n: Int): Set[String] = { def find(n: Int, from: Int, to: Int): Set[String] = { val s = sum(from, to) if (s == n) Set(""+from+"^2 - "+ to+"^2") else if (s < n) find(n, from + 1, to+1) ++ find(n, from, to + 1) else Set() } find(n, 2, 2) } //> find: (n: Int)Set[String] find(595) //> res6: Set[String] = Set(6^2 - 12^2) find(2) //> res8: Set[String] = Set() (1 to 1000).map(n=>(n,find(n))).filter(!_._2.isEmpty).map(p=>p._1+": "+p._2.mkString(" or ")).mkString("\r\n") //> res9: String = 4: 2^2 - 2^2 //| 9: 3^2 - 3^2 //| 13: 2^2 - 3^2 //| 16: 4^2 - 4^2 //| 25: 5^2 - 5^2 or 3^2 - 4^2 //| 29: 2^2 - 4^2 ... }A Python solution using second order differences, so no multiplication:
def squaresum(n): d0, n0 = -1, 0; d1, n1 = 1, 1; t = 1 while t != 0: if t < n: d1 += 2; n1 += d1; t += n1 elif t > n: d0 += 2; n0 += d0; t -= n0 else: return (n, (d0+3)//2, (d1+1)//2) for res in filter(None,map(squaresum,range(1,301))): print resIs it known whether any integer can be represented as the sum of consecutive squares in more than one way?
@Ernie: Yes; 25 can be represented by the sequences (3 4) or (5). Of these, the longest is (3 4), so it is the desired sequence. The suggested solution will always find the longest sequence because it starts from 1 and increases.
@Ernie: good question. Many numbers have 2 representations, as @praxis says, 25 is the smallest, 365 is the smallest that isn’t a perfect square.
Here’s a modified program that will show us numbers with 3 or more representations:
def squaresums(n): d0, n0 = -1, 0; d1, n1 = 1, 1; t = 1; s = [] while t != 0: if t == n: s.append((n, (d0+3)//2, (d1+1)//2)) if t <= n: d1 += 2; n1 += d1; t += n1 else: d0 += 2; n0 += d0; t -= n0 return s n = 1 while True: s = squaresums(n) if len(s) > 2: print s n += 1Output so far:
No quadruple representations so far.
Another question: do numbers with a sum of consecutive squares representation become scarcer as the numbers grow? Experimentally, they seem to, so there is a possibility there is a only a finite number (apart from the perfect squares of course).
To answer my own question: of course there are an infinite number as we can generate new ones as differences of sums of squares. Still not sure about the density. Something like N^(2/3) might be about about right (there are approximately N^(1/3) sums of squares less than N, and we can choose 2 of them to take the difference).
Here is a quadruple representation: 5545037505 (480, 1210), (3570, 3612), (3613, 3654), (7442, 7451)
@Paul: Good stuff! How did you find that one? I’m guessing by generating all differences-of-sums-of-squares directly rather than checking each number for a representation.
Did some investigation of density, N^(2/3)/N seems about right, but I suspect my reasons for coming up with it in the first were bogus.
@Paul: BTW, I think you meant 554503705. Good stuff anyway.
@Matthew. Sorry for the typo. I first generate the cumulative sum of squares. Then simply loop over the start and the end indeces and fill a dictionary. The main problem is that the memory is filled up quickly. Therefore I limit the range for the dict.
def all_longest_conseq_sq(minimum, maximum): squares = [i**2 for i in range(int(math.sqrt(maximum)))] acc_squares = list(accumulate(squares)) D = defaultdict(list) for i, aci in enumerate(acc_squares): for j, acj in enumerate(acc_squares[i+1:], i+1): if minimum < acj - aci <= maximum: D[acj - aci].append((i+1, j)) return DJava Script
//task is to write a program that finds the longest consecutive sequence of squares that sums to a given number, or determines that no such sequence exists. var x = 190; // enter the number for checking here document.write("Number " + x); document.write(" is a sum of consecutive squares of following numbers (if any): "+ conseq(x)); function conseq(x){ var max = Math.sqrt(x); for (var i=1; i<= max; i++ ){ var solution =[]; var sum=0; var j=i; while (sum <= x){ sum += Math.pow(j, 2); solution.push(j); j += 1; if (sum == x) {return solution }; }; //end of while cicle }; return "no solution :(" }; //end of function