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:
| (1,_,_) | (1,2,_) | (1,2,3) |
| (1,2,-2) | ||
| (1,2,0) | ||
| (1,-1,_) | (1,-1,1) | |
| (1,-1,0) | ||
| (1,0,_) | (1,0,2) | |
| (1,0,-1) | ||
| (1,0,0) | ||
| (0,_,_) | (0,1,_) | (0,1,2) |
| (0,1,-1) | ||
| (0,1,0) | ||
| (0,0,_) | (0,0,1) | |
| (0,0,0) |
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