Project Euler with Befunge


Fork me on GitHub
2014-09-24

Problem 037: Truncatable primes

Description:

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.


Solution:
v          // Project Euler - Problem 37



# ... #
. . . .
.  .  .
. . . .
# ... #

>"d"45**:10p5"d"*:20p*00p230p" ":03p13pv    v075320        p090<
v                                      <                      _^#`g03g00<
>"X"30g:10g%\10g/3+p30g>30g+:00g\`       #v_$>30g1+:30p:10g%\10g/3+g" "-|
   >90g"= ",,.@        ^p+3/g01\%g01:\" ":<  ^                          <
v                                           <                                                                                                      <
          v            >#                       ># $#                                                                                      v# -1<
                       $   >v                                         >$\          v                                    < >::.55+,90g+90pv
>:!#v_70p9> :70g55+*+:00g\`|>::10g%\10g/3+g"X"-#^_::55+\`#v_:55+/1\:!#^_55+/\55+*\v>::10g%\10g/3+g"X"-#v_\:50p%50g55+/\:|>|              >\>:1-#^_$^
    >$"= ",,90g.@      ^   <                              >$          #^!:       #<                    >$$0         >    ^>              ^
                                                                                                                    ^1$$<
This program is too big to display/execute here, click [download] to get the full program.

Explanation:

The approach for this problem is to first iterate through the left-truncatable primes and test if these are right-truncatable. All with the help of our trusty companion the sieve of Eratosthenes.
Tricky was that the generation of left-truncatable primes, my original algorithm was recursive and I had to transform it to an iterative one for befunge.


Interpreter steps: 128 154 558
Execution time (BefunExec): 20s (6.19 MHz)
Program size: 2000 x 514
Solution: 748317
Solved at: 2014-09-24



made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript