Project Euler problem 30

Problem 30:

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

As 1 = 1⁴ is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Another problem where I’d worked out the logic in Coldfusion, but had to rewrite it in Python to get the solution.

We’re going to loop through numbers testing them out. We know we can skip 1. But how far do we need to loop up to? Let’s look at 4 digit numbers first; the lowest 4-digit number is 1000.  1^5 + 0^5 + 0^5 + 0^5 =1.  The highest 4-digit number is 9999.  9^5 + 9^5 + 9^5 + 9^5 = 236196.  Somewhere in between there is scope for the 5th powers of a 4 digit number to add up to a 4 digit number.

What about 5 digit numbers?  The highest sum of the 5th powers is 295,245. So all 5 digit numbers fall within that range.

And with 6 digit numbers?  The highest sum of the 5th powers is 354294.  So we can cover 6 digit numbers up to that far and no further.

With 7 digit numbers, the highest value is 413343, i.e. the highest sum of the 5th powers of a 7 digit number only adds up to a 6 digit number.  So we only need to loop from 2 to 354294.

powers = []
grandtotal = 0

for i in range(2,354294):
        total = 0
        for j in str(i):
                total += int(j) ** 5

        if total == i:
                powers.append(i)

for i in powers:
        grandtotal += i

print("powers:", powers)
print("total:", grandtotal)

So we loop through our numbers. On each number, loop through the digits, adding up the values of each digit to the power of 5. If the total of those values = our number, then store that number in a list.
At the end of the loop, add up all the values in the list to give the solution to the problem.

Google: all sites may harm your computer

Sometimes you may have noticed “This site may harm your computer” appearing under individual search results on Google. Today I noticed it appearing under every search result, no matter what I searched for.

Some kind of hiccup down at the Google server farm? There was a generic error message that came up later, and now it all seems to be back to normal.

It’s reassuring to see that even Google can screw things up.

Update: as reported in The Register and LifeHacker

Google later put out the official explanation of what happened: human error. They’d entered / into their list of bad sites, which equalled all websites. Oops!

MSPs’ expense claims: Data Protection Registrar

After looking at how MSPs were claiming expenses for their websites, I decided to see if there were any other interesting facts to be gleamed from the MSP Allowances search form.

One of the categories they can claim for is Data Protection Registration, and reassuringly, 94 claims were made for this in financial year 2007-2008. I say claims, because only 93 MSPs claimed but Bill Wilson claimed twice, in February 2007 and November 2007. I’m not entirely sure how a claim for February 2007 can appear in results for a financial year that started in April 2007.

However there are 129 MSPs, which means 36 didn’t claim for this expense. When you register as a Data Controller, you have to pay £35 annually. So those 36 MSPs haven’t registered, or have incorrectly claimed the £35 expense in a different category, or have paid the fee but just not claimed for it.

So, can we find out which MSPs haven’t registered with the Information Commissioner?

Conveniently, the ICO has a search form for the Data Protection Public Register. Typing in MSP will give you almost 80 names straight away. To find the rest it’s a case of plugging in the names. Some have variations on how they’ve spelled their name, but eventually I got down to a list of eight names I couldn’t find:

Name	Party	Constituency
Andy Kerr	Labour Party	East Kilbride
Bruce Crawford	Scottish National Party	Stirling
Elizabeth Smith	Conservative	Mid Scotland and Fife
Jim Mather	Scottish National Party	Argyll and Bute
Joe Fitzpatrick	Scottish National Party	Dundee West
Margaret Curran	Labour Party	Glasgow Baillieston
Nicola Sturgeon	Scottish National Party	Glasgow Govan
Nigel Don	Scottish National Party	North East Scotland

It might be that these MSPs have registered under a different name that I’ve not searched for, or there’s been a typo when the details have been entered into the system.

Let’s cross-check those eight names against the list of names who claimed expenses, and see which of those eight have claimed:

• Andy Kerr, January 2008
• Bruce Crawford, November 2007
• Elizabeth Smith, January 2008
• Joe Fitzpatrick, October 2007
• Margaret Curran, January 2008
• Nicola Sturgeon, June 2007
• Nigel Don, October 2007

So they all claimed except for Jim Mather. I’m going to give them the benefit of the doubt, and assume they are correctly registered with the ICO, and for some reason I’m just not having any luck finding them on the Data Protection Public Register.

MSPs, MPs, MEPs and Councillors are basically obliged to register as Data Controllers. Some information I’ve found on the ICO site confirms this:

Organisations or individuals that process personal information covered by the Act may need to notify the Commissioner about their processing. A description of the processing activities is placed on a public register of notifications. These organisations or individuals must also comply with eight data protection principles which together form a framework for the proper handling of personal information. Individuals whose personal information is processed have rights under the Act, for example, to a copy of the information that is held about them.
…
When elected members represent residents of their ward, they are likely to have to notify in their own right, for example, if they use personal information to timetable surgery appointments or take forward complaints made by local residents.
…
The Data Protection Act contains a number of criminal offences including:
When someone is required to notify and does not do so. For example, a councillor who holds computerised records of constituents’ details for casework purposes, would commit an offence if they had not notified this use of personal information.

Someone should be checking these eight MSPs to make sure they have been correctly registered with the ICO. If you are a constituent of any of these MSPs, you might want to use the excellent WriteToThem.com to ask your MSP what name they have registered with the Information Commissioner.

Glenrothes wins award for most dismal town in Scotland

Glenrothes won the Carbuncles award! In the other categories, Donald Trump’s controversial golf course won worst planning decision, and the conversion of the Plaza Ballroom in Glasgow into flats won worst new building.

Fife Council issued a press release criticising the awards. Council leader Peter Grant said “Already I’m being contacted by some of these volunteers who feel they’ve been kicked in the teeth as part of a cheap publicity stunt to boost sales of a magazine that neither they nor possibly anybody in Glenrothes has ever heard of”. That sort of sounds to me like a backwards way of saying nobody in Glenrothes is interested in architecture, which I guess is part of the problem that won it the award in the first place.

BBC video footage
BBC News article
BBC blogs
The Telegraph
Architecture Scotland press release

Disclaimer: I work for Fife Council, but my views do not in any way represent the council.

Project Euler: problem 48

Problem 48:

The series, 1¹ + 2² + 3³ + … + 10¹⁰ = 10405071317.

Find the last ten digits of the series, 1¹ + 2² + 3³ + … + 1000¹⁰⁰⁰.

Trying to do this one in CFML, on a Coldfusion 5 server, I get #INF, i.e. the CF server decides the number is too close to infinity and gives up! 1000^1000 is a number with 3000 zeroes in it, which is a pretty big number by all accounts. Python spits it out within a second without any problem. I’m really glad I decided to look at Python for these Project Euler problems; there are several where I could only go so far in CFML, knowing it wouldn’t work with the large numbers, but I think I’ll be able to complete in Python.

limit = 1000
sum = 0

for i in range(1, limit):
        sum = sum + pow(i,i)

sumStr = str(sum)

length = len(sumStr)

lastTen = ''

for i in range(length-10, length):
        lastTen += sumStr[i]

print(lastTen)

I don’t think this Python code is particularly good. I’m still struggling a bit to get my head around the range() function, and just how you do the basic things with strings. In CFML, I’d simply have said Right(sum, 10) to get the 10 right-most digits. I expect Python has similar, but I couldn’t find it after a quick look, so used the Range to loop 10 times towards the end of the sum, appending to a string.

Project Euler: problem 25

Problem 25:

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n-1 + F_n-2, where F₁ = 1 and F₂ = 1.

Hence the first 12 terms will be:

F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144

The 12th term, F₁₂, 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)

Unfit for the BBC?

This is the Disasters Emergency Committee video appeal the BBC’s Director General, Mark Thompson, is unwilling to air because it would apparently compromise the BBC’s impartiality.

An article in today’s Guardian suggests part of Mark Thompson’s reasoning might be connected to the Balen report into its Middle East coverage, which is as yet unpublished, despite attempts to get it released under Freedom Of Information.

Update: today’s Guardian has further details that shed more light on this:

Under guidelines agreed between the DEC and broadcasters, three criteria warrant a nationwide appeal:

• substantial, urgent need in a humanitarian crisis;
• evidence that aid agencies can guarantee effective assistance on the ground;
• and sufficient “public awareness, and sympathy for” the humanitarian crisis.

All of which are currently met by the crisis in Gaza. But the BBC say: “Preserving our impartiality is the BBC’s main criterion when deciding whether to broadcast an appeal”. The DEC have been broadcasting similar appeals since the 1960s, and only this one and their previous appeal for the Israel-Lebanon conflict in 2006 have been rejected by the BBC for “impartiality” reasons. (Some have been rejected for failing to meet all of the three criteria above).

Previous DEC appeals the BBC broadcast include:

• 1999 Kosovo war
• 1990 Gulf conflict
• 1982, for victims of Israel’s invasion of Lebanon
• 1968, for victims of the Vietnam war
• 1967, for Palestinian and Syrian refugees displaced by the Six Day War

And many others that might not be considered “impartial“.

It seems Mark Thompson is now making up what the guidelines are when deciding to show the DEC’s appeals. Incidentally, Thompson has held meetings with Ariel Sharon, and has a Jewish wife, but I’m sure neither of those would be affecting his decision-making capabilities on this matter.

Glenrothes up for award

Glenrothes in Fife has been shortlisted for the annual Carbuncle Awards, “the prize that identifies Scotland’s most dismal town.”

The judges’ statement says:

Glenrothes is a classic Scottish New Town. However, the judges felt that unlike New Towns such as East Kilbride and even Cumbernauld, it has failed to move with the times. It is dominated by the vast Kingdom Centre which also serves as the town centre. From the outside it is an ugly and depressing complex which inspires little civic pride. Inside it feels like an 80s timewarp. Said Gordon Young, “The real failing with this town centre is the lack of civic space. The whole thing is internalised. It is really just a big mall. But with a little investment it could be so much more. “However, the shops are busy. But the judges felt this was more down to a lack of competition in the region which explains a sense that the Kingdom complex perhaps does not need to try too hard in terms of attracting local trade. “One almost gets the feeling that perhaps Historic Scotland should give this place a listing, as an example of how poor shopping centres used to be.”

That’s pretty accurate. Basically Glenrothes is a series of suburbs, most of which have a small shopping precinct. The only town centre is really the Kingdom Centre shopping mall, which is a large indoor shopping centre, mostly surrounded by car parks.

On the other hand, Glenrothes has a lot of public sculptures, a reasonable amount of green space, and seems well catered for by cycle paths and footpaths, although the transport system is dominated by roundabouts.

The other nominees for the Plook on the Plinth Award are Motherwell and New Cumnock.

There is also the Pock Mark Award for worst planning decision and the Zit Building Award for the most disappointing building.

Vote online here or see more Glenrothes photos here.

Project Euler: problem 20

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.

Project Euler: problem 16

Problem 16:

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

What is the sum of the digits of the number 2¹⁰⁰⁰?

This was a problem I’d tried doing in Coldfusion a while ago, and gave up. The problem is that 2¹⁰⁰⁰ 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.