You're reading: News

13532385396179 doesn’t climb to a prime

Someone called James Davis has found a counterexample to John H. Conway’s “Climb to a Prime” conjecture, for which Conway was offering \$1,000 for a solution.

The conjecture goes like this, as stated in Conway’s list of \$1,000 problems:

Let $n$ be a positive integer. Write the prime factorization in the usual way, e.g. $60 = 2^2 \cdot 3 \cdot 5$, in which the primes are written in increasing order, and exponents of $1$ are omitted. Then bring exponents down to the line and omit all multiplication signs, obtaining a number $f(n)$. Now repeat.

So, for example, $f(60) = f(2^2 \cdot 3 \cdot 5) = 2235$. Next, because $2235 = 3 \cdot 5 \cdot 149$, it maps, under $f$, to $35149$, and since $35149$ is prime, we stop there forever.

The conjecture, in which I seem to be the only believer, is that every number eventually climbs to a prime. The number 20 has not been verified to do so. Observe that $20 \to 225 \to 3252 \to 223271 \to \ldots$, eventually getting to more than one hundred digits without reaching a prime!

Well, James, who says he is “not a mathematician by any stretch”, had a hunch that a counterexample would be of the form $n = x \cdot p = f(x) \cdot 10^y+p$, where $p$ is the largest prime factor of $n$, which in turn motivates looking for $x$ of the form $x=m \cdot 10^y + 1$, and $m=1407$, $y=5$, $p=96179$ “fell out immediately”. It’s not at all obvious to me where that hunch came from, or why it worked.

The number James found was $13\,532\,385\,396\,179 = 13 \cdot 53^2 \cdot 3853 \cdot 96179$, which maps onto itself under Conway’s function $f$ – it’s a fixed point of the function. So, $f$ will never map this composite number onto a prime, disproving the conjecture. Finding such a simple counterexample against such stratospherically poor odds is like deciding to look for Lord Lucan and bumping into him on your doorstep as you leave the house.

A lovely bit of speculative maths spelunking!

via Hans Havermann, whom James originally contacted with his discovery.

3 Responses to “13532385396179 doesn’t climb to a prime”

  1. Avatar Matt McIrvin

    I think I see the logic behind the hunch… he was just assuming that the exponent of the biggest prime factor would be 1. Which, if you are exploring numbers beneath some threshold, say, would be the most likely value for it to have. Now I’m wondering whether there are other accessible counterexamples of this form and what happens when you look for terminal exponent 2, etc. Also other number bases, since this is so arbitrarily decimal.

    • Avatar Jimmy

      @Matt McIrvin : turns out I searched for other bases and found solutions

      base6 : 24 (16) = 2^4
      base8 : 33 (27) = 3^3
      base29 : 26 (64) = 2^6
      base11 : 3518 (4617) = 3^5 x 18 (3^5 x 19)
      base12 : 15287 (29767) = 15^2 x 87 (17^2 x 103)
      base2 : 111110011111110011 (255987) = 11^11 x 10011 x 111110011 (3^3 x 19 x 499)

      I also found a few pair, here is one :
      base2 : 10111011111 (1503) = 11^10 x 10100111 (3^2 x 167)
      base2 : 111010100111 (3751) = 1011^10 x 11111 (11^2 x 31)


(will not be published)

$\LaTeX$: You can use LaTeX in your comments. e.g. $ e^{\pi i} $ for inline maths; \[ e^{\pi i} \] for display-mode (on its own line) maths.

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>