13532385396179, the number which is its own prime factorization

Here is how you could, until just a couple of weeks ago, have made a thousand dollars by solving a math problem. The problem, with a bounty from John Conway, has to do with the prime factorization of integers. Take a number like \[120245675.\] This number, broken down to its prime factors, becomes
\[5 \cdot 5\cdot 11\cdot 17 \cdot 17 \cdot 17 \cdot 89.\]
Here we have sorted the factors from smaller to larger, and using exponent notation we can write the factorization as \[5^2\cdot 11 \cdot 17^3 \cdot 89.\]
Conway's weird idea was to consider the factorization itself as a new number by just reading the digits, including the exponents, from left to right:
\[521117389.\]
This would probably be frowned upon by many of my mathematician colleagues ("so typical of Conway!" I hear them say), who would point out that the operation is completely artificial and depends on writing the numbers in base 10.

But Conway is famous for inventing scientifically silly-looking puzzles and then asking (and answering!) extremely deep questions about them. He is the inventor of the famous Game Of Life that is believed to have wasted a substantial fraction of the world's computational resources in the last three decades of the twentieth century. Less well known is that, using Life-patterns discovered by various enthusiasts, he proved that basic questions about the game are undecidable in the sense of Turing and Gödel, and that self-replicating structures can be built in the game. And when he studied some simple two-person games, he happened to discover an amazingly rich theory of infinite numbers, now called the surreal numbers.

Anyway, Conway considered the function $f$ that maps a number to its prime-factorization-sorted-with-exponents-dropped-interpreted-in-base-10. And by the way, no, I don't think that this one will challenge the foundations of mathematics or the philosophy of science.

His 1000-dollar question was about what happens if we start with a number, apply the function $f$, and repeat.

If $N$ is a prime, then $f(N)=N$ and that's that. But for most other numbers, $f(N) > N$. For instance, the number $283439$ is certainly larger than $283\cdot 439$, since the former is more than 1000 times $283$ while the latter is only $439$ times $283$. And therefore $f(283\cdot 439) > 283\cdot 439$. It's easy to find examples where $f(N)<N$, like $f(512)=29$, but they require $N$ to have relatively few prime factors where at least one occurs to a power.

If we start from a number like 18, then in 3 steps we will reach 232, 2329, and 17137, which is prime. But if we start from 20, then after 50 iterations we will have reached a 66-digit (still non-prime) number with the numbers increasing in every step, and it seems entirely possible that the numbers will grow without limit, never reaching a prime.

There are deep and very precise results in number theory explaining how often one should expect to hit primes in a randomly increasing sequence of numbers. Basically the "probability" of a number being prime is inversely proportional to the number of digits, which means that a sequence that "only" grows exponentially can be expected to contain infinitely many primes, while slightly faster growing sequences might very well not contain any.

Iterating Conway's function will (under some assumptions of the numbers behaving like "average" numbers) lead to one of those sequences that grow just a smidgeon faster than exponentially (as long as it doesn't encounter a prime), so when it comes to iterating from a number like 20, it's not even clear (to me) what to guess based on the statistical properties of prime factorization.

This is what might have motivated Conway to award 1000 dollars for the proof or disproof of the statement that iterating $f$ starting from any integer $\geq 2$ will eventually lead to a prime. Just to demonstrate that silly looking problems can be extremely hard.

Nevertheless, the problem was recently solved by James Davis, an amateur mathematician, and there is already a Numberphile video on this.

What Davis decided to try was to refute Conway's conjecture by constructing a non-prime number $N$ for which $f(N)=N$.

On the whole, almost all numbers have their largest prime factor occurring to power 1 in their prime factorization. So it seems reasonable to search for an $N$ that ends in the digits of its largest prime factor, and Davis restricted his search to such numbers.

At first, this seems a bit weird. Could, for instance, a number that ends in the digits $7993$ be divisible by $7993$? Well, certainly! If we multiply $7993$ by anything divisible by $10000$, like $640000$, we will get a number that ends in four zeros. If we then add $7993$, making it $640001\cdot 7993$, we get a number, in this case $5115527993$, that ends in $7993$ and has $7993$ as one of its prime factors. This particular number doesn't give a counterexample to the Conway conjecture, but at least we have a method for finding candidates.

Now we could try all four digit primes say, and multiply them with numbers ending in 0001, checking whether we get a counterexample. But we can do even better. If instead we start from a number like $640001$, we can ask what it would take for a four digit prime $p$ to provide a counterexample of the form \[f(640001\cdot p) = 640001\cdot p.\]
Perhaps we can figure out what $p$ will have to be, instead of searching through all four-digit primes.

What we can do is to look at the prime factorization of the number $640001$. Provided all factors of $640001$ are smaller than $p$, $f(640001\cdot p)$ will consist of the digits of $f(640001)$ followed by the digits of $p$, which is \[f(640001)\cdot 10000 + p.\]
The equation \[f(640001)\cdot 10000 + p = 640001\cdot p\] now simplifies to
\[\frac{f(640001)}{64} = p.\]
The number $640001$ factorizes as $29^2\cdot 761$, which means that $f(640001) = 292761$. Since \[\frac{292761}{64}\] isn't even an integer, let alone a prime, we don't have to look further but can move on to computing \[\frac{f(650001)}{65}\] and so on.

This is what Davis did. Presumably he started by looking for a two-digit final prime, discovering the near-miss \[ \frac{f(1701)}{17} = \frac{f(3^5\cdot 7)}{17} = \frac{357}{17} = 21,\] that provides the equation \[35721 =  3^5\cdot 7 \cdot 21.\] If only $21$ had been a prime...

Then he moved on to searching for 3-, 4-, and 5-digit final primes, and eventually got to
\[\frac{f(140700001)}{1407} = \frac{f(13\cdot 53^2 \cdot 3853)}{1407} =\frac{135323853}{1407} =  96179.\]
Perhaps this was a moment of Bingo! rather than Heureka, but anyway, 96179 is not only a five-digit integer as required, but also a prime. Therefore the number
\[13532385396179 = 13\cdot 53^2\cdot 3853 \cdot 96179\] refutes the Conway conjecture.

The geeky part of me just loves weird coincidences like this one. I mean forget about $111111111^2$ and the multiplication table of $142857$, those are just what we expect in view of algebra, but this...

I don't know exactly in what order Davis was searching, but finding the counterexample must have taken no more than a tiny fraction of a second of computer time, since only a few thousand cases would need to be tried.

This perhaps doesn't seem too hard in retrospect, but to find it you have to dare search for the simplest type of counterexample even though it seems unlikely to exist. Notice that in order for this to work, the number $140700001$ had to have a fairly large repeated prime factor so that $f(140700001)$ becomes smaller than $140700001$, otherwise the quotient would have been greater than $10^5$ and therefore not five-digit. Then the number $f(140700001) = 135323853$, which has no simple arithmetical relation to $140700001$, had to be divisible by $1407$, and only one number in $1407$ is. Finally the quotient $96179$ had to be a prime number.  

As Davis eloquently commented on MathOverflow: "The point I took away was that there exist problems that look so hard, nobody has tried anything easy".