2015-06-06

# Problem 060: Prime pair sets

Description:

The primes `3`, `7`, `109`, and `673`, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking `7` and `109`, both `7109` and `1097` are prime. The sum of these four primes, `792`, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

Solution:
vXXXX  /#...##     ####
XXX   #     #     ####
XXXXXX.     .     ####
XX    .     .     ####
XXX   .     .     ####
XXXXX #     #     ####
XXX   ##...##     ####

>55+12p   "d!"*22p   26522g+++62p   22g:*52p   12g22g*42p   523p v
v                             p232<   >032p     v
v              p0+1g26p0g26:" "<                                    _^#`g23g24<
>"X"32g:12g%62g+\12g/p32g>32g+:42g\`         #v_\$>32g1+:32p:12g%62g+\12g/g" "-|
^p/g21\+g26%g21:\" ":<  ^                            <
v                                                                              <
>52g     >1-:0\:22g%9+\22g/1+pv
|:                   <
v       \$<
>22g1+   >1-       :0\8\p     v
|:                   <
v       \$<
>22g     >1-:0\9+0p           v
|:                   <
v       \$<
>0  113p >  ::12g%62g+\12g/g"X"-#v_:13g8+0p:713gp22g13g1+:13p\`#v_v
|-g24:+1                <                                <
v       \$<                                                      <
>114p  024p  "@@@@` "+****34p  015p 025p 035p 045p 055p 065p     v
v                                                       <        <
>14g#v_34g.@
>14g1+5g1+:14g1+5p22g-#v_14g1-14p24g714g1+5g1+g-24p^
vg41g32g+1g5+1g417g42g43<
>-*+`#v_14g1-14p24g714g1+5g1+g-24p                  ^
v-1g41<
:>:1+5g1+14g1+5g9+\g#v_\$                            ^
>|:-1                <
\$
>14g1+5gv                                                >             >             >      >\$0v
v       <                                 >55+*\:v              >             >              \$1v
>:1+8\g#v_:::1\1+8\p36p9+0g26p1+v>:9+0g:26 g>\:#v_\$+:2\`#^_:2-!#^_:2%!#^_:9\`#^_:3%!#^_:5%!#^_1 :v
v2:<         ^\/+55<   v\                      p13:+1g13:_v#-3 <p1 3<
\$                    >2g-|<                 >:11p1-0\>:2% !#v_v    v ++!!+1-g< #    ^ <   >v
v       <                       \$<-                          ^\+1\/2< \    >3-#v_\$\$  1>31g\  !|>  |
g                  vp01p03p04 g11p12<        >:*11v1 >\$1   #\$^  :
2                  >120pv        v%g04*<v-1\    %g<^ \!!-1:<\$0  0
2                  vg030<  v-1\  < >10g^   >\:::*11  g%1-!\^>^
:                      >\$1\> :#v_ \$ 21g >:#^_\$1-!!  ^
+                  >:!#^_\1+\2v\ ^_^#!%2/\g03p<
1                  ^p02*2g02/ <>:*40g%20g2/:20^
v                                            g62\g62g0+9: <
^                                                      p+1g63+9\<<
>             >             >      >\$0v
>55+*\:v              >             >              \$1v
> \>\:#v_\$+:2\`#^_:2-!#^_:2%!#^_:9\`#^_:3%!#^_:5%!#^_1 :v
^\/+55<   v\                      p13:+1g13:_v#-3 <p1 3<
>:11p1-0\>:2% !#v_v    v ++!!+1-g< #    ^ < >:1^
^\+1\/2< \    >3-#v_\$\$  1>31g\  !|>|
vp01p03p04 g11p12<        >:*11v1 >\$1   #\$^>:0^
>120pv        v%g04*<v-1\    %g<^ \!!-1:<\$0
vg030<  v-1\  < >10g^   >\:::*11  g%1-!\^>^
>\$1\> :#v_ \$ 21g >:#^_\$1-!!  ^
>:!#^_\1+\2v\ ^_^#!%2/\g03p<
^p02*2g02/ <>:*40g%20g2/:20^
>24g714g1+5g1+g+24p14g1+14p14g5g14g1+5p v
>14g23g-|                    >24g714g1+5g1+g+34p v
>34g24g714g1+5g1+g+`#^_                  >14g1-14p24g7 v
^                                                    <p42-g+1g5+1g41<
This program is too big to display/execute here, click [download] to get the full program.

Explanation:

Wow, so this is now officially my biggest (in terms of file size) befunge program. The file has around ten megabyte. And probably also in terms of unique variables (26 variables plus two 2D-arrays)

The problem was also not that befunge-compatible. My solution is pretty similar with the one from MathBlog. We generate primes from `1` to `3300` and save verified pairs in an Hashmap. And when I say Hashmap I mean an fucking `3000x3000` array where every possible pair has an field (yay for befunge).

I had to use quite a few codesnippets from older project: My standard sieve of eratosthenes, an implementation of the Miller-Rabin primality test and method to concatenate two numbers.

In the end is to say that in befunge the program size is normally an good indicator for the runtime (not really, but its kinda correct for all my programs). So as you probably guessed this program takes a pretty loooooong time to complete. I even had to make some aspects dynamic so I could test it with only 4 concatenated primes (and an sieve of size 9000). Otherwise it would be impossible to debug it (or at least very tiresome).

 Interpreter steps: 8 609 996 835 Execution time (BefunExec): 33min (4.24 MHz) Program size: 3323 x 3360 Solution: 26033 Solved at: 2015-06-06

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