Duncan’s blog

January 27, 2009

Project Euler: problem 25

Filed under: Project Euler,Python — duncan @ 11:58 pm
Tags: , , ,

Problem 25:

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn-1 + Fn-2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144

The 12th term, F12, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

In Python, reusing most of the logic from way back in Problem 2:

```fibonacci = 1
old1 = 0
old2 = 1
limit = 1000

i = 1

while len(str(fibonacci)) < limit:
fibonacci = old1 + old2
old1 = old2
old2 = fibonacci
i = i + 1

print(i)
```

January 26, 2009

Project Euler: problem 20

Filed under: Project Euler,Python — duncan @ 12:00 am
Tags: , ,

Problem 20:

n! means n x (n − 1) x … x 3 x 2 x 1

Find the sum of the digits in the number 100!

Another one that had previously foxed me in CFML (on Coldfusion 5), but was simple in Python:

```limit = 100
total = 0
product = 1

for i in range(limit, 1, -1):
product = product * i

prodStr = repr(product)
length = len(prodStr)

for i in range(length):
total = total + int(prodStr[i])

print(total)
```

Similar code to problem 16. I work out 100!, then I turn the number into a string, work out the length of the string, loop through the string, adding up each digit.

This is only my second bit of Python ever, so I’d love some feedback from anyone with more experience of the language.

January 25, 2009

Project Euler: problem 16

Filed under: Project Euler,Python — duncan @ 8:10 pm
Tags: , ,

Problem 16:

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 21000?

This was a problem I’d tried doing in Coldfusion a while ago, and gave up. The problem is that 21000 is a 302-digit number. Coldfusion supports 32-bit integers, between -2,147,483,648 and 2,147,483,647. Even a 64-bit integer wouldn’t be long enough.

I briefly tried something in Javascript, then turned to Python, which I’ve never used before. So the following is my first ever Python program! Probably a few lines longer than it needs to be; I later saw solutions expressed in one line.

```x = 0
y = repr(pow(2,1000))
length = len(y)

for i in range(length)
x = x + int(y[i])

print(x)
```

This was exactly what I’d tried and failed to do with CFML. After installing Python 3.0, skimming through the tutorial and reading a few other bits in the documentation, I was able to put the above together and get the solution pretty quickly.

Although Python is dynamically-typed, you still have to cast a numeric value to a string and a string to an int, using repr() and int() respectively. In Coldfusion there’s no need to do that; I can create a string, then perform arithmetic directly on it (if it’s a numeric value in the string), then check the length of the string, append another string, find the square root, etc. all without having had to cast or convert it at any stage.

Apart from that, I like what I see of Python so far. I’m a stickler for good indentation normally, so I don’t see the requirement to indent as being a problem. I’ll maybe see if I can use Python to solve some of the other Project Euler problems that I’ve not been able to finish due to Coldfusion’s limitations with long integers.

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 9, 2008

Project Euler: problem 79

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

Problem 79:

A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may asked for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.

The text file, keylog.txt, contains fifty successful login attempts.

Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length.

At first I started coding up a solution. It looked a bit complicated, so I decided to try it by hand with pen and paper. Doing it that way took about two minutes, much quicker than trying to code a solution! However if you were going to do this for say a hundred different users, you’d be better trying to work it out in code.

The theory would be to have an array, and insert each new digit encountered in the logins to the array. For each digit, check if it’s already in the array. If it is, compare its position against the next digit in the current block of three. If they’re not in the correct order in the array, shuffle them around until they are.

Doing it by hand, just draw ten columns on your page. Start putting the numbers into the array, manually working out where they should be each time. Doing it that way isn’t very hard at all…

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 5, 2008

Project Euler: problem 19

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

This was a problem I’d initially passed over as I thought it looked a bit tricky, then when I came back to it I realised it wasn’t that hard at all.

Problem 19:

You are given the following information, but you may prefer to do some research for yourself.

• 1 Jan 1900 was a Monday.
• Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine.
• A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

The reason it didn’t turn out that hard was because Coldfusion has many useful date functions built in. In fact, I started writing my own IsLeapYear() function before realising that was one that already existed.

```<cfset sum = 0>

<cfset start = CreateDate(1901, 1, 1)>
<cfset end = CreateDate(2000, 12, 31)>

<cfloop index="i" from="#start#" to="#end#">
<cfif DayOfWeek(i) EQ 1 AND FirstDayOfMonth(i) EQ DayOfYear(i)>
<cfset sum = sum + 1>
</cfif>
</cfloop>

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

Looping through dates like this isn’t something I do often. In this loop, i is an ordinal value, e.g. 365, 366, 367 etc, which corresponds to dates from 1st January 1900 onwards it seems.

DayOfWeek returns a value from 1 to 7, where 1 equals Sunday. If you ever do any calendar work, this is a useful function. Its only problem is if you’re trying to do a calendar where Monday is the first day of the week instead of Sunday; it then becomes a bit tricky. I find that a bit of a bug-bear, because of course Monday is the first day of the week, as any fule knoe (and there’s an ISO standard that says the same). Ideally DayOfWeek could take an optional attribute to define whether Monday or Sunday is the desired first day. Or even have an LSDayOfWeek.

FirstDayOfMonth is one of those functions I’ve maybe never used, or only very rarely. If you give it a date, it’ll tell you what day of the year (1-365/366) was the first day of that month. So by comparing FirstDayOfMonth(i) to DayOfYear(i), if they’re the same then that day was indeed the first of a month.

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.

« Previous PageNext Page »

Theme: Rubric. Blog at WordPress.com.