2014-09-11

# Problem 012: Highly divisible triangular number

Description:

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Solution:
# ... #
. . . .
.  .  .
. . . .
# ... #

v  p03+1g03 p04+1g04   p +3/g01\%g01:g04 g03 <
>"d"55+*:10p3"2"*:20p*00p230p" ":03p13p            v              >130p040p  > 30g:10g%\10g/3+g" "- 00g30g` !#v_          |
v                                                  <             _^#`g03g00 <^                        p03+1g03            <
> "X" 30g:10g%\10g/3+p30g >30g+ : 00g\`     #v_\$>30g1+:30p:10g%\10g/3+g" "- |
^p+3/g01\%g01:\" ":<  ^                           <
v                                                            +1\$<
>:1+2/>:01p31p111p0>::10g%\10g/3+g::*01g`#v_121p>:31g\%         !#v_11g21g*11p31g1-|
v        <    ^p13/\g13:p12+1g12<
v                      <          vp21<*2g11\$\$<^g11\$\$                                  <
>2 212p222p >:2%|                             >12g22g*"d"5*` #v_1+    1v
|                                   <                       0+1\$<
>:1+  >:01p31p111p0>::10g%\10g/3+g::*01g`#v_121p>:31g\%         !#v_11g21g*11p31g1-|
#   v        <  v ^p13/\g13:p12+1g12<
^p22<*2g11\$\$<^g11\$\$                                  <
>\$\$:1+*2/.@
^                                                                                                    \$p05-1g04<
This program is too big to display/execute here, click [download] to get the full program.

Explanation:

Here I was desperately in need of an efficient algorithm. So I copied this one from mathblog.dk and translated it into befunge. And I have to say it's amazingly fast.

 Interpreter steps: 38 855 123 Execution time (BefunExec): 7.57s (5.14 MHz) Program size: 1000 x 170 Solution: 76576500 Solved at: 2014-09-11

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