Project Euler Problem 45

Triangular, pentagonal, and hexagonal

Triangle, pentagonal, and hexagonal numbers are generated by the following formula:

Triangle    Tn=n(n+1)/2     1, 3, 6, 10, 15, ...
Pentagonal  Pn=n(3n−1)/2    1, 5, 12, 22, 35, ...
Hexagonal   Hn=n(2n−1)      1, 6, 15, 28, 45, ...

It can be verified that T285 = P165 = H143 = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

Same quadratic equation as previous problem number 44. So for triangle:

    m  = n(n+1)/2
    2m = n^2 +n
    n^2 + n - 2m = 0

    n = (sqrt(1+8m)-1)/2

for pentagonal:

    m = n(3n-1)/2
    3n^2 -n -2m = 0
    n = (1+sqrt(24m+1))/6

for hexagonal:

    m = n(2n-1)
    2n^2 -n -m = 0
    n = (1+sqrt(1+8m))/4

and brutforce python solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#!/usr/bin/python3

import math

def tri_d(n): return n*(n+1)/2
def tri_i(m): return (math.sqrt(1+8*m)-1)/2 

def pen_d(n): return n*(3*n-1)/2
def pen_i(m): return (1+math.sqrt(24*m+1))/6

def hex_d(n): return n*(2*n-1)
def hex_i(m): return (math.sqrt(1+8*m)+1)/4

i = 40756
while True:
        #print("I:%s" %i)
        t,p,h = tri_i(i),pen_i(i),hex_i(i)
        if t.is_integer() and p.is_integer() and h.is_integer():
            print("Answer %s" % i)
            break
        i += 1

it is super slow, i waited aron 30 mins and it’s still working, so i had have to find another way.

Hexagonal: 1,    6,     15, 28, 45, ...
Triangle:  1, 3, 6, 10, 15, ...

looks like hexagonal is subset of triangle set. So try to prove it:

    Triangle = n(n+1)/2
    lets n = 2m-1 -> Triangle = (2m-1)(2m-1+1)/2 = 2m(2m-1)/2 = m(2m-1)
    and we are have HEX formula

so we have to calculate HEX numbers and chek it is pentagonal.

python implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#!/usr/bin/python3

import math

def pen_i(m): return (1+math.sqrt(24*m+1))/6
def hex_d(n): return n*(2*n-1)

i = 144
while True:
    p = pen_i(hex_d(i))
    if p.is_integer():
        print("Answer: %s" % hex_d(i))
        break
    i += 1

and same algorith with erlang:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname p45
% vim:syn=erlang
-mode(compile).

pen_i(M) -> (math:sqrt(24*M+1)+1) / 6.
hex_d(N) -> N*(2*N-1).

main(_) -> io:format("Answer: ~p ~n", [t45(144)]).

t45(I) ->
    P = pen_i(hex_d(I)),
    case round(P) == P of
        true -> hex_d(I)
        ;_   -> t45(I+1)
    end.

this way pretty fast:

1
2
3
4
5
6
7
8
9
10
11
12
13

mkh@mkh-xps:~/work/mblog/pr_euler/p45$ time ./p45_1.py 
Answer: 1533776805

real    0m0.050s
user    0m0.049s
sys     0m0.004s
mkh@mkh-xps:~/work/mblog/pr_euler/p45$ time ./p45.erl 
Answer: 1533776805 

real    0m0.268s
user    0m0.252s
sys     0m0.044s