Pentagon numbers
Problem 044: Pentagon numbers
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:
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-#^_^
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 |