2014-12-10

Problem 044: Pentagon numbers

Description:

Pentagonal numbers are generated by the formula, `Pn=n(3n-1)/2`. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that `P4 + P7 = 22 + 70 = 92 = P8`. However, their difference, `70 - 22 = 48`, is not pentagonal.

Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference are pentagonal and `D = | Pk - Pj |` is minimised; what is the value of D?

Solution:
>v%%% %%%%       >    v
v06p09:/2*-1*3:p06::+1<vg07g09                         <<  <
g\$ >:70p:3*1   v #      >0v>vv p03+g03*2:p04-\g04+g03:<
v                      <3 pp2# v/4    <   >:30g+40g`! |
1#  >            4**1+:0^ 40>0g>:40g`#^_>:|:/4p03/2g03< \$
>-:|^6-p08:/2*-< #        >^ >30g2/30p4/^ >\$30g:*-30g\  |
8 >\$\$           ^v030:+1**46+g09g08             ># !#  # _^
>::**::**8*20p1 ^v>vv p03+g03*2:p04-\g04+g03:<@.-g08g0 9<
pp2# v/4    <   >:30g+40g`! |  ^5%6   <\$
40>0g>:40g`#^_>:|:/4p03/2g03< >\$     ^
>^ >30g2/30p4/^ >\$30g:*-30g\ #^_6%5-#^_^
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

My first attempt at this problem took over 5 hours to compute and had a complexity of O(n^3).

The problem is that you need a square root to inverse the pentagonal formula and Befunge has no square root function. So I needed to implement my own version of integer square roots in Befunge (see wikipedia). The program is still not really fast but it's good that I managed to speed it up to a time where you can execute it without waiting the whole night.

Also this program is nicely compact, by the time I'm writing this my Befunge interpreter BefunExec has gotten a display of all possible paths a program can take. And if you look at the graph of this program, it looks pretty interesting...

 Interpreter steps: 1 509 045 439 Execution time (BefunExec): 4min 18s (5.83 MHz) Program size: 60 x 11 (fully conform befunge-93) Solution: 5482660 Solved at: 2014-12-10

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