2012-05-06

Project Euler problem 182 - Solved

Comments

The statement of the problem can be found here.

In this problem we are given two primes p and q that are used to generate an n for an RSA key-pair.

As it states to complete a key pair one must choose an exponent e in the range but for each e there will be a number of unconcealed messages, this means that .

The number of unconcealed messages for an exponent e in modulo N with is equal to

Knowing this it is pretty easy to write a code that finds the exponents that generate the fewer unconcealed messages and add them up. The python source code can be downloaded (problem182.py):

import gmpy

if __name__ == '__main__':
    p = 1009
    q = 3643
    n = p * q
    phi_n = n - p - q + 1
    result = 0
    min_res = 9999999999999
    for e in range(1, phi_n):
        if gmpy.gcd(e, phi_n) != 1:
            continue
        num_unconcealed = (gmpy.gcd(e-1, p-1) + 1) * (gmpy.gcd(e-1, q-1) + 1)
        if num_unconcealed < min_res:
            min_res = num_unconcealed
            result = e
        elif num_unconcealed == min_res:
            result += e
    print("The result is: {0}".format(result))
2011-12-27

Project Euler problem 142 - Solved

Comments

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

Comments

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)