executable prime

A number can be represented as a string of bits, and so can a program. A prime number that represents an executable program (on some reasonable operating system) is an executable prime!

The most common processor with one byte instructions is the x86 line and on these the least positive executable number is 195.  The is the value of the one-byte program RET (return).  If this one byte is stored as a .com file, then it could be executed on a DOS machine (or a Windows machine in a DOS window).

According to Phil Carmody (see his well written link below), the three smallest executable primes on current hardware are the two byte programs:

  • 38*256+195 which is ES:RET (segment override).
  • 46*256+195 which is CS:RET (segment override).
  • 47*256+195 which is DAS; RET (decimal adjust for subtract, then exit).

(These should execute fine on any x86 system.)

If we do not require that the prime run on a current system, then Phil suggests the least executable prime is 199 (RST 0).  This instruction would perform a warm reset on a 8080 or Z80 machine running CP/M (both of which were common in 1980). Like the DOS .com files, CP/M executables required no headers, so this single byte is the whole program.

What about a non-trivial prime?  The first one ever found was a program that is apparently functionally equivalent to Charles Hannum's tiny C version of deCSS. Phil Carmody altered the code slightly to make the compiled version shorter, and created an 1811-digit prime.  See the first Prime Curios! link below.

See Also: Illegal

Related pages (outside of this work)

Printed from the PrimePages <t5k.org> © Reginald McLean.