Duncan's blog

December 12, 2009

Project Euler problem 44

Filed under: Project Euler,Python — duncan @ 3:08 pm
Tags: , ,

Problem 44:

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 is pentagonal and D = |Pk − Pj| is minimised; what is the value of D?

I’d originally made a start on this in Python, then gave up on it. Came back to it much later and tried doing it in ColdFusion. My solution there took too long to run, so I went back to my Python version and finished it off.

Here’s the code:

import math

def pentagonal(x):
	return x * (3 * x - 1) / 2

def isPentagonal(x):
        n = (math.sqrt((24 * x) + 1) + 1) / 6

        if n == int(n) and n > 0:
                return 1
        else:
                return 0

        
i = 0
pentagonals = []
solution = 0

while 1:
        i += 1
        p = pentagonal(i)

        for j in pentagonals:
                diff = abs(p - j)
                
                if isPentagonal(diff) == 1:
                        intSum = p + j
                        
                        if isPentagonal(intSum) == 1:
                            print("solution:", int(diff))
                            solution = 1
                            break

        if solution:
                break

        pentagonals.append(p)

The formula for calculating the pentagonal numbers is given to us. I already had a formula for the reverse, checking if a number is pentagonal, from problem 45.
To calculate the square root, I needed to import the math library.

Basically I loop until I find a solution. I calculate the pentagonal value of i. Then I subtract each pentagonal number smaller from it (but use the abs() function to get the absolute value).
If that difference is pentagonal, then I do a sum as well.
If that is also pentagonal, then our solution is the difference.
As I go along I append each pentagonal number into the array.
This solution runs in about 12 seconds for me.

Advertisements

1 Comment »

  1. […] previously blogged about this Project Euler puzzle over 5 years ago, using Python.  This is my approach using PHP as a simple practical exercise for myself, and I’d […]

    Pingback by Project Euler: problem 44 (PHP) – Pentagon numbers | Duncan's blog — October 13, 2014 @ 8:05 am | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: