User login

Project Euler (Now all problems up to 50 solved)

13 replies [Last post]
161803398874989's picture
161803398874989
Offline
male
Joined: 12/13/2010

To be found at Projecteuler.net, project Euler is a series of challenging mathematical/computer programming problems.
Have any of you heard of it, or even participated? And if you've participated, what level are you? Also, username sharing! Laughing out loud
Mine is ThreeLetterSyndrom, I'm level 2. I will now post my solutions for the first 25 problems (I recreated them over the past two days since I didn't have a lot of them anymore). I do everything in Python (so noobish, I know. Tongue)

I will use spoiler tags, as well as explain my approach. I will explain the first problem(s) as good as I can to non-programmers, but later on some experience with programming languages (python isn't all that hard) will be required.
Problem 1:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Now this problem is fairly easy. Here's my code:

Spoiler: Highlight to view
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.

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Not too difficult. Here's my code (beware, weird functions!):

Spoiler: Highlight to view
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 (Crazy to start at the first three-digit number we know: 100. This will run until 999, which is still less than 1000. Wink 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.

After I've checked every possible combination I let the program display the largest palindrome on the screen.

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Rather than using a computer program, I used pencil and paper to find the answer. Here's how I did it.

Spoiler: Highlight to view

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.

Problem 6

The sum of the squares of the first ten natural numbers is,
1^2 + 2^2 + ... + 10^2 = 385

The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)^2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Solution done mathematically, with pencil and paper.

Spoiler: Highlight to view

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.

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

This one is a small challenge, but nothing monstrous. Here's the code.

Spoiler: Highlight to view
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. Wink 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.

Problem 8

Find the greatest product of five consecutive digits in the 1000-digit number.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

This one's really easy. Here's the code.

Spoiler: Highlight to view
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.

Problem 9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a^2 + b^2 = c^2

For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Mathematics > programming, again.

Spoiler: Highlight to view

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.

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.

Other than the huge amount of numbers you have to crunch, this is an easy problem. Code incoming!

Spoiler: Highlight to view
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.

Problem 11

In the 20×20 grid below, four numbers along a diagonal line have been marked in red. [Check the problems page to see which ones.]
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 × 63 × 78 × 14 = 1788696.

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

Pencil and paper ftw!

Spoiler: Highlight to view

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.

Problem 12
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

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

Let us list the factors of the first seven triangle numbers:

     1: 1
     3: 1,3
     6: 1,2,3,6
    10: 1,2,5,10
    15: 1,3,5,15
    21: 1,3,7,21
    28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

A bit more complex. I struggled to get this done in a reasonable time. Here's the code.

Spoiler: Highlight to view
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.

Problem 13

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
37107287533902102798797998220837590246510135740250
...[removed the rest for brevity]

This is stuff for oneliners. Here's the code:

Spoiler: Highlight to view
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. Laughing out loud
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.

Problem 14

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

This problem was more difficult and it took me some time to figure out. I found it hard even to get this under one minute. I managed to, though, so I'm proud of it. Code incoming.

Spoiler: Highlight to view
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 Tongue).
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.

Problem 15

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20×20 grid?

This one is way too easy now. We had the solution to this handed to us at school. Here's the code.

Spoiler: Highlight to view
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.

Problem 16

2^15 = 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^1000?

This uses one of my favourite functions in Python. The code isn't that elegant, but my first version (much slower) was uglier. It's a oneliner, though!

Spoiler: Highlight to view
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. Wink
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. Tongue

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.

Not much to this problem. Used pen and paper. Wink

Spoiler: Highlight to view

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. Smile

Problem 18

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

This one was pretty annoying. I can't remember whether I bruteforced this one or found a clever method on my first try. While making the program this time around, I used an algorithm described by Mather in the problem forum. Here's the code.

Spoiler: Highlight to view
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. ;)

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)?

Oh, Python, how do I love thee? Built-in datetime module! Code:

Spoiler: Highlight to view
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.

Problem 20

n! means n × (n − 1) × ... × 3 × 2 × 1

For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

This is the factorial function I was talking about earlier. A oneliner again. Here comes the code...

Spoiler: Highlight to view
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.

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.

A problem I struggled with, but I managed to work out the divisor function correctly, so it worked. Code:

Spoiler: Highlight to view
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.

Problem 22

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?

Nothing to difficult. Here's the code.

Spoiler: Highlight to view
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.

Problem 23

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

The problem itself is fairly easy... if you don't care about speed. Here's the code:

Spoiler: Highlight to view
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.

Problem 24

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Another pen and paper solution.

Spoiler: Highlight to view

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 Innocent 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.

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?

Mathematical solution.

Spoiler: Highlight to view

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.

Problem 26

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

An alright problem. I enjoyed this one. Here's the code:

Spoiler: Highlight to view
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 Innocent 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.

Problem 27

uler published the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

Using computers, the incredible formula n² − 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000

where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |−4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

This took way too long in my original implementation. Luckily, Wolfram Mathworld and the Problem forum came to my rescue.

Spoiler: Highlight to view
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.

Problem 28

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:
21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

Did this one by hand, but it took me pretty long.

Spoiler: Highlight to view

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.

Problem 29

Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

2^2=4, 2^3=8, 2^4=16, 2^5=32
3^2=9, 3^3=27, 3^4=81, 3^5=243
4^2=16, 4^3=64, 4^4=256, 4^5=1024
5^2=25, 5^3=125, 5^4=625, 5^5=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 a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

The first time I did this, it was a challenge, but now it's a piece of cake. Here's the code:

Spoiler: Highlight to view
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.

Problem 30

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

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

As 1 = 1^4 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.

This problem doesn't seem all that difficult, but it's wise to think about the upper limit. Here's the code:

Spoiler: Highlight to view
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 Tongue)

Problem 31

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

Had some difficulties with this (I'm not good at turning a story into mathematics/computer programs). Anyway, here's the code:

Spoiler: Highlight to view
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.

Problem 32

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

Here's the code:

Spoiler: Highlight to view
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.

Problem 33

The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

The first time I did this, it gave me a lot of trouble. Luckily, Python has it's very own Fractions module. Code incoming.

Spoiler: Highlight to view
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.

Problem 34

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

Pretty easy to just bruteforce, so that's what I did.

Spoiler: Highlight to view
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.

Problem 35

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

This problem got the ALL OF MY HATE-prize a few days in a row because I just couldn't figure out how to make it go fast.

Spoiler: Highlight to view
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.

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.)

Nothing too difficult.

Spoiler: Highlight to view
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.

Problem 37

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

I actually made the program layout at work (a large part is waiting) and when I got home, I got the answer in like 5 minutes of coding.

Spoiler: Highlight to view
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.

Problem 38

Take the number 192 and multiply it by each of 1, 2, and 3:

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?

This was actually my first time solving this problem. Nothing too difficult.

Spoiler: Highlight to view
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.

Problem 39

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?

Mathematics is awesome. It helped a lot in reducing the problem to a more simple one.

Spoiler: Highlight to view
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.

Problem 40

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021...

It can be seen that the 12th digit of the fractional part is 1.

If dn represents the nth digit of the fractional part, find the value of the following expression.

d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000

There were two ways to do this, by analysis or brute-force computing. I did the latter because I didn't want to count (this was the 12th in a row of problems, give me a break Tongue)

Spoiler: Highlight to view
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.

Problem 41

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

I learnt a few things about Python in the progress of doing this, so I think this is a great problem. (That sounds really weird.)

Spoiler: Highlight to view
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.

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?

I used something I learnt from Stabby here. Tongue

Spoiler: Highlight to view
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.

Problem 43

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

d2d3d4=406 is divisible by 2
d3d4d5=063 is divisible by 3
d4d5d6=635 is divisible by 5
d5d6d7=357 is divisible by 7
d6d7d8=572 is divisible by 11
d7d8d9=728 is divisible by 13
d8d9d10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

Not my favourite problem, since it takes a lot of time.

Spoiler: Highlight to view
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.

Problem 44

Pentagonal numbers are generated by the formula, Pn=n(3n−1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference is pentagonal and D = |Pk − Pj| is minimised; what is the value of D?

This was an interesting one to solve.

Spoiler: Highlight to view
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.

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(3n−1)/2 1, 5, 12, 22, 35, ...
Hexagonal Hn=n(2n−1) 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.

Another one of those triangle-pentagonal-hexagonal number problems. There are a lot of those. Tongue

Spoiler: Highlight to view
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.

Problem 46

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×1^2
15 = 7 + 2×2^2
21 = 3 + 2×3^2
25 = 7 + 2×3^2
27 = 19 + 2×2^2
33 = 31 + 2×1^2

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

The problem here is that you have to decide what approach to take.

Spoiler: Highlight to view
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.

Problem 47

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7
15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?

This problem had me confused at first, because I thought they meant that each number would have four distinct prime factors when compared with the other numbers.

Spoiler: Highlight to view
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.

Problem 48

The series, 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317.

Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000.

Clever solution for this one, I think.

Spoiler: Highlight to view
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.

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?

This won the ALL OF MY HATE-prize for sunday, monday and tuesday (which is today).

Spoiler: Highlight to view
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. Wink
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.

Problem 50

The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

A good runner-up for the ALL OF MY HATE-prize for sunday and monday.

Spoiler: Highlight to view
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.

That's all for now, folks!

_________________

"Betraying the Assassins is never good for one's health."
"Well, neither is drinking liquor, but I'm drawn to its dangers all the same."

stabguy's picture
stabguy
Offline
Administrator
male
Honolulu, HI USA
Joined: 09/15/2009
161803398874989 wrote:
I will use spoiler tags, as well as explain my approach.

You may want to close that spoiler tag somewhere. Wink

This returns the answer 233168 in a time of 0.000478 seconds.

Yay! Less than 1 millisecond. I like the way you avoided branching (if-then) by doing math with the boolean. Many programmers don't realize how much branching will slow down a program.

Is part of the challenge to solve the problems quickly? If so I would recommend two loops, one for multiples of 3 and the other for 5. I don't know python but it would look something like this:

s=0
i=3
while i<1000:
        s+=i
	i+=3

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

print s

The condition in the second loop is to avoid counting numbers twice that are multiples of both 3 and 5 (such as 15). Now the first loop can be replaced with a one liner based on Gauss' observation that the sum of the numbers between 1 and n equals n * (n + 1) / 2:

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

print s

Assuming 1000/3 is an integer divide (= 333) in python.

You won't even feel the blade.

JoeyFogey's picture
JoeyFogey
Offline
Administrator
male
Indianapolis, IN
Joined: 02/16/2010

It's fun to read all that, then read stab's sig.

PSN: JoeyFogey

Steam: JoeyFogey

Instagram: thatsketchyhero

161803398874989's picture
161803398874989
Offline
male
Joined: 12/13/2010

I used this because it was shorter in programming and I didn't have to think as much. Tongue
As for the problem itself, it's really easy to solve mathematically. Just go for 1000/3=333,333... => 333. For 5: 1000/5=200. The sum then becomes 3*333*(333+1)/2+5*200*(200+1)/2=267333. The problem is that we've counted all number divisible by both 3 and 5 twice. If a number is divisible by both 3 and 5, it's also divisible by 15. We can then subtract the sum of all numbers divisible by 15. 1000/15=66,666... => 66. The sum then becomes: 26733-15*66*(66+1)/2 = 267333 - 33165 = 234168. The caveat here is that we've counted 1000 as well, since 200*5=1000. So we subtract 1000 from the sum and we get the final answer. Wink

Part of the challenge is to write programs under one minute, but there's no one who checks that. All the 'rules' can be found on this page.

_________________

"Betraying the Assassins is never good for one's health."
"Well, neither is drinking liquor, but I'm drawn to its dangers all the same."

stabguy's picture
stabguy
Offline
Administrator
male
Honolulu, HI USA
Joined: 09/15/2009
161803398874989 wrote:
Part of the challenge is to write programs under one minute

Oh, I see. That makes more sense than writing a program that will run quickly. I was heading down the road toward solving it mathematically but decided to stop while it was still a program and not an equation. Grade

You won't even feel the blade.

161803398874989's picture
161803398874989
Offline
male
Joined: 12/13/2010

You're allowed to do it with pen and paper, though, only there are some problems that just don't work that way, like problem 67. Tongue

_________________

"Betraying the Assassins is never good for one's health."
"Well, neither is drinking liquor, but I'm drawn to its dangers all the same."

PatrickDeneny's picture
PatrickDeneny
Offline
Citizen
Joined: 05/24/2010

The solution to Problem 5 is just brilliant Laughing out loud

161803398874989's picture
161803398874989
Offline
male
Joined: 12/13/2010

Thanks, Patrick! I think you'll like my solution for problem 9 (coming up now) even more. Wink

_________________

"Betraying the Assassins is never good for one's health."
"Well, neither is drinking liquor, but I'm drawn to its dangers all the same."

PatrickDeneny's picture
PatrickDeneny
Offline
Citizen
Joined: 05/24/2010
161803398874989 wrote:
Thanks, Patrick! I think you'll like my solution for problem 9 (coming up now) even more. Wink

Indeed I do Tongue Do you just remember all these rules and equations? I love science and was decent enough at GCSE maths, but I certainly don't have a mathematical brain like you. I enjoy seeing these solutions though Tongue

161803398874989 wrote:
32 + 42 = 9 + 16 = 25 = 52.

This bit had me confused for ages until I realised the twos were meant to be squared symbols Tongue

161803398874989's picture
161803398874989
Offline
male
Joined: 12/13/2010

Haha, that's an oversight indeed. I figured they'd just copy over. Tongue If you're confused, you can always check the problems page linked at the top of the problem. I'll fix it now. Wink

I remember a lot of formulae since I can deduce most of them, but there's also stuff I look up, like Euclid's formula. I think you'll also like my solutions to problems 17, 24 and 25. I'm off now, however. Wink

_________________

"Betraying the Assassins is never good for one's health."
"Well, neither is drinking liquor, but I'm drawn to its dangers all the same."

JoeyFogey's picture
JoeyFogey
Offline
Administrator
male
Indianapolis, IN
Joined: 02/16/2010

Slapped myself repeatedly for attempting to read all 50 problems. O_o

PSN: JoeyFogey

Steam: JoeyFogey

Instagram: thatsketchyhero

161803398874989's picture
161803398874989
Offline
male
Joined: 12/13/2010

Haha, sorry for that. You must've liked my solution to 41 a lot. Tongue

51 is giving me a hard time. My initial code runs pretty fast for all numbers under 100000, but for under a million, it takes ages. By ages, I mean 410 seconds, as opposed to 4 seconds for a limit of 100000.
If we get technical, we'd say my program would run in about O(n^2), which means that if the program gets twice as long, the execution time gets four times as long.
I'd really like to get rid of this business, but I don't think I can. I have to compare every number for one list to every number of another list, so you automatically get this.

I really need to come up with a better method. I've been busy with this particular problem for about 8 hours now (I've eaten in between, though), so I'm taking a break now. A friend of mine is getting his diploma today (got mine yesterday) and afterwards we'll go have a beer or something, or so I'm told. Tongue

_________________

"Betraying the Assassins is never good for one's health."
"Well, neither is drinking liquor, but I'm drawn to its dangers all the same."

stabguy's picture
stabguy
Offline
Administrator
male
Honolulu, HI USA
Joined: 09/15/2009
161803398874989 wrote:
I'd really like to get rid of this business, but I don't think I can. I have to compare every number for one list to every number of another list, so you automatically get this.

I haven't read problem 51 but may be able to help get your O(n2) algorithm down to O(n log(n)) or even O(n).

If you're trying to compare every number in list A to every number in list B, sort both lists first. Once sorted, keep an index i into list A and index j into list B. Do your comparison between A[i] and B[j]. Then increment the index of whichever element was smaller. If the sizes of A and B are both O(n), then this algorithm is O(n log(n)) + O(n log(n)) + O(n) = O(n log(n)) [assuming you use a decent sorting algorithm]

If you're comparing for equality, the really aggressive way to solve problems like this is with a hash table. Iterate over all the elements in list A or list B (choose the smaller list when possible) and insert them into a hash table. Now iterate over all the elements in the other list and look them up in the hash table. If there's a hit, that's a match. Hash tables have O(1) insert and lookup so this algorithm is O(n).

I hope I understood your requirements correctly.

You won't even feel the blade.

161803398874989's picture
161803398874989
Offline
male
Joined: 12/13/2010

I actually fixed it now. Instead of comparing primes, I just generated a prime list, then made families out of those, corresponding to the requirements and checked if those were primes. It runs in just under 2.5 seconds.

I'm currently working on Problem 60. I think I've got a good approach there. Get primes, generate string combinations and see if those satisfy the conditions. I need to generate a quintuplet, so I'll just go on to take the pairs found and check their combinations. This may be an O(n^2) process, but there are only 2324 pairs under 10^7, so that's doable. I can filter out most of them very quickly to get to the triples and there are even less of those. After that, we'll get to the quintuples, which is what we want.
Generating the primes and finding the pairs took about 30 seconds so far, so I still have 30 seconds left, without having to use a computation-intensive function.

_________________

"Betraying the Assassins is never good for one's health."
"Well, neither is drinking liquor, but I'm drawn to its dangers all the same."