When Computers Struggle with Basic Arithmetic

Beneath the surface of a simple game from the New York Times is a monster that can subdue even the most powerful computer.

The new game from the New York Times is called Digits, and like their other games, its beauty is its simplicity.

Using some or all of the six given input numbers, as well as the four simple arithmetic operations of +, -, x, and ÷, your job is to arrive at the target -- in this case 62. After staring at this for a while, you might see that 62 = 10 x (5+1) + 2

That was an easy one, but the game progresses nicely to harder levels by using bigger targets that lie a little beyond the reach of the multiplication tables we all hazily remember from elementary school.

It's not difficult to write a program to play Digits. When the game was released for Beta testing in April I spent a happy couple of hours coding up my program in Python. And as you might expect, the program found each answer in just a fraction of a second.

But the code I wrote left me a little uneasy: the only way I could be sure to find an answer was to exhaustively test almost every possible path through this small thicket of numbers and operators hoping to blindly arrive at the target.  

That doesn't sound very efficient, and it quickly explodes in the number of operations you need to do if you try to apply it to more than six input numbers. But why would anyone want to do this?

Generalizing problems is what mathematics and computer scientists do. If solving a problem with six inputs is easy, it’s natural to wonder how high your approach can go. Some problems are extremely well behaved, and the steps required to solve them only grow in strict proportion to the number of inputs. If Digits had this property, we’d expect it to take twice as long to solve a problem with 12 inputs as it does to solve the one with six. These problems are called “linear”—if you plot the time taken against the number of inputs you get a straight line.

My program solved Digits with 6 inputs in about 1/10^th of a second, so if a linear method could be found it should be able to do 12 inputs in just 2/10^ths of a second. I knew the exhaustive approach of finding every path through all combinations of numbers and operators wasn’t linear, but I had to see how bad things were. After an hour of burning electricity I had to interrupt it—progress had been minimal.  

Surely there was a clever way to do this so that a computer could solve a Digits problem that had 10 or even 100 input numbers? I puzzled about this for a while, then turned to that almost magical resource for mathematicians and scientists, the Online Encyclopedia of Integer Sequences. Just about every problem involving numbers that mathematicians have studied is represented here one way or another. There are more than 300,000 of these sequences in the encyclopedia, including widely famous ones like the prime numbers, and the Fibonacci sequence, and a profusion of more obscure ones.

After a bit of searching, I hit upon the intriguing A060315 sequence which asks the closely related question: What is the first number than cannot be made with +, -, / and ÷  and just the numbers 1,2,3,…N where N is some maximum?  As I suspected, this problem had been studied, starting back in 2001, and updated as recently as last year.

As an example, it lists the smallest number that could not be made from 1,2 and 3 using just +, -, x, and ÷, as 10. Try it yourself: you can make every number up to and including 9, but not 10.

Interestingly, if there is ever a Digits game with the input numbers 1 through 6, and a target of 284, you will know that the editors are messing with you, since 284 is listed in the encyclopedia as the smallest number than cannot be made using 1,2,3,4,5 and 6.

The shocking thing about our friend, A060315, is how short it is. A handful of people have tried their programming skills at calculating terms in this sequence, devoting weeks of computer time trying to find the smallest number that cannot be made from the numbers 1 through N for successive values of N.

The furthest anyone has been able to calculate so far turns out to be 1 through 12. This was exactly the sequence I was testing with my naïve little program. The encyclopedia told me that 10,539,427 was the smallest target that could not be arrived at, so every number less than that had a solution. It had taken several weeks of run-time on a beefy computer to discover this.

The fact that nobody had been able to calculate the answer for 1 through 20, let alone 1 through 100, added weight to my suspicion that this problem was one of those beasts that appear to be inherently difficult for computers. Not difficult because we don’t know how to solve them, but because the only way we know how to solve them involves exhaustive search through an exponentially growing set of cases.

If linear problems are the meek, well-behaved, animals in the computational zoo, exponential problems are fire-breathing monsters that can easily overpower a supercomputer.

Computer Science students learn about this in a subject called Computational Complexity Theory, which studies the amount of work a computer has to do to solve different problems. Some of the hardest known problems are thought to be exponential in their time complexity.

Exponential is a word that gets used in common language to mean “very big”, but it has a more precise and ominous meaning. If something grows exponentially, it means that the time required for every additional input is a multiple of the time required to compute the previous one.

That may not sound too ominous, but even when the multiple is a very small number like 2, exponential functions can gobble up almost any resource surprisingly quickly.

The best known illustration of this is the wheat and chessboard legend of a king bankrupted by a promise to grant the inventor of chess 1 grain of wheat for the first square, 2 for the second, 4 for the third, 8 for the fourth, and so on.  The last square would hold 2⁶⁴ grains, which is a number with 20 digits, making the US national debt with its 14 digits seem modest indeed.

In the Digits game the problem is even worse. Here the multiple itself grows as the number increases, so code that solves 1 through 6 in 1/10^th of a second takes about 1 second to solve 1 through 7,  and  might take about two weeks to calculate the answer for 1 through 12.

Perhaps there was a smarter solution out there that I and the contributors to the encyclopedia hadn’t found? I turned to my long-time friend, David P. Anderson (the polymath known to New York Times science section readers for his proposed feature requests for the computer simulation that we might be living in), who also could not find a non-exponential algorithm, and doubts there is one. We were definitely not going to solve this problem up to 100.

But could we push the boundaries of knowledge at all here?  Dave quickly wrote code that executed about 10 times faster than my initial effort, and in another few days was able to get another factor of 10 speedup by tricks like changing programming languages and the way in which the data was represented in the program.

By doing so, and with only 7 hours of computer time, he was able to extend humanity's paltry knowledge of this problem from the previously known result for inputs 1 through 12 all the way to a probable solution for 1 through 13. That's right. We now know exactly one more term in this stubborn sequence. It is 95,492,777. Aren’t you glad you know that?

(I say probable, because Dave made the reasonable, but as yet unproven, assumption that we do not need to consider the division operator when it results in anything other than whole numbers.)

Calculating a 14^th number seems possible, but not without burning through energy like a crypto miner on a spree. A Digits game with 20 inputs might require 30,000 years of computer time, or a year for 30,000 CPUs working together. For the sake of the planet, let’s not go there.

We are living in the age of AI, where it seems that nothing is impossible for computers. So it’s almost comforting to know that at least for now there still remain problems involving small numbers and simple arithmetic that reliably stump even the biggest computer.