Euler project: Ulam spiral

Spiral like this:

This spiral is famous because it has the fact that most of prime number are present on the diagonal position of this rectangular.

Euler problem ask for the sum of all diagonal numbers like red ones above. The prime feature could not be used because not all diagonal positions are prime number. The hint is just every turn in this spiral, the length goes like: 1, 1, 2, 2, 3, 3, 4, 4,...

Since every turn is also the diagonal, except the first one, 2, use this length growth to build the sum is easy:

Every first odd turn should be taken care of because the actual diagonal number is the one before the turn number. Also, note the last turn is not included to form the required rectangular.

Fibonacci and yield

Look at this problem 25 from euler project below:

Yes it is simple recursion:


But this one is like running forever. Considering the fact it needs the first number with 1000 digits, not surprising.

Then I start browsing and googling, met this one, using yield to generate fibonacci number; hell, when I saw the word "yield" I was like YEAH THATS IT:


When I run it I almost wet myself. So fast that makes you cant help but sing a song about it.

Basically, it returns a generator. Generator in python is lazy, it never actually calculates the next one until you force it by calling next. Old version every time it generates a new fib number, it goes to the very first and runs back one by one later. When number gets big the problem is like hell. Use generator however, you only do one addition every time, plus, in the while loop, you only return one number each time. Well I dont know you, but to a python rookie like me...


what happens to the old version? Still running.

Euler project 12: triangle number

I am writing this only because I find these simple math trick is like magic.
Triangle number is ones composed by adding previous number together, like the additive analog of factorial number: Tn = 1 + 2 + 3 + ... + n. Now it asks what is the first triangle number with more than 500 divisors?

There are several ways to generate a triangle number. One is use the plain equation to sum up; other one is clearly use the sum-up equation Tn = n*(n-1)/2. However, since what we basically need here is to iterate all triangle numbers starts with 1 (or some bigger yet still small number), I add a step every time using Tn = Tn-1 + n. I think latter two should be mostly at the same speed.

Another thing is to find the number of divisors for a number. This is just iterate from 1 to sqrt(n), according to many math properties. Also since divisors appear in pairs, one might add two every time it finds a fit one if one uses this method; but minus one if the divisor it finds happens to be the sqrt(n).

Codes: