123456789. How many ways are there to insert + and – between the numbers and create a formula for 100? With pen and ink it takes a long time to answer. With programming, the answer will flash up in an instant:

01. 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
02. 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100
03. 1 + 23 - 4 + 5 + 6 + 78 - 9 = 100
04. 1 + 23 - 4 + 56 + 7 + 8 + 9 = 100
05. 12 - 3 - 4 + 5 - 6 + 7 + 89 = 100
06. 12 + 3 + 4 + 5 - 6 - 7 + 89 = 100
07. 12 + 3 - 4 + 5 + 67 + 8 + 9 = 100
08. 123 - 4 - 5 - 6 - 7 + 8 - 9 = 100
09. 123 + 4 - 5 + 67 - 89 = 100
10. 123 + 45 - 67 + 8 - 9 = 100
11. 123 - 45 - 67 + 89 = 100

And the beauty of programming is that you can easily generalize the problem to other bases. In base b, how many ways are there to insert + and – in the block [12345…b-1] to create a formula for b^2? When b = 10, the answer is 11. When b = 11, it’s 42. Here are two of those formulae in base-11:

123 - 45 + 6 + 7 - 8 + 9 + A = 100[b=11]
146 - 49 + 6 + 7 - 8 + 9 + 10 = 121

123 + 45 + 6 + 7 - 89 + A = 100[b=11]
146 + 49 + 6 + 7 - 97 + 10 = 121

When b = 12, it’s 51. Here are two of the formulae:

123 + 4 + 5 + 67 - 8 - 9A + B = 100[b=12]
171 + 4 + 5 + 79 - 8 - 118 + 11 = 144

123 + 4 + 56 + 7 - 89 - A + B = 100[b=12]
171 + 4 + 66 + 7 - 105 - 10 + 11 = 144

So that’s 11 formulae in base-10, 42 in base-11 and 51 in base-12. So what about base-13? The answer may be surprising: in base-13, there are no +/- formulae for 13^2 = 169 using the numbers 1 to 12. Nor are there any formulae in base-9 for 9^2 = 81 using the numbers 1 to 8. If you reverse the block, 987654321, the same thing happens. Base-10 has 15 formulae, base-11 has 54 and base-12 has 42. Here are some examples:

9 - 8 + 7 + 65 - 4 + 32 - 1 = 100
98 - 76 + 54 + 3 + 21 = 100

A9 + 87 - 65 + 4 - 3 - 21 = 100[b=11]
119 + 95 - 71 + 4 - 3 - 23 = 121

BA - 98 + 76 - 5 - 4 + 32 - 1 = 100[b=12]
142 - 116 + 90 - 5 - 4 + 38 - 1 = 144

But base-9 and base-13 again have no formulae. What’s going on? Is it a coincidence that 9 and 13 are each one more than a multiple of 4? No. Base-17 also has no formulae for b^2 = 13^2 = 169. Here is the list of formulae for bases-7 thru 17:

1, 2, 0, 11, 42, 51, 0, 292, 1344, 1571, 0 (block = 12345...)
3, 2, 0, 15, 54, 42, 0, 317, 1430, 1499, 0 (block = ...54321)

To understand what’s going on, consider any sequence of consecutive integers starting at 1. The number of odd integers in the sequence must always be greater than or equal to the number of even integers:

1, 2 (1 odd : 1 even)
1, 2, 3 (2 odds : 1 even)
1, 2, 3, 4 (2 : 2)
1, 2, 3, 4, 5 (3 : 2)
1, 2, 3, 4, 5, 6 (3 : 3)
1, 2, 3, 4, 5, 6, 7 (4 : 3)
1, 2, 3, 4, 5, 6, 7, 8 (4 : 4)

The odd numbers in a sequence determine the parity of the sum, that is, whether it is odd or even. For example:

1 + 2 = 3 (1 odd number)
1 + 2 + 3 = 6 (2 odd numbers)
1 + 2 + 3 + 4 = 10 (2 odd numbers)
1 + 2 + 3 + 4 + 5 = 15 (3 odd numbers)
1 + 2 + 3 + 4 + 5 + 6 = 21 (3 odd numbers)
1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 (4 odd numbers)

If there is an even number of odd numbers, the sum will be even; if there is an odd number, the sum will be odd. Consider sequences that end in a multiple of 4:

1, 2, 3, 4 → 2 odds : 2 evens
1, 2, 3, 4, 5, 6, 7, 8 → 4 : 4
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 → 6 : 6

Such sequences always contain an even number of odd numbers. Now, consider these formulae in base-10:

1. 12 + 3 + 4 + 56 + 7 + 8 + 9 = 99
2. 123 - 45 - 67 + 89 = 100
3. 123 + 4 + 56 + 7 - 89 = 101

They can be re-written like this:

1. 1×10^1 + 2×10^0 + 3×10^0 + 4×10^0 + 5×10^1 + 6×10^0 + 7×10^0 + 8×10^0 + 9×10^0 = 99

2. 1×10^2 + 2×10^1 + 3×10^0 – 4×10^1 – 5×10^0 – 6×10^1 – 7×10^0 + 8×10^1 + 9×10^0 = 100

3. 1×10^2 + 2×10^1 + 3×10^0 + 4×10^0 + 5×10^1 + 6×10^1 + 7×10^0 – 8×10^1 – 9×10^0 = 101

In general, the base-10 formulae will take this form:

1×10^a +/- 2×10^b +/- 3×10^c +/– 4×10^d +/– 5×10^e +/– 6×10^f +/– 7×10^g +/– 8×10^h +/– 9×10^i = 100

It’s important to note that the exponent of 10, or the power to which it is raised, determines whether an odd number remains odd or becomes even. For example, 3×10^0 = 3×1 = 3, whereas 3×10^1 = 3×10 = 30 and 3×10^2 = 3×100 = 300. Therefore the number of odd numbers in a base-10 formula can vary and so can the parity of the sum. Now consider base-9. When you’re trying to find a block-formula for 9^2 = 81, the formula will have to take this form:

1×9^a +/- 2×9^b +/- 3×9^c +/- 4×9^d +/- 5×9^e +/- 6×9^f +/- 7×9^g +/- 8×9^h = 81

But no such formula exists for 81 (with standard exponents). It’s now possible to see why this is so. Unlike base-10, the odd numbers in the formula will remain odd what the power of 9. For example, 3×9^0 = 3×1 = 3, 3×9^1 = 3×9 = 27 and 3×9^2 = 3×81 = 243. Therefore base-9 formulae will always contain four odd numbers and will always produce an even number. Odd numbers in base-2 always end in 1, even numbers always end in 0. Therefore, to determine the parity of a sum of integers, convert the integers to base-2, discard all but the final digit of each integer, then sum the 1s. In a base-9 formula, these are the four possible results:

1 + 1 + 1 + 1 = 4
1 + 1 + 1 - 1 = 2
1 + 1 - 1 - 1 = 0
1 - 1 - 1 - 1 = -2

The sum represents the parity of the answer, which is always even. Similar reasoning applies to base-13, base-17 and all other base-[b=4n+1].