Suppose we have a number in which the first digit is divisible by one (and isn’t zero), the first two are divisible by two, the first three are divisible by three, and so on all the way up to a ten digit number that is divisible by, unsurprisingly, ten. Such a number is called a polydivisible number, and I’m quite excited to be writing about them because in my opinion there isn’t enough written about these wonderful numbers.
While I’d like to focus this article on the discoveries I made while searching for the largest polydivisibles I could find, this being a maths blog I think it’s only fair I give you the opportunity to hunt for them yourselves. The challenge is to find the ten digit number I just described, using each of the digits zero through nine just once. (Spoiler alert: the solution is in a couple of paragraphs’ time.)
I first read about polydivisible numbers in Matt Parker’s brilliant Things to Make and Do in the Fourth Dimension. While he did investigate the details in a fair amount of depth, he was only able to give solutions for up to base 16—poor effort, Matt! A base is the mathematical way of expressing the number of digits available to us. Binary is made up of ones and zeroes, and so we call this base-2. When counting, we have ten digits (including zero), and therefore it is base-10 that is used in our day to day lives.
In base-10, the solution you hopefully found (don’t tell me you didn’t work it out!) is 3816547290. I’m a software developer myself and so the most interesting part for me was finding shortcuts to the answer. While a computer can find the solution by brute force fairly quickly, it still takes a bit of time as there are 3,628,800 possible answers to check: in computer science, we call these permutations.
I read a little further, and found out that indeed there were shortcuts that could be made—this is the power of mathematical thinking in problem-solving: a monumental task can become considerably easier by simply applying a little bit of thought. For example, we know that the first two digits represent a multiple of two, and therefore we only need to check permutations where the second digit is zero, two, four, six or eight. Applying this and a few other rules, I was able to solve the problem for base-10 in a mere 16 milliseconds. Perhaps saving a few milliseconds doesn’t sound too exciting, but in computing it can really make a difference. Saving a little bit of time in just one calculation, if it has to be repeated a billion times, is very beneficial. The graph below shows how much longer it takes to solve this puzzle when we add just one extra digit.
https://plot.ly/~rafaelprietocuriel/63/computation-time-spent-searching-permutations/
To finish, I did promise that I’d outdo the sixteen bases Matt was able to find—I don’t really think his effort was poor, but having a bit more development experience under my belt I was able to make optimizations leading to the discovery of all of the solutions up to base 30. After 9C3A5476B812D in base fourteen, I was able to find… no more! Perhaps base-14 is as high as you can go? So far, despite extensive research and calculations, I haven’t been able to find any number in a higher base. There’s certainly an opportunity for a proof or counterexample here.
And I’ll leave it at that—this was just one journey into a fairly abstract and arguably pointless use of numbers. The truth is, however, that it still provides a great adventure for anyone willing to embark on it.
If you’re interested in the software I used to solve this puzzle, or perhaps you’re looking to beat the base-30 I achieved, the code is available for free here.
More from Chalkdust
New largest prime number discovered!
Amaze your friends with our top facts about the new largest known prime number
Pandigital square numbers
Why are there none in base 13?
What’s your favourite number?
Favourite numbers for many are linked to birthdays or anniversaries, but here is our take on the question
What’s hot and what’s not, Issue 01
Be the envy of your friends with our guide to what's hot in maths right now
A Fields Medal at UCL: Klaus Roth
Klaus Roth and his work
£100 Prize Crossnumber, Issue 01
Our original £100 prize crossnumber. Download and enjoy!