Project Euler Problem 44

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?

Link to original description

so, we have:

    m = n(3n - 1)/2
    2m = 3n^2 -n 
    3n^2 -n - 2m = 0 -- it is quadratic equation with roots:

    n1,2 = (1+/-sqrt(24m+1))/6 but n should be positive, so:

    n = (1+sqrt(24m+1))/6

and we have python solution:

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

#!/usr/bin/python3

import math

def fun_i(m): return (1 + math.sqrt(24*m+1)) / 6

def fun_d(n): return n*(3*n - 1) / 2


i, not_found = 1, True
while not_found:
    i += 1
    n = fun_d(i)
    for j in range(i-1,0,-1):
        n1 = fun_d(j)
        a, b = n-n1, n+n1
        p1, p2 = fun_i(a), fun_i(b)
        if p1.is_integer() == True and p2.is_integer() == True:
            print("n:%s n1:%s a:%s b:%s p1:%s p2:%s D:%s" % (n,n1,a,b,p1,p2, n-n1))
            not_found = False
            break

print("Answer: %s" % int(n-n1))

and same algorith with erlang

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

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

fun_i(M) -> (math:sqrt(24*M+1)+1) / 6.
fun_d(N) -> N*(3*N-1) / 2.

main(_) -> io:format("Answer: ~p ~n", [t44(2,1)]).

t44(I,0) -> t44(I+1,I);
t44(I,J) -> 
    {N, N1} = {fun_d(I), fun_d(J)},
    {P1,P2} = {fun_i(N-N1), fun_i(N+N1)},
    case {P1==round(P1), P2==round(P2)} of
        {true, true} -> round(N-N1)
        ;_           -> t44(I,J-1)
    end.

thats rare situation erlang 2 times faster python

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

mkh@mkh-xps:~/work/mblog/pr_euler/p44$ time ./p44.erl
Answer: 5482660 

real    0m1.144s
user    0m1.127s
sys     0m0.051s
mkh@mkh-xps:~/work/mblog/pr_euler/p44$ time ./p44.py
n:7042750.0 n1:1560090.0 a:5482660.0 b:8602840.0 p1:1912.0 p2:2395.0 D:5482660.0
Answer: 5482660

real    0m3.428s
user    0m3.427s
sys     0m0.004s
mkh@mkh-xps:~/work/mblog/pr_euler/p44$