Beginning of an outline of a proof... arc> (dedup:mapn [mod-expt 2 _ 100] 2 100) (4 8 16 32 64 28 56 12 24 48 96 92 84 68 36 72 44 88 76 52) That's the cy

Beginning of an outline of a proof... arc> (dedup:mapn [mod-expt 2 _ 100] 2 100) (4 8 16 32 64 28 56 12 24 48 96 92 84 68 36 72 44 88 76 52) That's the cycle of powers of 2 mod 100. (I removed the beginning 1 and 2, which don't repeat.) The first two numbers will show up as 04 and 08 in our number (except when the number is 4 or 8). Thus, there's always a 0 when n is 2 or 3 mod 20. (Note that there are 20 numbers up there.) arc> (no:prn:dedup:mapn [string:num->digs (mod-expt 2 _ 1000) 10 3] 3 1000) (008 016 032 064 128 256 512 024 048 096 192 384 768 536 072 144 288 576 152 304 608 216 432 864 728 456 912 824 648 296 592 184 368 736 472 944 888 776 552 104 208 416 832 664 328 656 312 624 248 496 992 984 968 936 872 744 488 976 952 904 808 616 232 464 928 856 712 424 848 696 392 784 568 136 272 544 088 176 352 704 408 816 632 264 528 056 112 224 448 896 792 584 168 336 672 344 688 376 752 504) That's the cycle of powers of 2 mod 1000, starting with n=3. There are 100 numbers. (Incidentally, the Euler-Fermat theorem and some thinking can tell you that the cycle of powers of 2 mod 10^k will have length that divides phi(5^k), which is 4 * 5^(k-1), which is 4, 20, 100, 500, etc.) I'll make my computer figure out which numbers contain 0. arc> (let u (dedup:mapn [string:num->digs (mod-expt 2 _ 1000) 10 3] 3 1000) (keep [pos #\0 u._] (range 0 dec:len.u))) (0 1 2 3 7 8 9 14 19 20 39 40 59 60 76 79 80 85 99) Which is 19 out of the 100 different things mod 1000. Now let's write a function to deal with 10^k. (def ass (k) (withs (pt (expt 10 k) u (dedup:mapn [string:num->digs (mod-expt 2 _ pt) 10 k] k (+ k (* 4 (expt 5 dec.k))))) (list (count [pos #\0 _] u) len.u))) To explain the above code: I let "pt" = 10^k, then I take the numbers from k to k + 4 * 5^(k-1), find 2^n (mod pt), write out its digits in base 10 (and force there to be k digits, by appending 0's to the front if necessary), put the digits together into a string, make a list of all these resulting strings, remove duplicates just to be sure, and give the resulting list the name "u"; then I return a list of two numbers, the number of strings in the list that contain 0, and the total number of strings in the list. From what we've seen above, we'd expect (ass 2) to return (2 20), and (ass 3) to return (19 100). arc> ass.2 (2 20) arc> ass.3 (19 100) That's a good sign. Now let's proceed to higher numbers. I'll make it print out the resources it's using, too. arc> time:ass.4 time: 30 gc: 0 mem: 2458488 (136 500) arc> time:ass.5 time: 338 gc: 169 mem: -21400960 (862 2500) arc> time:ass.6 time: 905 gc: 141 mem: -2376232 (5129 12500) arc> time:ass.7 time: 4333 gc: 227 mem: 43046240 (29330 62500) arc> time:ass.8 time: 28885 gc: 1797 mem: 74515640 (163232 312500) Well, we've passed the halfway mark, but my computer is feeling the pressure. If you rewrote this in C or something, you might be able to go up a few numbers higher, but probably not much. (Hmm, actually, I'm kind of repeating a bunch of work: I already know that "2 and 3 mod 20" numbers always have a 0, and similar for "3 4 5 6 10 ... mod 100 [add 3 to my third list of numbers]". However, if I ignored those, that would only cut out half the work for k=8. But maybe a lot more will get cut out in higher numbers, and the number of things to deal with will become manageable?) Well, in principle at least, this could be solved by computer. Edit: Hmm, qntm seems to have said much of this already. Well, at least I have done some grunt work to illustrate his arguments.