The square of a sum and the sum of cubes

Let’s start with a fun fact: Take the first \(n\) integers. Add them and then square the result; call this \(S\). Take the cube of each and add those numbers; call this \(C\). It will always be the case that \(S = C\). For instance, take \((1, 2, 3)\): \[(1 + 2 + 3)^2 = 6^2 = 36 \\ 1^3 + 2^3 + 3^3 = 1 + 8 + 27 = 36\]

This can be used to create problems such as “Find the values for a, b, and c if:” \[a^2 = a^3 \\ (a + b)^2 = a^3 + b^3 \\ (a + b + c) ^2 = a^3 + b^3 + c^3\]

Obviously, one solution is \((a, b, c) = (1, 2, 3)\). But that raises the question: Is that the only solution? Note that there are no constraints on possible values for a, b, and c in the original problem.

Starting with the first line, there are two solutions. We can find them by trial and error or by graphing, or we can find them through algebra: \[a^2 = a^3 \implies \\ a^3 – a^2 = 0 \implies a^2\cdot(a – 1) = 0 \implies \\ a^2 = 0 \wedge a – 1 = 0 \implies a \in \{0, 1\} \]

Using \(a =0\) erases it from the other equations, making the problem effectively: \[b^2 = b^3 \\ (b + c) ^2 = b^3 + c^3 \]

This has an obvious solution of \((b, c) = (1, 2)\). But note that b could also equal 0. That would make the problem, effectively, \(c^2 = c^3\). This gives us a total of four possible solutions: \[(a, b, c) \in \{(1, 2, 3), (0, 1, 2), (0, 0, 1), (0, 0, 0)\}\]

We can keep playing with this idea of 0 leading to so-called degenerate versions of the problem. We can actually use 0 for any of the three variables, and doing so effectively erases it from the problem. For instance, consider the solution set (1, 0, 2): \[1^2 = 1^3 = 1 \\ (1 + 0)^2 = 1^3 + 0^3  = 1 \\ (1 + 0 + 2) ^2 = 1^3 + 0^3 + 2^3 = 9\]

This gives us a total of \(2^3\) possible solutions: \[(a, b, c) \in \{(1, 2, 3), (0, 1, 2), (1, 0, 2), (1, 2, 0), \\  (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 0, 0)\}\]

We’re still not done yet. If we allow negative numbers (and,  again, there are no constraints in the original problem), we can cancel out values, since \(1 – 1 = 0\) and \(1^3 – (-1)^3 = 0\). We can’t do this entirely randomly, though; there’s an algorithm which I’ll detail below. However, what it means is for the problem above is that we have a total of thirteen possible solution sets: \[(a, b, c) \in \{(1, 2, 3), (0, 1, 2), (1, 0, 2), (1, 2, 0), \\  (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 0, 0), (1, 2, -2), \\ (0, 1, -1), (1, 0, -1), (1, -1, 0), (1, -1, 1)\}\]

This is an exhaustive list of solutions to the original problem. Note that we could add certain constraints, such as requiring that all numbers be positive, or all numbers be different.

The Algorithm

The list of solutions gets large rather quickly. For five variables, it’s 96; for six, it’s 267. There’s an algorithm for determining the sets, as suggested above; it can be seen in terms of a counter starting at 0. For each successively variable, we have up to three choices: Increase the current counter, decrease the current counter, or keep the counter the same. The option to decrease is not available if our current counter is 0.

That may be easier to understand by using the example above. The first digit is always 0 or 1; those are the only solutions to \(a^2 = a^3\). If our first digit is 1, our next digit can increase this to 2, decrease it to 0, or keep it at 1. We increase it simply by using 2; we can decrease it with -1; we can keep it the same with 0. If our second digit is 0, we have the same options we started with: 0 or 1.

Our second digit, then, can be 0, 1, or 2. If our second digit is 0, we have the same options again: 0 or 1. If our second digit is 1, we can increase to 2, decrease to 0, or stay at 1. If our second digit is 2, we can increase to 3, decrease to 1, or stay at 2.

The table below shows all possibilities, based on increasing, decreasing, or staying (in that order) at each step:

Pseudocode for deriving all possible paths:

Let Counter = 0
Dimension Solutions(3^N)
For I = 1 to N
  Add a solution:
    Counter++
    Put Counter in Solutions(?) slot I
  If Counter > 0 then add a solution:
    Put Counter in Solutions(?) slot I
    Counter--
  Add a solution:
    Put Counter in Solutions(?) slot I
Next I

Because the counter can only be decreased if it’s greater than 0, the actual number of solutions is always less than \(3^n\). For the first four cases, the number of solutions is \(2^{n-1}+3^{n-1}\), but after that, the number of solutions falls below that mark, too.

The number of possible solutions is a series that exists for other mathematical reasons. This passage most closely resembles the problem above: “number of paths in an n X n grid from (0,0) to the line x=n-1, using only steps U=(1,1), H=(1,0) and D=(1,-1)”. U, H, and D correlate to increasing, staying, and decreasing, respectively.

Note that this particular problem starts at the third item in the series (2), not the first. Thus, if you wanted to know the number of possibilities for n = 10 (that is, \[(a + b + c + d + e + f + g + h + i + j)^2 = \\ a^3 + b^3 + c^3 + d^3 + e^3 + f^3 + g^3 + h^3 + i^3 + j^3\] ), you’d look at the twelfth element in the series (143,365).

Also keep in mind that this is a method for finding all of the solutions to the system of equations represented by: \[\left(\sum_1^i a_i\right)^2 = \sum_1^i \left(a_i\right)^3 | i_1^n \] not to the final equation itself. For instance, \[a^2 = a^3 \\ (a + b)^2 = a^3 + b^3\] has five solutions, but \[(a + b)^2 = a^3 + b^3\] by itself has an infinite number of solutions.

Testing the Algorithm

My go-to for testing quick programs is Excel VBA. It’s clunky and ugly as programming languages go, but I’m familiar enough with it that I don’t have to fret about GUI issues, and it has a handy worksheet for dropping results into as needed. My particular implementation requires adjusting the actual code for different values of n (and hence wouldn’t work for, say, n=100), but it does demonstrate that my algorithm generates valid solutions. It doesn’t prove that my solution set is exhaustive; I do welcome anyone to prove either that my algorithm is indeed exhaustive or if it misses solutions.

Here’s the code for n=7:

Sub SquaresCubes()
  Dim Step1, Step2, Step3, Step4, Step5, Step6, Step7, Stack
  Dim Cell1, Cell2, Cell3, Cell4, Cell5, Cell6, Cell7, RowPointer

  RowPointer = 1
  For Step1 = 0 To 1
    For Step2 = -1 To 1
    If Step1 + Step2 >= 0 Then
      For Step3 = -1 To 1
      If Step1 + Step2 + Step3 >= 0 Then
        For Step4 = -1 To 1
        If Step1 + Step2 + Step3 + Step4 >= 0 Then
          For Step5 = -1 To 1
          If Step1 + Step2 + Step3 + Step4 + Step5 >= 0 Then
            For Step6 = -1 To 1
            If Step1 + Step2 + Step3 + Step4 + Step5 + Step6 >= 0 Then
              For Step7 = -1 To 1
              If Step1 + Step2 + Step3 + Step4 + Step5 + Step6 + Step7 >= 0 Then

                Stack = Step1
                Cell1 = Step1
                PushPop Stack, Step2, Cell2
                PushPop Stack, Step3, Cell3
                PushPop Stack, Step4, Cell4
                PushPop Stack, Step5, Cell5
                PushPop Stack, Step6, Cell6
                PushPop Stack, Step7, Cell7

                Cells(RowPointer, 1) = "(" & Step1 & ", " & Cell2 & ", " & Cell3 & ", " & Cell4 & ", " _
                  & Cell5 & ", " & Cell6 & ", " & Cell7 & ")"
                Cells(RowPointer, 2) = (Cell1 + Cell2 + Cell3 + Cell4 + Cell5 + Cell6 + Cell7) ^ 2
                Cells(RowPointer, 3) = Cell1 ^ 3 + Cell2 ^ 3 + Cell3 ^ 3 + Cell4 ^ 3 + Cell5 ^ 3 + _ 
                  Cell6 ^ 3 + Cell7 ^ 3
                RowPointer = RowPointer + 1

              End If
              Next Step7
            End If
            Next Step6
          End If
          Next Step5
        End If
        Next Step4
      End If
      Next Step3
    End If
    Next Step2
  Next Step1

End Sub

Sub PushPop(ByRef StackVal, ByRef StepVal, ByRef CellVal)
  If StepVal = 1 Then
    StackVal = StackVal + 1
    CellVal = StackVal
  ElseIf StepVal = -1 Then
    CellVal = -StackVal
    StackVal = StackVal - 1
  Else
    CellVal = 0
  End If
End Sub