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
- 46*256+195 which is
- 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)
- An Executable Prime Number? Phil Carmody's
- The first non-trivial executable prime The Prime Glossary's
- The smallest executable prime The Prime Curios'