The Hidden Blade Assassin's Creed in Depth

i=1
s=0
while i<1000:
	s+=i*(i%3==0 or i%5==0)
	i+=1

print s

This returns the answer 233168 in a time of 0.000478 seconds.
First, I start by making a counter named i that will go up to 1000. Then I declare something to keep track of the sum. Then I make a loop. The computer will keep doing the indented instructions as long as i is smaller than 1000.

What happens in the next rule is a bit complicated. Between the brackets I've put a conditional statement, a sort of 'yes or no'-question. If the answer is no, it will return a 0. If the answer is yes, it will return a 1. The question is as follows: is the remainder when I divide i by 3 zero, or is the remainer when I divide i by 5 zero? The remainer of a division can be found with the modulo operator, %. This works because the remainder will be zero if the division plays out well. If this conditional statement returns 1, i gets multiplied by 1 and then added to s (s+=i*1) if it returns 0, i gets multiplied by 0 and then added to s, but because i*0 will be 0 for every i, s will stay the same.
In the next rule, I add one to i.

The program keeps repeating the instructions from the last paragraph until i is 1000. Then it goes on to 'print s', which just means that s is displayed on the screen. Then the program is finished, since there are no more instructions.

from math import cos,pi,sqrt
def fib(n):
	return ((0.5*(1+sqrt(5)))**n-(2/(1+sqrt(5)))**n*cos(pi*n))/sqrt(5)

i=1
f=fib(i)
s=0
limit=4000000

while ft: t=n
		j+=1
	i+=1
print t

This returns the answer 906609 in 1.815566 seconds.
First I define a flipping function for flipping around an integer. I can do this by turning the number into text, but this takes time. Instead, I make a new number f (which is zero) and then start a loop. First, I multiply the number by ten to free up space and add the last number of n (the remainder when you divide n by 10) to that. I then divide n by 10 to eliminate the last number. This works because in Python, a divison a/b will result in int(a/b). So if you divide 3 by 2 (3/2=1.5), the result will instead be 1. So if I divide a single number (1,2,3,4,5,6,7,8,9) by 10, the result will be 0, which is the same as 'not true' in a conditional statement. This means the loop will end and the reversed number f (from 'flip').
To illustrate this, let's try it with 12345. First, f is made. Then, 0*10=0. n%10 is the last number in n, so that results in 5. Hence, f=5. Dividing 12345 by 10 in python will leave us with 1234. Not equal to 0, so we continue. We multiply f by 10, leaving us with 50. Then we add 4. This gives 54. Going on, we get n as 12 and f as 543, then n as 1 and f as 5432, and finally n as 0 and f as 54321. The function then returns f.
To check if a number is palindromic is easy. You just check whether the reversed number is the same as the starting number.

We are now ready to start the program. I just check every single combination of two three digit numbers possible. I start with another counter and the variable t for the largest palindrome. In the loop, I declare another counter ( to start at the first three-digit number we know: 100. This will run until 999, which is still less than 1000. I then call the product of i and j n. If it's a palindrome and larger than the top palindrome, it becomes the new top palindrome. I increase j by one and create a new number n. After j has been all three digit numbers, I increase i by one and check all combinations again.

My technique left me with the answer 232792560 in about 5 minutes (I used a calculator for the final step).
You may think that the easy answer is 20*19*18*...*3*2*1, but that is not the case. 2520 is not the same as 1*2*3*4*5*6*7*8*9*10, which is 362880.
You remember factors and prime factors? Well, this is a problem where they really come in handy. It turns out that divisors of a number have the same prime factors as that number. To clarify, look at 20. It has prime factors 2, 2, and 5. The divisors of twenty are 2, 4, 5 and 10 (20 and 1 are boring and don't count). 2 is a prime factor of 20. 4 equals 2*2. 5 is a prime factor of twenty. 10=2*5. If we take a look at 2520, we see: 2520=2*2*2*3*3*5*7. Now, the next step is the good part. 2=2. 3=3. 4=2*2. 5=5. 6=2*3. 7=7. 8=2*2*2. 9=3*3. 10=2*5. Every single number we wanted to be a divisor is contained within these prime factors. The trick then not becomes to find a number that is divisible by 1 through 20, but to find the minimal amount of prime factors that can express all those numbers.
So I went on and listed all the prime factors from 2 to 20.

2:  2
3:  3
4: 2*2
5:  5
6:  2*3
7:  7
8:  2*2*2
9:  3*3
10: 2*5
11: 11
12: 2*2*3
13: 13
14: 2*7
15: 3*5
16: 2*2*2*2
17: 17
18: 2*3*3
19: 19
20: 2*2*5

From the bottom out, I then circled 'new' prime factors and crossed out their duplicates. So starting from twenty, I circled the first 2, then crossed out one 2 in all the other factor lists. I then moved on to a second 2, and I crossed out all second 2's. Then 5, crossing out all the 5's in the other lists. Then 19, which didn't appear anywhere else. The 2 from 18 was already crossed out, so I moved onto the 3's. And so forth. The final list of prime factors I got was (in order of discovery): 2, 2, 5, 19, 3, 3, 17, 2, 2, 7, 13, 11. Since these were the prime factors of the number we were looking for, we just multiply them and obtain the answer. One of my favourite problems so far.

This method left me with the answer 25164150 in less than a minute.
We know that the sum of all numbers up to a number n equals n(n+1)/2. To square this means (n(n+1)/2)^2 = n^2(n+1)^2/4. The sum of all squares up to n, there's is a formula as well: n(n+1)(2n+1)/6 (I derived this myself a few months ago, but it can be found on the internet). The difference then becomes n^2(n+1)^2/4 - n(n+1)(2n+1)/6. Simply plugging in 100 for n will reveal the answer.

from math import sqrt
def isprime(n):
	if n==1: return False
	if n<4: return True
	if n%2==0: return False
	if n<9: return True
	if n%3==0: return False
	r=int(sqrt(n))
	f=5
	while f<=r:
		if n%f==0: return False
		if n%(f+2)==0: return False
		f+=6
	return True

c=2
i=3
while c<10001:
	i+=2
	c+=isprime(i)

print c

This returns the answer 104743 in 0.184284 seconds.
I start by defining a prime checking function. 1 isn't a prime, but 2 and 3 are. I then pick out all number divisible by two (half of the numbers!) and that means all numbers less than 9 left are primes as well. I finally pick out all numbers divisible by three as well. Then I can start the algorithm.
If a number is not prime, it is divisible by a prime. All primes (aside from 3) can be written in the from 6k+1 or 6k-1. Instead of checking every number up to the candidate, I check only possible primes of the form 6k+1 or 6k-1. I don't know exactly how much faster it goes, but it's a lot. I then start counting primes using the same loop thing I've been doing all along. I've got 2 and 3 covered and use an increment of 2 to avoid all the redundant even numbers.

num="731671765..."
t=0
i=0
while i<996:
	a=ord(num[i])-48
	for j in range(1,5):
		a*=ord(num[i+j])-48
	if a>t:t=a
	i+=1
print t

This code returns the answer 40824 in 0.002588 seconds.
I started by converting the number into a single line of text, using TextWrangler (like NotePad++ for Mac). I then built a bruteforce checker, since there are only 996 combinations to try. As far as indices go (Python has the capability to treat a string as a list of characters), we start at 0, so we only have to check indices 0 up to 995. I use the ord() function to turn my characters into numbers. It basically gives the computer index for a character. In Python, I also could've use the int() function, but ord() is faster (with int(), it takes 0.007192, which is 2.7 times as long!). The only caveat is that ord("0") will leave 48, ord("1") 49 and so on, so I subtract 48. The rest is just generic checking whether the combination is greater than the top combination.

My technique yielded the answer 31875000 in about 5 minutes (I made some mistakes in calculating).
Our friend Euclid comes to our help here (Greek mathematician, way before our time). He proved that all pythagorean triplets are of the form a=m^2-n^2, b=2mn and c=m^2+n^2, where m and n are natural numbers (positive whole numbers). Using this, we can start to solve the equation 1000=a+b+c
1000=a+b+c
Substituting for a, b and c:
1000=m^2-n^2+2mn+m^2+n^2
n^2-n^2=0, so that cancels out. m^2+m^2 = 2m^2:
1000=2m^2+2mn
Divide by 2:
500=m^2+mn
Extracting m:
500=m(m+n)

Now we have a product of two numbers which had to equal 500. Luckily, both numbers have to be natural, since two natural numbers added to eachother produce a new natural number. Cue (with the help of prime factorization) a divisors table. I always do these things in pairs, so that the product is immediately clear.

2  - 250
4  - 125
10 - 50
20 - 25

Now, for the problem, we need to find two factors such that m smaller is than m+n (n isn't negative), so I put m and n above the table. I then derived n.

m  - m+n - n
2  - 250 - 248
4  - 125 - 121
10 - 50  - 40
20 - 25  - 5

Because a, b and c are positive, m^2-n^2 has to be positive, so m has to be larger than n. The only pair that satisfies this condition is m=20 and n=5.
The rest is filling in. We turn up with the triple a=375, b=200 and c=425. Punching those numbers into a calculator gave me the answer.

i=2
s=0
while i<2000000:
	s+=isprime(i)*i
	i+=1
print s

This returns the answer 142913828922 in 10.336727 seconds. The isprime function I used is exactly the same as seen in Problem 7. It's just number crunching, really. I chose not to use a sieve because Python implementations for over 10000 just don't seem to be as fast. Might be me, though. I'll give it another shot later on. There's bound to be more prime-problems.

In about 3 minutes, my method returned the answer 70600674.
I just looked for all numbers starting with a nine, then looked if they were on the same line. It turns out there is a great line that contains the numbers 87, 97, 94 and 89. Punch into a calculator and done.

def triangle(n):
	return n*(n+1)/2

from math import sqrt
def countdivisors(n):
	i=2
	limit=int(sqrt(n))
	c=2+(n%limit==0)
	while i < limit:
		c+=2*(n%i==0)
		i+=1
	return c

i=1
d=0
while d<501:
	t=triangle(i)
	d=countdivisors(t)
	i+=1

print t

This code returns the answer 76576500 in 11.472437 seconds.
Since we know all triangle numbers are the sum of natural numbers, we can use the trick Gauss developed. The sum of all numbers up and including n is: n(n+1)/2. I use this to return the n'th triangle number. For the second function, I use a simple algorithm with some optimizations to find the number of divisors. Since 1 and the number itself are counted (as seen in the problem description), I put the counter at 2. I also directly check if the square root happens to be a divisor, so the number is square. If I'd done this inside of the loop, I'd have one divisor too much, so I don't check the limit in the loop. Since every divisor smaller than the square root has a counterpart greater than the square root, I can spare a lot of time.
The rest is brute force looping. Over 500 is the same as 501 or higher.

nums=[3710728...
print str(sum(nums))[0:10]

This code returns the answer 5537376230 in 3.9e-05 seconds. I'm not joking, that's what it said. That's 39 microseconds.
First I used TextWrangler to format the numbers into a list. After that, I use Python's built-in function 'sum' to get the total of all numbers in the list, convert it to a string and use Pythons clever string manipulation tools to display the first ten numbers.

def next(n):
	if n%2!=0: return (3*n+1)/2
	return n/2

i=17
t=12
m=7
while i<1000000:
	n=i
	c=0
	while n!=1:
		n=next(n)
		c+=1
	if c>=t:
		t=c
		m=i
	i+=1

print m

This code returns the answer 837799 in 46.908311 seconds. (My slowest yet.)
First I define a function that returns the next number in the list, or the number after that (if it's odd). I'll explain this in a minute. I define a counter, which starts with 17. I had figured out every number less than that in an attempt to make the program go faster. It turns out, the maximum chain length for a number under 17 is 12, when starting with 7. Then inside of the loop, I create a destruction variable (as I call them). This will be the variable that will be destructed in the process of checking (ie. it will change, keeping the index intact). Then I just loop over the sequence, keeping track of how long the chain is. If the chain is longer than the top chain, that chain becomes the top (duh ).
I mentioned the next function taking two steps. I had a lot of trouble getting the program to run under a minute, so I researched the Collatz problem a bit, which pointed me to a different sequence (3n+1)/2 instead of 3n+1. I thought about this and figured out that if you apply this to every number in the same fashion, the longest chain will still stay the longest. That allowed me to push the program's running time under a minute.

from math import factorial

def nCr(n,r):
	return factorial(n)/(factorial(r)*factorial(n-r))

print nCr(40,20)

This code returns the answer 137846528820 in 50 microseconds.
The routes from the one corner to the opposite corner without backtracking in a grid correspond to the number of movements in one direction out of total number of movements (both vertical and horizontal). It's a fundamental part of combinatorics. Look it up over at Khan Academy if you want to know more about it.
So, the function giving the answer to the problem isn't available in the standard Python libraries (I haven't got scipy or something like that installed), so I made my own using the factorial function that was in the library.

print sum(map(lambda x: ord(x)-48,str(2**1000)))

This returns the answer 1366 in 98 microseconds.
I set out to use the map function, which is basically a loop in one-line. It's also much faster than conventional Python loops, since it's hardcoded into Python, using C. I assume it's heavily optimized as well. What it does, is take the iterable (list-like object) and loop over that, applying the function before the iterable (I used a nameless function, which we call 'lambda functions') to it. The function in this case is converting a number as a character to an actual number. I use the ord() function, as seen in Problem 8. Using the map function, every item in the list is thus changed into a normal number. I then use the fast (because hardcoded) sum() function and am done.
I really like the map() function, as well as it's brothers reduce() and filter(). I used the last one to make a oneline-primesieve. It wasn't very fast, though.

My method revealed the answer 21124 in about 5 minutes.
I started by counting the first nine numbers (1-9) and wrote that number (36) down. I then went on for all numbers 1-99. Every tenth (like twenty, thirty, etc.) is repeated ten times (first the number itself, then with one, two, three, etc. added), so I summed those and multiplied those by ten. [10*6+10*6+...=10(6+6)] Added the repetition of one, two, three... 9 times (twenty to ninety, as well as the first time under ten) and the numbers 10-19. That gave me 854 numbers under 100. This would be repeated ten times (0 hundred, 1 hundred, 2 hundred, etc.), so that gave me 854*10=8540. I then had to count the x hundred and's. For every hundred numbers, the word 'hundred' is repeated 100 times, so 100*9=900. Then the numbers 1-9 (in front of hunderd), each repeated 100 times, so 100*36=3600. The number of 'and''s is smaller, 99 times (no and on the hundred itself), so 99*3=297. Adding those numbers gave me a grand total of 8540+900+3600+297=21113. Adding to this the 11 characters that 'one thousand' counts leaves us with 21124.

def summation(triangle,i):
	m=len(triangle[i])
	j=0
	while j=0:
	triangle=summation(triangle,i)
	i-=1

print triangle[0][0]

This code returns the answer 1074 in 0.000102 seconds.
I first modified the triangle into a matrix using TextWrangler, then wrote the program.
The idea is simple. You check from the bottom up (I'd figured as much, but didn't know how to work it out). Starting at the second row from below, you look which number below it is the greatest. This is obviously the number you would pick, should you reach that particular number above, to get the greatest total sum. Then you add those numbers and put them instead of the above number. You apply this to every number in the row. This means that you've got the sum of the optimized paths from that row to the row below in one go. Now we move up one row and do the same. This leaves us with the optimized paths for that row as well. Continuing upwards, we end up with the most optimal path on the top of the triangle. I then print this number.
Here's the process illustrated.
Say, we start with the leftmost part of the triangle:

      70
    91  71 
  63  66  4
4   62  98  27

Applying the algorithm to the number 63, we choose 62 and calculate the sum, so 63+62=125. For the number 66, this is 98, so 98+66=154. For the number 4, this is 98 again, so 98+4=102. The triangle then becomes:

     70
   91   71
125  154  102

Applying the algorithm to the number 91, this leaves 91+154=255. For 71, 71+154=225. The triangle then becomes:

   70
255  225

Going on, we add 70 to 255 which leaves us with 325, the largest number in this particular triangle. Check it if you want to. ;)

from datetime import date
sundays=0
y=1901
while y<=2000:
	m=1
	while m<=12:
		sundays+=(date(y,m,1).weekday()==6)
		m+=1
	y+=1
	
print sundays

The Python object date has four things I can use: a year counter, a month counter, a day of the month counter and a weekday counter. The function date.weekday() returns the number corresponding to the weekday. For sunday, this is 6 (monday is 0, you see). I just loop over the century's first days of the month and check if they're sundays. No need to bother with month length, year length and weekday switching.

from math import factorial
print sum(map(lambda x: ord(x)-48,str(factorial(100))))

This returns the answer 648 in 96 microseconds.
I used the same process as in problem 16, except for the factorial which I just got from the library.

from math import sqrt
def divisors(n):
	d=[1]
	i=2
	limit=int(sqrt(n))
	while i < limit:
		if n%i==0:d.extend([i,n/i])
		i+=1
	if n*1.0/limit==limit: d.append(limit)
	return d

def isamicable(a):
	b=sum(divisors(a))
	if a==sum(divisors(b)) and a!=b: return True
	return False

a=10
s=0
while a<10000:
	s+=a*isamicable(a)
	a+=1

Since we're evaluating the sum of all amicable numbers, I just have to check if a number is part of an amicable pair or not. If so, it's added to the sum. As for the other number in the pair, that will be checked later on.
I had to optimize the divisor function, it was way to clunky. It now includes only 1 as divisor, but not the number itself. For looping, it uses 'pair divisors' to speed up the progress. In the rule before last, I add the square divisor (if there is one), without counterpart. The rest is a piece of cake.

names=["MARY"...
names.sort(key=str.lower)

def worth(name):
	return sum(map(lambda x: ord(x)-64,name))

t0=clock()
s=0
for i in range(0,len(names)):
	s+=(i+1)*worth(names[i])
print s

This code returns the answer 871198282 in 0.016576 seconds.
First I sorted the names in alphabetical order using Python's built in function sort(). Then I defined a function worth(). It's the same as used in problem 16 and problem 20, only now I have to convert the characters to values. Easy peasy with the ord() function, which for "A" will yield 65. After this conversion, the function returns the sum of the list.
For the rest, looping over the names using an index. The value a name gets is position-dependent, so I used the index to find the multiplier.

def divisors(n):
	d=[1]
	i=2
	limit=int(sqrt(n))
	while i < limit:
		if n%i==0:d.extend([i,n/i])
		i+=1
	if n*1.0/limit==limit: d.append(limit)
	return d

def isabundant(n):
	return sum(divisors(n))>n
ab=[]
for i in xrange(12,20162):
	if isabundant(i):ab.append(i)

sums=[]
for i in ab:
	for j in ab[ab.index(i):]:
		n=i+j
		if n<20161:sums.append(n)
sums=set(sums)

nums=range(1,20162)
for i in sums:
	nums.remove(i)

print sum(nums)

This code returns the answer 4291075 in 5.535247 seconds.
I use the divisors function also seen in Problem 21 and then define a checker for abundant numbers. A little bit of Googling revealed that all numbers above 20161 could be written as the sum of two abundant numbers, so I set the limit to that.
I started out by putting all abundant numbers in a list. I use the xrange object instead of the range object (the latter returns a list, the former a generator) because it takes less memory for great ranges. After checking every number, I move on to putting all of their sums in a list. I use a slice to prevent duplicate adding (as in 1+2 and 2+1).
The rule after that is what makes the code go fast. A set in Python is a collection of items, without indices, in which no two items are the same. In converting a list to a set, Python will remove all duplicates.
Finally, we just loop over all the items in the sums set, removing them from the list of normal numbers and output the sum of what's left.

My method revealed the answer 2783915460 in about 5 minutes.
The first step is to recognize that there are 9! possibilities after selecting the first number. If we index the permutations lexicographically, this means that permutations 1 to 362880 will have a 0 in first place. Permutations 362881 to 725760 will have a 1 in first place. 725761 to 1088640 will have a 2 in first place. 1000000 lies between the latter, so we have a 2 in first place. The first permutation starting with 2 is: 2013456789, this is number 725761.
We are now looking for the 1000000-725760=274240'th permutation of 013456789. Applying the same logic, we can see that there are 8! possibilities after selecting the first number. 725761 lies between 6*8! and 7*8!, so it's the sixth (in fact seventh, because the first number has index number, which is a 7 (2 has been done away with). The first permutation to have this number is 241920. Our number now is 27...
We are now looking for the 274240-241920=32320'th permutation of 01345689. Applying the same logic as before, we find that 6*7! < 32320 < 7*7!, so we take the sixth number, which is 8. Our number then is 278...
The new number is the 32320 - 6*7! = 2080'th permutation of 0134569. Between 2*6! and 3*6!, leaves us with 2783...
2080 - 2*6! = 640'th permutation of 014569. Between 5*5! and 6*5!, leaves us with 27839...
640 - 5*5! = 40'th permutation of 01456. Between 1*4! and 2*4!, leaves us with 278391...
40 - 1*4! = 16'th permutation of 0456. Between 2*3! and 3*3!, leaves us with 2783915...
We're now looking for the 16-2*3!=4'th permutation of 046. Rather than keeping on calculating, I just wrote them down and pick the fourth.
1 - 046
2 - 064
3 - 406
4 - 460
The number then is 27839165460.

This method revealed the answer 4782 in about a minute.
The first number to contain 1000 digits is 10^999, so we were looking for the first Fibonacci number greater than 10^999. If we call this number F: F > 10^999. To find the index of F, there exists a formula I found on Wikipedia. I put in the number 10^999 on the computer, which revealed 4781,859. For a number higher than 10^999, I had to round upwards, so it's the 4782'th term.

def longdiv(a):
	n=1
	c=0
	done=[]
	while len(set(done))==len(done):
		while n<a n="n%a" if n="" return c return t="1" m="2" for d in l="longdiv(d)" if l>t:
		t=l
		m=d

print m

This code returns the answer 983 in 0.806856 seconds.
The first time I noticed when digits were starting to repeat during decimal expansions was in elementary school, when we were taught long division, so I've been sitting on this knowledge for a while. A repeat will start once the number to be divided repeats itself. Once that (or occurs, I return the length of the decimal expansion. This is not always the same as the length of the repeating cycle, but I figured the maximum recurring cycle would be longer than any normal decimal expansion anyway, so I just used that.
The rest is just looping over candidates. I might come back to this problem later and do it properly, but I don't feel like doing that at the moment.

def nums(a,b):
    n=0
    while n**2+a*n+b in primes: n+=1
    return n

def eratosthenes(n):
       sieve = [ True for i in range(n+1) ]
       def markOff(pv):
               for i in range(pv+pv, n+1, pv):
                       sieve[i] = False
       markOff(2)
       for i in range(3, n+1):
               if sieve[i]:
                       markOff(i)
       return [ i for i in range(1, n+1) if sieve[i] ]

primes=eratosthenes(10000)
top=[0,0,0]
for p in range(-30,32):
	a=1-2*p
	b=p**2-p+41
	t=nums(a,b)
	if t>top[2]:
		top=[a,b,t]

print top[0]*top[1]

This code returns the answer -59231 in 0.013269 seconds.
Wolfram Mathworld showed me that the formula n^2-79n+1601 = (n-40)^2-(n-40)+41. hk wrote about doing this not with forty, but with another number p. This is built on the premise that prime generating formulas of the form n^2+an+b the same as Euler's formula, moved to the right. For a number p, the formula then becomes (n-p)^2-(n-p)+41 = n^2+(1-2p)n+(p^2-p+41). We know that |p^2-p+41|<1000, so I resolved that. Turns out, -30≤p≤31. I then wrote a program that checks for all those values of p how many primes are generated by their specific formulae. I used a sieve code (ripped from the Internet somewhere) to get a table of primes.
It turned out thatp=31 gave the most primes, so I let the program display the product of the a and b belonging to that.

My method revealed the answer 669171001 in about 15 minutes.
If you look at the spiral, you can see all the numbers on the diagonal to the top right are squares of odd numbers. The diagonal to the top left is a little more far away: it's the square of an even number, plus one. The other two diagonals are averages. I'll get to them in a minute.
Now, all odd numbers have the form 2n+1. I assigned every 'circle' (more of a rectangle) a number. The circle ending with 9 gets number 1, so the square at the end becomes (2*1+1)^2=9. The number in the bottom left corner becomes (2*1)^2+1=5. The number in the top right corner is the average of these two, namely 7. The other is the average of bottom left and the top right of the previous circle. The top right of the previous circle is (2*1-1)^2=1. The number in the bottom right then becomes 3.
For a row with index i, the formula for the top right becomes: 4i^2+4i+1. Bottom left: 4i^2+1. Top left: 4i^2+2i+1. Bottom right: 4i^2-2i+1. Adding these yields 16i^2+4i+4. If we input 0 into this formula, the answer is 4 (the 0th circle is the 1 in the middle), which is the only wrong answer this formula produces. We'll keep this in mind. Using WolframAlpha, I found the sum formula for n rows: 2(n+1)(8n^2+7n+6)/3. For a 1001 by 1001 spiral, the number in the top right is 1001^2. We input this in our sum formula, which yields 669171004. The only wrong part about this is that the first circle counts 0, not 4, so we subtract 3, leaving the answer.

nums=[]
for a in range(2,101):
	nums.extend(map(lambda x: a**x,range(2,101)))
print len(set(nums))

This code returns the answer 9183 in 0.025286 seconds.
I start by initiating a loop from 2 up to (but not including) 101. Then, using the map() function, I generate an array filled with a raised to the x'th power, where x loops in the same fashion. I then extend the answer array with the new one. Rinse and repeat for different values of a.
After looping, I convert nums to a set, so all duplicates are removed and return the number of items in it using len(). It'd have been more readable if I'd used two for loops, but this is just a tad faster.

def digits(n):
	return map(lambda x: ord(x)-48,str(n))

def power(n,p=5):
	return sum(map(lambda x: x**p,digits(n)))==n

nums=[]
for i in xrange(2,5*9**5):
	if power(i): nums.append(i)

print sum(nums)

This code returns the answer 443839 in 1.657156 seconds.
Yes, I used map JUST to confuse you. (I actually did that once in an informatics class to confuse the teacher when programming a prime sieve. Needless to say, he was NOT amused.) Not really, it's faster and I prefer oneliners. In the digits function, the number n is converted to a string, then I use the ord() function to convert the characters into actual numbers. The power() function takes to arguments, but the second isn't necessary. If p isn't specified, it will default to 5. It' s another map function that raises every digit returned from digits(n) to the p'th power, then sums the result and checks if it's equal to n.
For the limit, I did some simple arithmetic. 5*9^5=295245. This is the maximum value for any five-digit number and six-digit numbers don't have to be checked, because 6*9^5=354294. So the limit is 5*9^5. (It could've been lowered more, but that was too much work IMO )

coins=[2,5,10,20,50,100,200]

def p(n=200,coin=200):
	if coin==2: return(n/2+1)
	m=n/coin
	c=0
	newcoin=coins[coins.index(coin)-1]
	while m>=0:
		c+=p(n-m*coin,newcoin)
		m-=1
	return c

print p()

This code returns the answer 73682 in 0.00183 seconds.
I did some research into this, and if we only have coins of 2p and 1p in our possession, the number of possible combinations is n/2+1, assuming integer division. n/2 combinations for the number of 2p coins and one option for no 2p coins. If we add a 5p coin, there are n/5 combinations for the number 5p coins, as well as one option without 5p coins, so we loop over those combinations and check for each of them how many combinations there are possible. m can also be 0, so we've got that covered as well. The rest is done recursively.

def ispandigital(s):
	return s==s[::-1]
nums=set()
for i in range(123,9876):
	l=divisors(i)
	for d in l:
		e=i/d
		if e in l and ispandigital(str(d)+str(e)+str(i)):nums.add(i)

print sum(nums)

This code returns the answer 27796 in 0.275868 seconds.
The pandigital function really shows python's string handling capabilites. The syntax s[a:b:k] slices the string (sequence of characters) from a to b with step k. For example, if I have the string s="abcdef". If I take s[1:5:2], it starts at 'b", then takes two steps forward, giving "bd" Two steps later, the index would be 6, so that one isn't included. If we don't enter values for a and b, the whole string is take. Using -1 as step, Python will get the string backwards, so s[::-1] produces "fedcba".
What I did in the code was simply use a set (to avoid multiple combinations) and then check for all divisor pairs of the number whether they made a pandigital.

from __future__ import division
def iscurious(a,b):
	f=a/b
	a=str(a)
	b=str(b)
	for c in a:
		if c in b:
			if c=="0": return False
			try:
				a=float(a.replace(c,""))
				b=float(b.replace(c,""))
			except:
				return False
			if a==0 or b==0: return False
			return a/b==f
	return False

from fractions import Fraction
nums=[]
for i in range(11,100):
	for b in range(11,i):
		if iscurious(b,i): nums.append(Fraction(b,i))

print reduce(lambda x,y:x*y,nums)

This returns the answer 100 in 0.008861 seconds.
The first line turns integer divides into float divides, so I can check with extra precision. The code in the checking function is a bit clunky. I have to convert the thing to strings so I can check for duplicates and remove those duplicates without changing the number too much. Removing a 0 is a trivial example, so that will immediately return false. I use an error catching method because replacing the common number in 9/90 will result in trying to convert nothing into a float, which won't work. The rest is easy. If the numbers have nothing in common, it just does the loop and ends up return false.
The rest is just looping over possible combinations of b/i less than zero. If they have the curious cancelling method, I append them using the Fraction module, so their numerator and denominators are kept intact. I apply a reduce function to take their product. The program then outputs 1/100.

from math import factorial
def iscurious(n):
	return sum(map(lambda x: factorial(x),digits(n)))==n

s=0
for i in range(3,factorial(9)):
	s+=i*iscurious(i)

print s

This code returns the answer 40730 in 2.352839 seconds, which is pretty slow IMO.
The digits function is the same as seen in Problem 30. I map the factorial to each of the digits and then return whether the sum is equal to n.
The rest is a simple loop and output.

def rotate(n):
	i=1
	while n%i != n:
		i*=10
	return (n+(n%10)*i)/10

wrong=[0,2,4,5,6,8,9]	
def iscirc(n):
	if not isprime(n): return False
	if n in [2,3,5]: return True
	for c in str(n):
		if c in wrong: return False
	ing=str(n)
	for i in range(len(ing)):
		n=rotate(n)
		if not isprime(n):return False
	return True

c=0
i=2
while i<1000000:
	c+=iscirc(i)
	i+=1
print c

This code returns the answer 55 in 5.460466 seconds.
The first optimization was the rotate function. If you don't have to convert to a string and back, you lose less time, so I devised a mathematical process where I get the last number, multiply that by 10 until it's up front (I only determine the number of times once), then divide by 10 to remove it from the end.
Second optimization is in the circular checker. A number will never be prime if it ends in 0, 2, 4, 5, 6 or 8. (I filter out the exceptions 02 and 05 in the beginning of the function) So, if a prime contains one of those numbers, it will never be a circular prime, because one of it's brothers will end in those numbers. Other than that, simple looping over the prime and its brothers and we're done.

def dectobin(n):
	b=""
	while n:
		b+=str(n%2)
		n>>=1
	return b

print sum(map(lambda i:i*(ispalindrome(str(i)) and ispalindrome(dectobin(i))),range(1,1000000)))

This code returns the answer 872187 in 0.945575 seconds.
For converting the decimal integer to a binary, I use a string. It's just much easier and you don't have to think as much. Besides, it's easier for the palindrome checker, which is the same as before.
For the dectobin function, I get the final bit of n using the modulus, because if it's divisible by two, the final bit will be 0. If not, it will be one. I then append this using the + operator to the bitstring. I then use a right bitshift to make the last bit fall off. It might seem a bit confusing, but I combine the assignment and shit operators, so that's why the = is in there.
As for the main program, I get the range of numbers from 1 to 1 million, then check if it's both palindromic in base 10 and base 10, and use boolean math. After that's been done, the sum of all items in the list is printed.

def truncl(n):
	return n%(10**(len(str(n))-1))

def truncr(n):
	return n/10
	
def istrunc(n):
	for c in str(n):
		if c in [0,2,4,5,6,8]: return False
	if not isprime(n): return False
	p=n
	while p:
		p=truncr(p)
		if not isprime(p): return False
	while n:
		n=truncl(n)
		if not isprime(n): return False
	return True

i=11
s=0
c=0
while c<11:
	if istrunc(i):
		c+=1
		s+=i
	i+=1

print s

This code returns the answer 748317 in 5.008227 seconds.
truncl truncates a number from the left. This means that the leftmost digit must be removed. If we have 1234, this is 234, which is the same as 1234%1000. 1000=10**3=10**(4-1)=10**(len(1000)-1). Truncr does the same from the right and is considerably easier. Integer divison, yay!
For the istrunc() function, I check if one of the 'bad' numbers is in there, since those will eventually turn up at the back of the number during truncating. Same logic as the circular prime problem.
I create a dummy variable so I can use two loops to check whether it's a truncatable prime. The isprime() function is the same as always.
Since it was a given there were eleven of truncatable primes, I kept track of those instead of applying a maximum number.

def ispandigital(s):
	s=map(lambda x: ord(x)-48,s)
	for i in range(1,10):
		if i not in s: return False
		s.remove(i)
		if i in s: return False
	return not s
t=0
for i in range(1,10000):
	s=""
	j=1
	while len(s)<9:
		s+=str(i*j)
		j+=1
	if int(s)>t and ispandigital(s):t=int(s)
	
print t

This code returns the answer 932718654 in 0.074768 seconds.
For the pandigital function, I first convert the string to a list of numbers. Then, I check for all numbers from 1 to 10 (10 not included) whether they're in the string. If so, I remove them and check if there isn't another. (Pandigital means no repeats!). If there's a character in there like A or B, the function will still return False because s is not empty.
Other than that, simple product checking with an increasing counter.

t=0
p=0
for q in range(3,1000):
	c=0
	div=[d for d in divisors(q) if (d[0]t:
		p=q
		t=c
print p

This code returns the answer 840 in 0.006682 seconds.
Applying the same problem we had for problem 9 (man, that seems like a long time ago!), we get p=a+b+c=2m(m+n), because the perimeter is the sum of the sides. For what number p has this the greatest number of solutions? If there are multiple solutions for m and n, there will be multiple solutions for a, b and c. The more solutions you have for m and n, the more solutions you have for a, b and c. How do you maximize the number of solutions? Since we're multiplying here, the answer is pretty obvious: whichever number has got the most different divisors. However, because m+n > m and n < m, not all divisors qualify. I use a filtered list here, which is akin to filter() in it's function it takes every element in the list specified (in this case the divisors of q) and checks if the value at the end is true. I modified the divisors function to return pairs, so I only had to run those against eachother. For the actual value, I had to set up the conditional statement correctly.
Say, we find a pair of divisors a and b, so that q=a*b. Let's assume b < a. Then b=m and a=n+m, so m < m+n. We also know that n≤m. n=a-m=a-b, so a-b≤b. Adding b to both sides leaves us with a≤2b. Add to that b a. This gives us the statement a < b<≤2a.
In the code, a=d[0] (the first number the group of divisors) and b=d[1]. I then count the number of divisor pairs that satisfy the conditions outlined above and check whether it's greater than the maximum pairs already found.

s=''.join([ str(i) for i in range(1,1000000) ])
print reduce(lambda x,y: x*y, map(int,[s[0],s[9],s[99],s[999],s[9999],s[99999],s[999999]]))

This code returns the answer 210 in 0.470931.
Yay for brevity! First, I generate a list of integers from 1 to 1 million. This is the range object. Then I use a list filter to turn all numbers in the list into text, then join each element in the list so we get one big string. In the next rule, I make a list out of the required numbers, turn them back into integers with map and multiply them by eachother using reduce. Print the outcome and we're done.

from itertools import permutations
for i in range(4,10):
	for p in permutations(range(1,i+1)):
		p=int(''.join([str(i) for i in p]))
		if p>t and isprime(p): t=p
print t

This code returns the answer 7652413 in 2.421658 seconds.
Right of the bat, the thing I learnt about Python: it has a built in combinatorics module. This means that I don't have to worry about making a function to permutate the numbers, I can just put it in there and the thing will generate it for me. (This can also be used to solve problem 24 in one line: print ''.join(list(permutations("0123456789",10))[999999]).)
I just loop through all the numbers from 4 to 10 (not including 10) and check whether one of their 1-n pandigitals is prime. The rest is easy.

words=["A"...
triangles = [ n*(n+1)/2 for n in range(1,300) ]
c=0
for word in words:
	c+=(worth(word) in triangles)
print c

This code returns the answer 162 in 0.015856 seconds.
Instead of trying to dissolve the worth of a word into a triangle number, I generated a list with the first 300 triangle numbers, then checked if the worth was in there. The worth function is the same one as seen in problem 22.

def property(s):
	l=[int(s[1:4])%2,int(s[2:5])%3,int(s[3:6])%5, int(s[4:7])%7,int(s[5:8])%11,int(s[6:9])%13,int(s[7:10])%17]
	return not sum(l)
from itertools import permutations
s=0
for p in permutations(range(0,10),10):
	p=''.join([str(i) for i in p])
	s+=int(p)*property(p)
	
print s

This code returns the answer 16695334890 in 48.915536 seconds.
In the property function, I use string slices to lift the digits and put their remainders when divided by the numbers in the Problem statement in a list. If the sum of this list is 0 (ie. there are no remainders), the function has to return True, so I return not sum(l).
Other than that, I generate 0-9 pandigitals using the permutations function and check if they have the property.

from math import sqrt
def ispenta(n):
	v1=(1+sqrt(1+24*n))/6.0
	return round(v1,2)==v1

def pent(n):
	return n*(3*n-1)/2

check=False
for i in range(1,10000):
	p=pent(i)
	for j in range(i,10000):
		q=pent(j)
		if ispenta(q-p) and ispenta(p+q):
			print q-p
			check=True
			break
	if check: break

This code returns the answer 5482660 in 19.963802 seconds.
Because the answer has to be so large (I started out using the same method as in Problem 42), lists of pentagonal numbers aren't viable, so I made a pentagonal checker. I chose to round to two decimals for extra safety, but one or none would've done the trick as well.
For neatness, I also wrote a function that returns the n'th pentagonal number. The rest is just looping over candidates with some minor optimization. If the number is found, a check variable is changed that allows me to break out of the outer loop, because the break statement can only break the loop it's in.

h=[n*(2*n-1) for n in range(144,1000000)]
for n in h:
	if ispenta(n):
		print n
		break

This code returns the answer 1533776805 in 0.329313 seconds.
The fun thing about this is that every hexagonal number is also triangular (it's the other way around in only half of the cases), because h=n(2n-1)=2n(2n-1)/2. If we then say 2n=m+1, we get the following formula: h=(m+1)m/2, which is the formula for a triangle number. Since I already had something to check for pentagonal numbers, I figured I'd just loop over a lot of hexagonal numbers (generated using a list filter) and check to see if they were pentagonal. Since there is only one loop, I don't have to use check variables or the like.

squares=[i**2 for i in range(1,100)]
for i in range(33,100000,2):
	check=True
	for s in squares:
		if isprime(i):
			check=False
			break
		if isprime(i-2*s):
			check=False
			break
	if check:
		print i
		break

This code returns the answer 5777 in 0.030114 seconds.
Since I had a good primality checker around, I decided to check if a composite number minus two times a square was a prime. It also helped that the numbers had to be composites, so I could use a primality check to filter out the primes. Since we're only dealing with odd numbers here, I start with 33 (the first few had been shown in the problem) and take increment 2, skipping over all even numbers.
Every loop we assume i is an odd composite not writable as the sum of a prime and twice a square, so check is set to True. Then we start the loop over the squares, well, not really, since we still have to check whether i is prime. I do this inside of the loop because otherwise the program will set check to False and then start doing the whole loop, which takes time.
Inside of the loop, I check whether i minus two times a square is prime. If so, check is False (since it is an odd composite writable as etc. etc.). Finally, if check is True in the main loop, I print i and break out.

def primefactors(n):
	div=divisors(n)
	p=[]
	for d in div:
		if isprime(d): p.append(d)
	return p

i=647
while True:
	f=0
	for j in range(0,4):
		f+=(len(primefactors(i+j))>=4)
	if f==4: break
	i+=1
print i

This code returns the answer 134043 in 29.664553 seconds.
Divisors function and primality check same as seen before. I modified the divisors function so it would return a list of numbers, not a list of pairs. I think the primefactors function speaks for itself, not much to it.
Actually, the whole code hasn't got much to it, since it's bruteforce. I don't use upper bounds here, but rather break out of the loop if the consecutive integers have been found.

s=0
for x in range(1,1001):
	s=(s+(x**x))%10**10
	
print s

This code returns the answer 9110846700 in 0.018814 seconds.
Since we're just adding numbers, we don't have to worry about the first however-much-there-are digits, only the last ten. I don't use the += operator here so I can take the modulus in the same rule.

primes=eratosthenes(10000)
print [''.join(map(str,[p,p+3330,p+6660])) for p in primes if p+3330 in primes and p+6660 in primes and sorted(str(p+3330))==sorted(str(p+6660)) and sorted(str(p))==sorted(str(p+3330))][1]

This code returns the answer 296962999629 in 0.042279 seconds.
Yeah. That's right. That is two lines of code. Just for you.
The problem statement is a bit vague, so I was completely on the wrong track before reading up on it, so it just wouldn't work. For two days straight. >.< So after I'd found the increment had to be 3330, it was easy. I just generated all the primes up to 10000 and checked if their brothers were prime as well, as well as permutations of eachother. I'll explain what happens. The first part ''.join(map(str([p,p+3330,p+6660])) turns the numbers in to text and then concatenates them into one string. It does this for every p in primes, if p+3330 and p+6660 are prime. The digits have to be permutations of eachother as well, so turn the numbers into strings and sort them to check if they contain the same characters.
So now, we have a list of all concatenated numbers which have this property. Since the first number is 1487, I print the second item in the list.

def prefixsum(primes):
	ps=[0]
	s=0
	for p in primes:
		s+=p
		ps.append(s)
	return ps

primes=eratosthenes(999999)
lim=primes[-1]
ps=[p for p in prefixsum(primes) if p<2000000]

m=0
maxn=0
for p in ps:
	i=ps.index(p)
	for q in ps[i+m:]:
		n=q-p
		if n>lim: break
		j=ps.index(q)
		run=j-i
		if isprime(n) and run>m:
			m=run
			maxn=n
print maxn

This code returns the answer
Prefixsum() returns a list of the running sum. For instance, if I have the list [1,2,3,4,5,6], the prefix sum list would be [1,3,6,10,15,21]. The clever thing about this is that sum for numbers with index i to j in the earlier list are given by prefixsum[j]-prefixsum[i]. I learnt this from Stabby in the "The Last Human Being to Retort Shall Claim Victory (however, Soar in the Fashion of a Diurnal Bird triumphs all)"-thread.
Instead of looping over the prime list and looking for how long a run could be made, I chose to loop over the prefix sum list and check whether the number generated by those two loops was prime. Also, the prime number can't be greater than one million, so I took the last prime before 1000000 as an extra limit. If the sum would become higher than that, the inner loop would break.
At first, my code was really slow, but after applying a limit for the prefix sum list (I figured 2000000 was alright), it ran better.