Longest Consecutive Sequence Of Squares

December 11, 2015

Some numbers can be represented as the sum of a sequence of consecutive squares; for instance, 595 = 62 + 72 + 82 + 92 + 102 + 112 + 122. 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. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

13 Responses to “Longest Consecutive Sequence Of Squares”

  1. Rutger said

    in Python

    def longest_consequtive_squares(n):
    	results = []
    	for i in range(1,int(n**0.5+1)):
    		for j in range(i, int(n**0.5+2)):
    			if sum([x**2 for x in range(i,j)]) == n:
    				results.append(range(i,j))
    	if results:
    		results.sort(key=len, reverse=True)
    		return results[0]
    	else:
    		return None
    
    
    for n in range(1,1000):
    	print n, longest_consequtive_squares(n)
    
  2. Paul said

    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 None
    
  3. FA said
    package 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  ...
    }
    
  4. matthew said

    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 res
    
  5. Ernie said

    Is it known whether any integer can be represented as the sum of consecutive squares in more than one way?

  6. programmingpraxis said

    @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.

  7. matthew said

    @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 += 1
    

    Output so far:

    [(20449, 7, 39), (20449, 38, 48), (20449, 143, 143)]
    [(147441, 18, 76), (147441, 29, 77), (147441, 85, 101)]
    [(910805, 35, 140), (910805, 144, 178), (910805, 550, 552)]
    [(1026745, 1, 145), (1026745, 51, 147), (1026745, 716, 717)]
    [(2403800, 298, 322), (2403800, 368, 384), (2403800, 583, 589)]
    [(2513434, 66, 198), (2513434, 286, 313), (2513434, 473, 483)]
    [(3198550, 1, 212), (3198550, 127, 226), (3198550, 225, 275)]
    

    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).

  8. matthew said

    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).

  9. Paul said

    Here is a quadruple representation: 5545037505 (480, 1210), (3570, 3612), (3613, 3654), (7442, 7451)

  10. matthew said

    @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.

  11. matthew said

    @Paul: BTW, I think you meant 554503705. Good stuff anyway.

  12. Paul said

    @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 D
    
  13. Yuri said

    Java 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
    
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: