Following his work on the
Illegal Prime Number,
Phil Carmody found the smallest executable
prime number on an
x86/
DOS system to be
9923.
This number is 38*256+195, the instruction
ES:RET, which may seem silly, but is acceptable, since an executable
program needs only to
terminate sucessfully. The
ES: prefix is simply a segment override.
I now present a version for
z80/
CP/M, found on
December 19, 2001 which I believe to be the smallest. The
assembly code is:
0x05 dec b
0xc9 ret
giving a value of 1481, and beats Phil's number by 8442. This is valid since CP/M allows raw machine code image programs, as
MS-DOS COM files.
(Update February 4, 2002: I have only tested this on CP/M plus on an Amstrad CPC6128 emulator, and could not get it to work... anyone with an older CP/M machine would be welcome to test it for me, and confirm that it does, in fact, work.)
The search is now on for a
CPU which allows a yet
smaller number. The program must be prime, and work on a system which doesn't require a header on executable files.
(Please note, I can't take any credit for the idea, but I can take a little credit for the small amount of work finding the z80 version. The original idea came from Phil Carmody and Professor Chris Caldwell).
Update, same day @ 13:54 GMT
Thanks to a lead from
ameoba(sic), I have inspected the
Intel 4004 instruction set, and believe that the following instruction should be executable, depending on the architecture.
BBL 0x1
This equates to
"Load A with 1, and branch back a level", and has the hex code 0xc1 or decimal 193.
(Maybe someone who is wise in the way of 4004 could /msg me and confirm that this is, in fact, executable; and whether there exists a machine which will allow a raw executable image)
Another update:
Phil got back to me and suggests:
dec b
rst nn
Where nn is any value that gives
rst nn <
ret. We need to find an os/platform where this is acceptible, to give, for example 1231 (for rst 08).