## Sunday, February 23, 2014

### Perl solution to Project Euler's problem #2

http://projecteuler.net/problem=2
```#!/usr/local/bin/perl
\$fib1 = 1;
\$fib2 = 2;
\$sum = 1;
while (\$fib2 < 4000000) {
if(\$fib2 % 2 == 0){
\$sum += \$fib2;
}
\$aux = \$fib2;
\$fib2 += \$fib1;
\$fib1 = \$aux;
}

print \$sum;```

### Perl solution to Project Euler's problem #1

```#!/usr/local/bin/perl
\$sum = 0;
for \$i (1 .. 999) {
if((\$i % 3) == 0){
\$sum += \$i;
}
else
{
if((\$i % 5) == 0){
\$sum += \$i;
}
}
}

print \$sum;
```

https://ideone.com/5NrFot

## Tuesday, December 3, 2013

### Solution

```def is_prime(x, primes):
for p in primes:
if x % p == 0:
return False
return True

assert is_prime(3, )
assert not is_prime(4, [2, 3])

def smallest_common_multiple_of_all_numbers_up_to(x):
if x == 1:
return 1
y = 1
primes = []
for i in range(2, x + 1):
if is_prime(i, primes):
primes.append(i)
y *= i
continue
if y % i == 0:
continue
for p in primes:
if (y * p) % i == 0:
y *= p
break
return y

assert smallest_common_multiple_of_all_numbers_up_to(3) == 6
assert smallest_common_multiple_of_all_numbers_up_to(10) == 2520

print smallest_common_multiple_of_all_numbers_up_to(20)
```

## Sunday, December 1, 2013

### Solution

```def reverse(number):
result = 0
while number > 0:
result = result * 10 + (number % 10)
number = int(number / 10)
return result

def is_palindrome(number):
return number == reverse(number)

largestPalindrome = 0
a = 999
while a >= 100:
if a % 11 == 0:
b = 999
db = 1
else:
b = 990
db = 11
while b >= a:
if a*b <= largestPalindrome:
break
if is_palindrome(a*b):
largestPalindrome = a*b
b = b-db
a = a-1
print largestPalindrome```

## Problem 6 - Sum square difference

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

#### its time complexity is O(n) (linear)

it's under a second for 10,000 but it takes a while for 100,000
```def sum(an):
n = int(an / 2)
return n * (1 + an)

def sum_square(an):
sum = 0
for i in range(1, an + 1):
sum += i ** 2
return sum

def problem6(an):
return sum(an) ** 2 - sum_square(an)

print problem6(100)
```

## Problem 3 - Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

### Simplest solution

#### its time complexity is O(n) (linear) with the largest factor

It means it's fast for 600851475143 but not for 600851475145
```def get_prime_factors(number):
factor=2
while number <> 1 & factor <= number:
factor += 1
while number % factor == 0:
yield factor
number /= factor

for x in get_prime_factors(600851475143):
print x
```

### Fastest solution

#### its time complexity is O(sqrt(n)) (fractional power) with the largest factor.

```def get_prime_factors(number):
while number % 2 == 0:
yield 2
number /= 2
factor=1
maxFactor = int(number ** .5)
while number <> 1 & factor <= maxFactor:
factor += 2
while number % factor == 0:
yield factor
number /= factor
if number > 1:
yield number

for x in get_prime_factors(600851475145):
print x```

## Problem 2 - Even Fibonacci numbers

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.

### Python solution

#### it is very fast even for numbers up to 1e200

```def fibsum(maximum):
fib1 = 0
fib2 = 1
sum = 0
while fib2 < maximum:
aux = fib2
fib2 += fib1
fib1 = aux
if fib2 & 1 == 0:
sum += fib2
return sum

print fibsum(int(4e6))```