Duncan's blog

November 2, 2008

Project Euler: problem 29

Problem 29:

Consider all integer combinations of ab for 2 <= a <= 5 and 2 <= b <= 5:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 <= a <= 100 and 2 <= b <= 100?

So we need to work out a^b for all values of a and b between 2 and 100, just get the distinct terms, and work out how many of them there are.

<cfset limit = 100>
<cfset numbers = "">

<cfloop index="i" from="2" to="#limit#">
	<cfloop index="j" from="2" to="#limit#">
		<!--- check it's not already in our array --->
		<cfif NOT ListFind(numbers, i^j)>
			<cfset numbers = ListAppend(numbers, i^j)>
		</cfif>
	</cfloop>
</cfloop>

<cfoutput>#ListLen(numbers)#</cfoutput>

So, two nested loops. This is possibly the first time in nine years of Coldfusion development that I’ve actually used the ^ operator. In fact I wasn’t even sure there was one.

In this problem I’ve used a list rather than an array, for a change. This is just for simplicity, because Coldfusion doesn’t have an ArrayFind function equivalent of ListFind (although there is one in CFLib.org).

So, ListFind to make sure we don’t store any value we’ve already stored, then ListLen to work out how many values there are.

This code isn’t the fastest; taking around 90 seconds to execute for me. After getting the correct answer, I remove the ListFind else-clause, and it took around 58 seconds. I then rewrote that version to use an array instead of a list, and it took under a second. This just reaffirms what has already been reported elsewhere; List functions are significantly slower than Array functions!

1 Comment »

  1. […] previously blogged about this Project Euler puzzle nearly 6 years ago, using ColdFusion.  This is my approach using PHP as a simple practical exercise for myself, and […]

    Pingback by Project Euler: problem 29 (PHP) | Duncan's blog — October 8, 2014 @ 8:00 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

Blog at WordPress.com.

%d bloggers like this: