Highly divisible triangular number

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<

Download

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