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).

Log in or register to write something here or to contact authors.