Labels

Project Euler #44: Pentagon numbers

Question
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?

Answer :  5482660

Hacker Rank Problem

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
25
26
27
28
29
30
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        SortedSet<Long> res = new TreeSet<Long>();

        for(long i=k+1;i<=n;i++)
        {
            long pn = (long)(i*((3*i)-1)/2);
            long j = i-k;
            long pNMinusK = (long)(j*((3*j)-1)/2);
            if(isPentagonal(pn-pNMinusK) || isPentagonal(pn+pNMinusK))
                res.add(pn);
        }
        Iterator it = res.iterator();
        while (it.hasNext())
            System.out.println(String.valueOf(it.next()));
    }
    
    private static boolean isPentagonal(long number)
    {
        double penTest = (Math.sqrt(1 + 24 * number) + 1.0) / 6.0;
        return penTest == ((long)penTest);
    }
}
Labels:

Comments

Post a Comment

Popular Posts