pythagorean_triplet.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
from itertools import combinations
from fractions import gcd
from math import ceil


def is_triplet(three):
    """
    Is this a Pythagorean triplet?
    """
    a, b, c = sorted(three)
    return a**2 + b**2 == c**2


def triplets_in_range(start, end):
    """
    Get Pythagorean triplets with all members in the (start, end) range (inclusive)
    """
    return set(filter(
        is_triplet,
        combinations(range(start, end+1), 3)
    ))


def make_triplet(m, n):
    """
    Make a pythagorean triplet from coprime integers m and n
    using a=(m^2-n^2), b=2*m*n and c=(m^2+n^2)
    """
    a, b, c = sorted((
        abs(m**2 - n**2),
        2 * m * n,
        m**2 + n**2
    ))

    return (a, b, c)


def coprime(pair):
    """
    Are m and n coprime?
    """
    m, n = pair
    return gcd(m, n) == 1


def primitive_triplets(starter):
    if starter % 4 != 0:
        raise ValueError("Must start with a multiple of 4")

    # Working with a=(m^2-n^2), b=2*m*n and c=(m^2+n^2)
    # and taking the starter value to be b
    product = int(starter / 2)
    limit = int(ceil(product ** 0.5))

    # (m, n) multiple pairs
    pairs = (
        (x, product // x)
        for x in range(1, limit) if product % x == 0
    )

    return {
        make_triplet(m, n)
        for (m, n) in filter(coprime, pairs)
    }

Comments


You're not logged in right now. Please login via GitHub to comment