# Duncan’s blog

## November 11, 2008

### Project Euler: problem 21

Problem 21:

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a != b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

I passed over this one initially, and came back to it later. It wasn’t too difficult, but I got the wrong answer first time round.

We need to loop up to 9999. For each number (i), work out what its factors are, and add them up (let’s call this sum1). Then work out what the factors of sum1 are, and add them up (sum2). If i equals sum2, then i and sum1 are amicable numbers.

My mistake was forgetting to check that i and sum1 are different. It turns out several numbers seem to be amicable, but are the same. e.g. the factors of 6 are 1, 2 and 3, which add up to 6; but (6, 6) is not an amicable pair.

```<cfset d = StructNew()>

<cfscript>
function getFactors(x)
{
var i = 0;
var factors = ArrayNew(1);

for (i = 1; i LTE x/2; i = i + 1)
{
if (NOT x MOD i)
{	// its a factor
ArrayAppend(factors, i);
}
}

return factors;
}

function sumFactors(x)
{
var i = 0;
var sum = 0 ;

for (i = 1; i LTE ArrayLen(x); i = i + 1)
{
sum = sum + x[i];
}

return sum;
}
</cfscript>

<cfloop index="i" from="1" to="9999">
<cfset j = getFactors(i)>	<!--- factors of i --->
<cfset k = sumFactors(j)>	<!--- sum of those factors --->
<cfset l = getFactors(k)>	<!--- factors of that sum --->
<cfset m = sumFactors(l)>	<!--- sum of those factors --->

<cfif m EQ i AND NOT StructKeyExists(d, i) AND NOT StructKeyExists(d, k) AND i NEQ k>
<!--- amicable pair --->
<cfset d[i] = k>
<cfset d[k] = m>
</cfif>
</cfloop>

<cfset sum = 0>
<cfset d2 = StructKeyArray(d)>

<cfloop index="i" from="1" to="#ArrayLen(d2)#">
<cfset sum = sum + d[d2[i]]>
</cfloop>

<cfoutput>#sum#</cfoutput>
```

This code is pretty slow, taking about eight minutes to run. The PDF available after you complete it has a more optimised version. After doing a minor rewrite based on that, it only took 15 seconds! So ignore the code above, take a look at this instead:

```<cfscript>
function sumFactors(x)
{
var i = 0;
var sum = 1;

for (i = 2; i LTE SQR(x); i = i + 1)
{
if (NOT x MOD i)
{	// its a factor
sum = sum + i;
if (i NEQ (x / i))
sum = sum + (x / i);
}
}

return sum;
}
</cfscript>

<cfset sum = 0>

<cfloop index="i" from="1" to="9999">
<cfset j = sumFactors(i)>	<!--- sum factors of i --->
<cfset k = sumFactors(j)>	<!--- sum of those factors --->

<cfif i EQ k AND j NEQ k>
<!--- amicable pair --->
<cfset sum = sum + j>
</cfif>
</cfloop>

<cfoutput>#sum#</cfoutput>
```

So what’s the difference? Firstly, I was using a Struct to store each amicable pair. I did away with that, and just added directly to my total. I wouldn’t normally code like that; for these sort of things its good to have a variable that you can then interrogate later to see actually what numbers are we calling amicable. However, on the assumption that the code is now correct, doing away with it removes one level of complexity. I can then remove one StructNew function call, the two StructKeyExists function calls, one StructKeyArray function call, and one cfloop.

Secondly, instead of having one function to get all the factors, and another function to then add those together, I simplified this to just one function that both finds the factors and adds them together.

This function originally extended to half of x, e.g. if the number was 198, the largest factor of that is 99. However the function rewritten only extends to the square root of x, and adds both the factor and x / factor. e.g. for 220 we only go as far as 14, and add 1 (outwith our loop), 2 and 110 (220/2), 4 and 55 (220/4), 5 and 44 (220/5), 10 and 22 (220/10), 11 and 20 (220/11).

Then we sum those factors (sum1), then find the factors of sum1, sum them (sum2) and compare i and sum2. Assuming they match and sum1 and sum2 are different, we add sum1 to our total.

## November 10, 2008

### Project Euler: problem 49

Problem 49:

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

There are three aspects to this:

• Work out how to loop through the numbers
• Work out if the digits are the same in each case
• Work out if each number is prime

So, each number has to be 4 digits. The largest 4 digit number is 9999. If we add 3330 each time, the largest number can’t be any more than 9999 – 3330 – 3330. On re-reading the brief, it says “there is one other 4-digit increasing sequence“, and I had a nasty thought that it maybe wasn’t one that increased by 3330, but some other number. However that’s not the case thankfully.

If we know 1487 is the other number that this works for, we can exclude that. I made the assumption that the second number would be larger than 1487. However this could have been a wrong assumption, and my code should have started at 1001, and deliberately stepped over 1487. But my assumption turned out be correct, so the code worked as it was.

All primes apart from 2 are odd, so I started at the next odd number greater than 1487. Also setting the loop increment to +2, so we can exclude the even numbers.

To work out if the numbers are the same each time, I put two sets of numbers each into an array, sort the arrays, then compare them. If the numbers in the arrays differ, then the digits must be different.

I’m reusing my IsPrime() function from earlier problems.

```<cfset end = 9999 - (3330 * 2)>

<cfscript>
function sameDigits(x, y)
{
var i = 0;
var arrX = ArrayNew(1);
var arrY = ArrayNew(1);

for (i = 1; i LTE Len(x); i = i + 1)
{
ArrayAppend(arrX, Mid(x, i, 1));
}
for (i = 1; i LTE Len(y); i = i + 1)
{
ArrayAppend(arrY, Mid(y, i, 1));
}
ArraySort(arrX, "numeric");
ArraySort(arrY, "numeric");

for (i = 1; i LTE ArrayLen(arrX); i = i + 1)
{
if (arrX[i] NEQ arrY[i])
return false;
}

return true;
}

function isPrime(x)
{
var isPrime = true;
var i = 0;

if (x LT 2)
{
return false;
}

if ((NOT x MOD 2) AND (x GT 2))
{	// a multiple of 2, but not 2 itself
return false;
}

for (i = 3; i LTE SQR(x); i = i + 2)
{
if (NOT x MOD i)
{	// found a factor of x
return false;
}
}

return isPrime;
}
</cfscript>

<cfloop index="i" from="1489" to="#end#" step="2">
<cfset num2 = i + 3330>
<cfset num3 = num2 + 3330>

<cfif 	sameDigits(i, num2)
AND 	sameDigits(i, num3)
AND 	IsPrime(i)
AND 	IsPrime(num2)
AND 	IsPrime(num3)>
<cfoutput>#i##num2##num3#</cfoutput>
<cfbreak>
</cfif>
</cfloop>
```

## November 8, 2008

### Project Euler: problem 36

After struggling for several days with another Project Euler problem, I decided to give up and tackle something easier. This one took about five minutes to work out.

Problem 36:

The decimal number, 585 = 10010010012 (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

So I reused the IsPalindrome function I wrote for Problem 4. The only new part here is working out a number in base 2. Coldfusion conveniently has a FormatBaseN function, allowing you to convert a number from base 10 to any other base. The inverse of that is InputBaseN, converting a number from any base back to base 10.

```<cfset sum = 0>

<cfscript>
function isPalindrome(x)
{
if (x EQ Reverse(x))
return true;
else
return false;
}
</cfscript>

<cfloop index="i" from="1" to="999999">
<cfif isPalindrome(i) AND isPalindrome(FormatBaseN(i, 2))>
<cfoutput>#i# #FormatBaseN(i, 2)#<br></cfoutput>
<cfset sum = sum + i>
</cfif>
</cfloop>

<cfoutput><strong>#sum#</strong></cfoutput>
```

## November 4, 2008

### Project Euler: problem 45

After completing problem 42, which required checking if a number was a triangular number, this problem was a natural progression. This time we’re also wanting to check if our number is a hexagonal number and pentagonal number.

Problem 45:

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
Triangle Tn=n(n+1)/2 1, 3, 6, 10, 15, …
Pentagonal Pn=n(3n1)/2 1, 5, 12, 22, 35, …
Hexagonal Hn=n(2n1) 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.

So again, thanks to Wikipedia for the formulae, I just added a couple functions to test if any number is hexagonal and pentagonal.

```<cfscript>
function isTriangle(x)
{
var n = (SQR((8 * x) + 1) - 1) / 2;

if (n EQ Round(n))
// it's an integer
return true;
else
// it's not an integer, therefore not a triangle number
return false;
}

function isPentagonal(x)
{
var n = (SQR((24 * x) + 1) + 1) / 6;

if (n EQ Round(n) AND n GT 0)
// it's a natural number
return true;
else
// it's not a natural number, therefore not a pentagonal number
return false;
}

function isHexagonal(x)
{
var n = (SQR((8 * x) + 1) + 1) / 4;

if (n EQ Round(n))
// it's an integer
return true;
else
// it's not an integer, therefore not a triangle number
return false;
}

</cfscript>

<cfset i = 1>

<cfloop condition="1 GT 0">
<cfset i = i + add>
<cfif IsTriangle(i) AND isPentagonal(i) AND isHexagonal(i) AND i GT 40755>
<cfbreak>
</cfif>
</cfloop>

<cfoutput>#i#</cfoutput>
```

Initially I started out at i=40755, and incremented one at a time. However that seemed to be rather slow. So instead I decided to start at 1, so I could keep track of how much to increment each time; using the series of triangle numbers rather than either of the others, just because that was simplest.

## November 3, 2008

### Project Euler: problem 42

After completing problem 22, I spotted this one that looked quite similar.

Problem 42:

The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and ‘Save Link/Target As…’), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

So, reusing most of the code from problem 22, the only new bit of functionality we need to worry about is how to determine if a number is a triangular number. The Wikipedia gave me the formula needed. An alternative way would have been to just calculate a list or array of all the triangular numbers up to some limit, then check if each word’s value is in that list.

```<cffile	action="read"
file="#GetDirectoryFromPath(GetCurrentTemplatePath())#words.txt"
variable="wordsFile">

<cfset words = ArrayNew(1)>
<cfset total = 0>

<!--- transfer names into an array --->
<cfloop index="i" list="#wordsFile#">
<cfset ArrayAppend(words, ReplaceNoCase(i, '"', '', 'ALL'))>
</cfloop>

<cfscript>
function isTriangle(x)
{
var n = (SQR((8 * x) + 1) - 1) / 2;

if (n EQ Round(n))
// it's an integer
return true;
else
// it's not an integer, therefore not a triangle number
return false;
}
</cfscript>

<cfloop index="i" from="1" to="#ArrayLen(words)#">
<cfset sum = 0>

<cfloop index="j" from="1" to="#Len(words[i])#">
<cfset sum = sum + Asc(Mid(words[i], j, 1)) - 64>
</cfloop>

<cfif isTriangle(sum)>
<cfset total = total + 1>
</cfif>
</cfloop>

<cfoutput>#total#</cfoutput>
```

Again, I’m making the assumption that all letters are uppercase, so I can simply subtract 64 from each letter’s ASCII value to get it transformed into a 1-26 range.

## 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!

## October 31, 2008

### Project Euler: problem 17

Filed under: Coldfusion,Project Euler — duncan @ 7:00 am
Tags: , , , , ,

After completing the first eleven problems, I’ve started to cherry-pick the ones I think I can tackle. I jumped ahead a bit to problem 17.

Problem 17:

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of “and” when writing out numbers is in compliance with British usage.

So this is kind of a fun problem that I think is actually a useful thing to know as a web developer. You might not have a practical application where you need to convert digits to words, however there are similar applications. For instance you might want to output a date or time difference in words rather than numbers, e.g. ‘you last logged in four days / three weeks / two months / one year ago’. The principles are similar.

```<cfset numbers = ArrayNew(1)>
<cfset words = ArrayNew(1)>
<cfset sum = 0>

<cfset numbers[1] = "one">
<cfset numbers[2] = "two">
<cfset numbers[3] = "three">
<cfset numbers[4] = "four">
<cfset numbers[5] = "five">
<cfset numbers[6] = "six">
<cfset numbers[7] = "seven">
<cfset numbers[8] = "eight">
<cfset numbers[9] = "nine">
<cfset numbers[10] = "ten">
<cfset numbers[11] = "eleven">
<cfset numbers[12] = "twelve">
<cfset numbers[13] = "thirteen">
<cfset numbers[14] = "fourteen">
<cfset numbers[15] = "fifteen">
<cfset numbers[16] = "sixteen">
<cfset numbers[17] = "seventeen">
<cfset numbers[18] = "eighteen">
<cfset numbers[19] = "nineteen">
<cfset numbers[20] = "twenty">
<cfset numbers[30] = "thirty">
<cfset numbers[40] = "forty">
<cfset numbers[50] = "fifty">
<cfset numbers[60] = "sixty">
<cfset numbers[70] = "seventy">
<cfset numbers[80] = "eighty">
<cfset numbers[90] = "ninety">

<cfloop index="i" from="1" to="1000">
<cfset numberAsString = "">

<!--- how many thousands? --->
<cfset thousands = i \ 1000>
<cfset hundreds = i \ 100>	<!--- DIV 100 --->
<cfset tens = (i \ 10) MOD 10>	<!--- DIV 10 MOD 10 --->
<cfset units = i MOD 10>

<cfif thousands GT 0>
<cfset numberAsString = numberAsString & numbers[thousands] & " thousand">
</cfif>

<cfif hundreds GT 0 AND hundreds LT 10>
<cfset numberAsString = numberAsString & numbers[hundreds] & " hundred">

<cfif (tens GT 0 AND tens LT 10) OR units GT 0>
<cfset numberAsString = numberAsString & " and ">
</cfif>
</cfif>

<cfif tens EQ 1>
<cfset numberAsString = numberAsString & numbers[(tens*10) + units]>
</cfif>

<cfif tens GT 1 AND tens LT 10>
<cfset numberAsString = numberAsString & numbers[tens*10] & " ">
</cfif>

<cfif units GT 0 AND tens NEQ 1>
<cfset numberAsString = numberAsString & numbers[units]>
</cfif>

<cfoutput>#numberAsString#</cfoutput><br>

<!--- strip out the spaces --->
<cfset ArrayAppend(words, REReplace(numberAsString, "[[:space:]]", "", "ALL"))>
</cfloop>

<cfloop index="i" from="1" to="#ArrayLen(words)#">
<cfset sum = sum + Len(words[i])>
</cfloop>

<cfoutput><strong>#sum#</strong></cfoutput>
```

This code’s not as lean as it could be. However I hope it’s easy to understand, which is perhaps more important!

Firstly I create an array for the words we’ll need to use to build up our string. I set the array index equal to whatever that number is. This means our array has lots of empty elements; we’ll be fine so long as we don’t try and loop through the array from 1 to the end.

Then I loop up to 1000. At each iteration, do some DIV and MOD calculations on the loop counter. In Coldfusion, the DIV operation is represented by a \ instead of the normal / used for floating point division. Just to clarify for anyone who doesn’t know what I mean by DIV: divide a by b. MOD gives you just the remainder, DIV gives you the integer part before the remainder (aka the ‘quotient‘). So 12 DIV 10 = 1. Or in CFML:
<cfset x = 12 \ 10>

Then gradually build up the string based on what number we have for each of the thousands, hundreds, tens and units. We need to make a special exception for the numbers between eleven and nineteen, because we don’t write them as ‘ten one’, ‘ten two’ etc.

Then I strip out the spaces, store this in a separate array, loop through that array and add up the lengths. This last step could be done in a variety of simple ways. There’s no real advantage to me using the array, I could just have easily ditched that array and second loop, and just made the last line inside my main loop
<cfset sum = sum + Len(REReplace(numberAsString, “[[:space:]]”, “”, “ALL”))>

## October 30, 2008

### Project Euler: problem 13

Filed under: Coldfusion,Project Euler — duncan @ 7:00 am
Tags: , , , , ,

Problem 13:

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
… etc.
53503534226472524250874054075591789781264330331690

So this seems reasonably straightforward. Reusing our <cfsavecontent> technique from problem 8 and problem 11, we can just loop through the numbers, adding them up, right?

```<cfsavecontent variable="number">
37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
...
53503534226472524250874054075591789781264330331690
</cfsavecontent>

<cfset sum = 0>

<cfloop index="i" list="#number#" delimiters="#Chr(13)##Chr(10)#">
<cfset sum = sum + i>
</cfloop>

<cfoutput>#sum#</cfoutput>```

This code returns a number in scientific notation, because of the limitations of 32-bit integers. If you’re using CFMX (I’m doing this in CF 5), you could just cast to a Java long int to get your answer. I tried a variety of ways to present the total sum, then realised the answer was right there on the screen.

The answer is in the form
1.23456789012E+051
i.e. the equivalent of
1.23456789012 x 1051
i.e. the equivalent of
123456789012 followed by forty digits.
I’m only looking for the first ten digits, so I just manually removed the decimal and grabbed those digits. KISS!

## October 29, 2008

### Project Euler: problem 11

Filed under: Coldfusion,Project Euler — duncan @ 7:00 am
Tags: , , , , ,

This is one of those problems that at first glance looks really difficult, but when it comes down to it, wasn’t that hard.

Problem 11

In the 20 x 20 grid below, four numbers along a diagonal line have been marked in red.

```08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
```

The product of these numbers is 26 x 63 x 78 x 14 = 1788696.

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20 x 20 grid?

One thing it doesn’t mention in that spec is if the numbers have to be in a straight line, or if it means it could be up, left, diagonal, right all in the same set of four.  However, in the list of all the problems, it summarises it as "What is the greatest product of four numbers on the same straight line in the 20 by 20 grid?"

So basically this can be done with four sets of nested loops, one each for horizontal, vertical, and the two diagonals.

Going diagonally, we have to exclude some values in opposing corners. Laying it out like this helped me visualise what I need to do in the code:

Diagonal 1:

```08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48```

Diagonal 2:

```08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48```

This one was a bit like problem 8, with a large block of numbers which is ideal for plugging into <cfsavecontent>. Use a nested loop when constructing the array, as our block of numbers is delimited on the line by CRLF, and delimited between the numbers by spaces.

```<cfsavecontent variable="grid">
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
</cfsavecontent>

<cfset numbers = ArrayNew(2)>
<cfset m = 1>
<cfset max = 0>
<cfset product = 0>

<!--- store all this in a 2D array --->
<cfloop index="i" list="#grid#" delimiters="#Chr(13)##Chr(10)#">
<cfset n = 1>
<cfloop index="j" list="#i#" delimiters=" ">
<cfset numbers[m][n] = j>
<cfset n = n + 1>
</cfloop>
<cfset m = m + 1>
</cfloop>

<!--- across --->
<cfloop index="i" from="1" to="#ArrayLen(numbers)#">
<cfloop index="j" from="1" to="#(ArrayLen(numbers[i])-3)#">
<cfset product =numbers[i][j] 	*
numbers[i][j+1]	*
numbers[i][j+2]	*
numbers[i][j+3]>
<cfif product GT max>
<cfset max = product>
</cfif>
</cfloop>
</cfloop>

<!--- down --->
<cfloop index="i" from="1" to="#(ArrayLen(numbers)-3)#">
<cfloop index="j" from="1" to="#ArrayLen(numbers[i])#">
<cfset product =numbers[i][j] 	*
numbers[i+1][j]	*
numbers[i+2][j]	*
numbers[i+3][j]>
<cfif product GT max>
<cfset max = product>
</cfif>
</cfloop>
</cfloop>

<!--- diagonally 1, \\\\ --->
<cfloop index="i" from="1" to="#(ArrayLen(numbers)-3)#">
<cfloop index="j" from="1" to="#(ArrayLen(numbers[i])-3)#">
<cfset product =numbers[i][j]		*
numbers[i+1][j+1]	*
numbers[i+2][j+2]	*
numbers[i+3][j+3]>
<cfif product GT max>
<cfset max = product>
</cfif>
</cfloop>
</cfloop>

<!--- diagonally 2, //// --->
<cfloop index="i" from="4" to="#ArrayLen(numbers)#">
<cfloop index="j" from="1" to="#(ArrayLen(numbers[i])-3)#">
<cfset product =numbers[i][j]		*
numbers[i-1][j+1]	*
numbers[i-2][j+2]	*
numbers[i-3][j+3]>
<cfif product GT max>
<cfset max = product>
</cfif>
</cfloop>
</cfloop>

<cfoutput><strong>#max#</strong></cfoutput>
```

For each of the loops, we don’t want to go all the way to the end of the line. For instance on the horizontal one, we loop as far as the 3rd last, because we’re going to grab those last 3 values anyway.
The vertical loop just switches round the values for i and j from the horizontal loop.
The diagonal loops require manipulating both i and j values.

## October 28, 2008

### Project Euler: problem 10

This one had me stumped for a while. The code isn’t that difficult, but making something that can run efficiently on my old CF 5 server seemed a bit trickier. In the end I used something that took ages to run, and decided to refactor my code once I’d read some of the discussions you get access to after completing these problems.

Problem 10:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

The brute force way to do this would be to loop from 1-2000000, checking if each number is prime before adding it to your total. A slightly less brute method would be to do it in steps of 2, avoiding the even numbers (except 2). I tried to avoid doing that, using various methods I’d already been using in earlier ones, trying to apply the Sieve of Eratosthenes, stepping in sixes, etc but with no luck. So I went back to the brute force, which took many minutes. Then rewrote my code.

I initially hadn’t been too far away from getting the solution, just needed a bit of tidying up. Here’s the revised code:

```<cfset limit = 2000000>
<cfset numbers = ArrayNew(1)>

<!--- initialise our array --->
<cfset ArraySet(numbers, 2, limit, 1)>

<!--- switch off all the even numbers except 2 --->
<cfloop index="i" from="4" to="#ArrayLen(numbers)#" step="2">
<cfset numbers[i] = 0>
</cfloop>

<!--- we only need to loop up to the root of our limit --->
<cfloop index="i" from="3" to="#SQR(limit)#" step="2">
<cfif numbers[i]>
<cfloop index="j" from="#(i * i)#" to="#limit#" step="#(2 * i)#">
<cfset numbers[j] = 0>
</cfloop>
</cfif>
</cfloop>

<cfset sum = 0>

<cfloop index="i" from="2" to="#limit#">
<cfif numbers[i]>
<cfset sum = sum + i>
</cfif>
</cfloop>

<cfoutput>#sum#</cfoutput>
```

I’m still lacking a true understanding of how to generate prime numbers efficiently. The things that I didn’t get right in my first go round:

• only looping to the square root of our limit
• not needing to actually check if a number is prime
• the values for the from and step attributes in this line:
<cfloop index=”j” from=”#(i * i)#” to=”#limit#” step=”#(2 * i)#”>
I had them as from=”#(i * 2)#” and step=”#i#”

Interestingly, at one point I rewrote my code from normal CFML syntax to all be in CFScript, thinking that perhaps multiple <cfset> statements would run faster like this. That used to be the conventional wisdom in CF 5; multiple cfsets should be moved to a cfscript block; but no longer applies in CFMX. However I found it took almost twice as long to run.

Next Page »

Theme: Rubric. Blog at WordPress.com.