2011-12-27

# Project Euler problem 142 - Solved

The statement of the problem can be found here.

In order to solve this problem, first, we have to express the different equations and then start working with them.

Let’s begin expressing the equations:

Now let’s begin working with them, we can express:

So, bruteforcing only the values we can obtain possible solutions, but in order to get the values of x, y z we need to solve the linear equation:

which has only one solution, this one:

From this solution we can see that $D+C$ must be even, so D and C must have the same parity, thus E and F must have the same parity.

With all this in mind we can easily write an algorithm in Python to solve the problem (problem142.py):

from itertools import count, takewhile

is_square = lambda x: int(x ** 0.5) ** 2 == x

if __name__ == '__main__':
for a in count(6):
a_2 = a ** 2
for f in (f for f in takewhile(lambda f: f < a, count(4)) if is_square(a_2 - f ** 2)):
f_2 = f ** 2
c_2 = a_2 - f_2
setoff = 3 if (f & 1) else 2
for e in (e for e in takewhile(lambda e: e ** 2 < c_2, count(setoff, 2)) if is_square(c_2 - e ** 2) and is_square(a_2 - e ** 2)):
e_2 = e ** 2
b_2 = c_2 - e_2
d_2 = a_2 - e_2
z = -(d_2 - c_2) // 2
y = -(-d_2 - c_2 + 2 * b_2) // 2
x = (d_2 + c_2) // 2
print('The result is: (x){0} + (y){1} + (z){2} = {3}'.format(x, y, z, x + y + z))
exit(0)

2011-09-25

# Project Euler problem 129 - Solved

The statement of the problem can be found here.

Using the same technique as in my previous post to determine whether a number divides a repunit or not, we create a function to find the A(n) by bruteforcing it.

As A(n) can’t be greater than n we start searching for the number we are looking for from 1000001. The algorithm is really simple:

from CommonFunctions import *
from itertools import *

def A(n):
i = 2
while (mod_pow(10, i, 9 * n) != 1):
i += 1
return i

limit = 10 ** 6

if __name__ == '__main__':
for n in count(1000001, 2):
if str(n)[-1] == '5':
continue
x = A(n)
if x > limit:
break
print("The result is:", n)

2011-09-03

# Project Euler problem 132 - Solved

The statement of this problem can be found here.

In order to solve this problem the first important thing to notice is how a repunit can be represented: $R(k) = \frac{10^k - 1}{9}$

Therefore, we can express if a repunit is divisible by p like:

So if $10^k \mod 9p = 1$, then p divides $R(10^k)$. The problem now is how to calculate the remainder in an efficient way as it is impossible to calculate the remainder to a number of a thousand million digits. Here we can use Modular exponentiation as what we need to calculate is the remainder of a number than can be expressed as a power with base 10 and exponent 9.

The solution for this code in Python (problem132.py) is really simple (the CommonFunctions file can be found in my wiki):

from CommonFunctions import *
from itertools import *

if __name__ == '__main__':
primes = find_primes_less_than(10 ** 6)
base = 10
exp = 10 ** 9
result = sum(islice((p for p in primes if mod_pow(base, exp, 9 * p) == 1), 0, 40))
print("The result is:", result)