You just gotta take a look at this one! It’s one of the absolutely coolest things I’ve seen recently 🙂 A virtual machine with internal state consisting of just one integer number! And its instruction codes are… fractions! Whoa. It’s Turing-complete and unlike Brainfuck and some other quirky esoteric languages it has this feeling of mathematical ellegance. I just love it! Not to mention that I almost made it to the top 20 on Project Euler this time 😀
A program written in the programming language Fractran consists of a list of fractions.
The internal state of the Fractran Virtual Machine is a positive integer, which is initially set to a seed value. Each iteration of a Fractran program multiplies the state integer by the first fraction in the list which will leave it an integer.
For example, one of the Fractran programs that John Horton Conway wrote for prime-generation consists of the following 14 fractions:
17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/2, 1/7, 55/1.Starting with the seed integer 2, successive iterations of the program produce the sequence:
15, 825, 725, 1925, 2275, 425, …, 68, 4, 30, …, 136, 8, 60, …, 544, 32, 240, …The powers of 2 that appear in this sequence are 2^(2), 2^(3), 2^(5), …
It can be shown that all the powers of 2 in this sequence have prime exponents and that all the primes appear as exponents of powers of 2, in proper order!If someone uses the above Fractran program to solve Project Euler Problem 7 (find the 10001st prime), how many iterations would be needed until the program produces 2^(10001st prime) ?
how did you do it? 🙂
Hehe, the same way others did – brute force ;]
any hints about how to a _fast_ brute force?
how big is the result (ie. how many decimal digits) ?
i doubt my current O(iterations) brute force can work. 1s for 100th prime, 3m for 500th, ??? for 10001st.. :-/
I used 2 simple optimization techniques, though not good enough. I suspect there’s a way to skip huge steps in the process. Or maybe a smart matrix transfer / compact automaton method. Dunno.
Mind shedding some lights on this? Thanks.
Of course it wasn’t pure brute force, rather a brute force technique refined with some optimizations possible thanks to observation of the behavior of the algorithm. It computed the result in 1m45s. Read about Fractran and its characteristics as a programming language. Better yet – learn programming in Fractran 🙂 Then dedicate some time to analyzing the algorithm and observing its behavior. The result is a 16-digit number so brute force per se obviously won’t work.
yay! i got it. added another optimization. now with those 3 tricks, solved it finally. 🙂
Any more hints? 🙂