I'd thought of looking at this in the past, but never got round to doing it. However, recently Richard Fitzhugh announced that he'd found a bitstring that was prime when interpreted as a base-B number for bases B=2..9, and that he was interested in finding one that is prime when interpreted as base 10 as well.

Here's a table of the smallest bitstrings a(n) which are prime in all bases 2..n :

n | a(n) | length | discoverer |
---|---|---|---|

2 | 10 | 2 | Richard Fitzhugh |

3 | 10 | 2 | |

4 | 101111 | 6 | |

5 | 10010111 | 8 | |

6 | 111110100001 | 12 | |

7 | 111110100001 | 12 | |

8 | 11000011101101111 | 17 | |

9 | 10011110011011110110110011 | 26 | |

10 | 110100000010101111110001010011001110001 | 39 | Phil Carmody (Confirmed minimal by Jim Fougeron) |

11 | 1000000010000011110100010001000101001010110111001 | 49 | Andreas Höglund |

12 | 10100001011000101000110101011011011101111110100101011 | 53 | Jim Viebke |

I'd expect these to grow faster than exponentially, as they require a larger set of coincidences, and the numbers involved become progressively bigger as we look at higher bases. If you have any ideas what the heuristics for the growth rate should be, please drop me a note. I did have some outragiously unjustifiable ones which predicted a 10 solution by a length of 41, which I knew to be definitely an over-estimate (it didn't take into account things like residues modulo 3 being the same in several of the bases) - it appears this heuristic wasn't that far out after all. Don't ask me to explain them though!

Verification of the primality of the 10 values using Pari/GP has been done:

(10:45) gp > isprime(447045215857) %29 = 1 (12:32) gp > isprime(1851193010400469453) %30 = 1 (12:32) gp > isprime(95627998214513466021121) %31 = 1 (12:32) gp > isprime(439467878714199097912128751) %33 = 1 (12:33) gp > isprime(434924918653560794391998440369) %34 = 1 (12:33) gp > isprime(148875746530003785625335312352057) %35 = 1 (12:33) gp > isprime(23405900702264469207686840135749633) %36 = 1 (12:34) gp > isprime(2030059115079417390663329544965264491) %37 = 1 (12:34) gp > isprime(110100000010101111110001010011001110001) %38 = 1

Update - 2022/10/18 - Andreas passed on news of Jim's amazing 12

Update - 2008/02/14 - Andreas Höglund informs me of his wonderful 11

Update - 2003/08/24 - Jim Fougeron has confirmed the minimality of the above solution

Update - 2003/08/24 - Mike Oakes has some heuristics.

Last modified 2022/10/18, obviously

Another hastily constructed page by Phil Carmody

Home /
Maths /
Trivia /
multibase.html