> Here’s the program written in Python. I used it to find every Munchausen number less than 500,000,000. After thirty minutes or so of intense computation, it t

> Here’s the program written in Python. I used it to find every Munchausen number less than 500,000,000. After thirty minutes or so of intense computation, it turns out that the only Munchausen numbers are 1 and 3435. This is an awfully long time to wait for something that is very clearly optimizable. If we are searching for Munchausen numbers, then we are probably going to do so in a brute force way. (We could optimize this with various symmetries, such as digit permutations, but let's ignore this for now.) If we are going to brute force it, then we are probably not going to exceed 64-bits, which means we can avoid using bignums altogether. Written correctly, this would be extremely fast in C. With this code [0], on my machine, with only meager optimization effort (not thinking too hard about things other than data types), I can go through 3 billion in less than a minute: > (time (find-munchausen 3000000000)) Computing all Munchausen numbers below three billion. Evaluation took: 57.087 seconds of real time 57.059879 seconds of total run time (56.840355 user, 0.219524 system) 99.95% CPU 159,836,797,604 processor cycles 401,488 bytes consed (0 1 3435 438579088) The assembly code for the Munchausen test is relatively tight (though not at all as good as handwritten, of course), which makes evident why we check so quickly. ; 8E2: 4C8B05A7FFFFFF MOV R8, [RIP-89] ; #(0 1 4 27 ...) ; 8E9: 488BD9 MOV RBX, RCX ; 8EC: 0F1F4000 NOP ; 8F0: L0: 48BA9A99999999999919 MOV RDX, 1844674407370955162 ; 8FA: 488BC3 MOV RAX, RBX ; 8FD: 48F7E2 MUL RAX, RDX ; 900: 488BFA MOV RDI, RDX ; 903: 4883E7FE AND RDI, -2 ; 907: B814000000 MOV EAX, 20 ; 90C: 488BF7 MOV RSI, RDI ; 90F: 48D1FE SAR RSI, 1 ; 912: 480FAFF0 IMUL RSI, RAX ; 916: 4829F3 SUB RBX, RSI ; 919: 488BF3 MOV RSI, RBX ; 91C: 488BDF MOV RBX, RDI ; 91F: 498B44B001 MOV RAX, [R8+RSI*4+1] ; 924: 4839C8 CMP RAX, RCX ; 927: 7E0E JLE L2 ; 929: B917001020 MOV ECX, 537919511 ; 92E: L1: 488BD1 MOV RDX, RCX ; 931: 488BE5 MOV RSP, RBP ; 934: F8 CLC ; 935: 5D POP RBP ; 936: C3 RET ; 937: L2: 4829C1 SUB RCX, RAX ; 93A: 4885DB TEST RBX, RBX ; 93D: 75B1 JNE L0 ; 93F: 4885C9 TEST RCX, RCX ; 942: B917001020 MOV ECX, 537919511 ; 947: 41BB4F001020 MOV R11D, 537919567 ; T ; 94D: 490F44CB CMOVEQ RCX, R11 ; 951: EBDB JMP L1 [0] https://bitbucket.org/tarballs_are_good/lisp-random/raw/master/munchausen.lisp https://bitbucket.org/tarballs_are_good/lisp-random/raw/mast...