Primitive Pythagoreans

Computer Science Level 5

The Pythagoreans were students of Pythagoras' school of thought.They subscribed to Pythagoreanism,a philosophy that was dominated by mathematics and mysticism.

A Pythagorean triple consists of three positive integers $(a,b,c)$ such that $a^2+b^2=c^2$ .

A triple is said to be primitive if $a$ , $b$ and $c$ are co-prime to each other( $GCD(a,b,c)=1$ ).

There are $16$ primitive triples with $c \leq 100$ and $a<b<c$ as shown below.

$( 3, 4, 5 ),( 5, 12, 13),( 8, 15, 17),( 7, 24, 25)$

$(20, 21, 29),(12, 35, 37),( 9, 40, 41),(28, 45, 53)$

$(11, 60, 61),(16, 63, 65),(33, 56, 65),(48, 55, 73)$

$(13, 84, 85),(36, 77, 85),(39, 80, 89),(65, 72, 97)$

Find the number of primitive Pythagorean triples with $c \leq 10^6$ and $a < b < c$ ?

Details and assumptions

You may assume that the triplets $(a,b,c)$ and $(b,a,c)$ are the same when counting.
This was inspired by a projecteuler problem
For more about Pythagoreans and irrational numbers take a look at Peter's note on the discovery of irrational numbers .
There is a great interactive tutorial on pythagorean triples here .

The answer is 159139.

5 solutions

Jack D'Aurizio
Apr 23, 2014

This is the same as counting the couples of integers $(u,v)$ such that: $1\leq u<v\leq 1000,$ $u^2+v^2\leq 10^6,$ $\gcd(u,v)=1$ and one integer between $u$ and $v$ is even. With a couple of cycles we get the answer: $159139$ . This is very close to $\frac{10^6}{2\pi}$ and not by chance, since the asymptotic probability of two random integers in $I=[1,N]$ of being coprime is $\frac{6}{\pi^2}$ and the asymptotic probability of two random integers $a,b\in I$ to satisfy $a^2+b^2\leq N^2$ is $\frac{\pi}{4}$ .

Silent Trailblazer
May 16, 2014

Using a trick in the helpful link given in the problem:

from fractions import gcd
def gen_triplet(m,n):
    ms = m*m
    ns = n*n
    mn = 2*m*n
    return ns - ms,mn,ms+ns

def triplet_count(limit):
    total = 0
    m_max = int(limit**.5)
    for m in range(1,m_max+1):
        for n in range(m+1,m_max+1):
            x,y,z = gen_triplet(m,n)
            if x<=limit and y<=limit and z<=limit and gcd(gcd(x,y),z) == 1:
                total += 1
    return total

triplet_count(1000000)
# takes ~1.0 seconds on my machine
# 159139

Amit Patil
May 9, 2014

http://en.wikipedia.org/wiki/Tree of primitive Pythagorean triples

Here is the python program for it:

import numpy as np

A = np.matrix([[1,-2,2],[2,-1,2],[2,-2,3]])
B= np.matrix([[1,2,2],[2,1,2],[2,2,3]])
C = np.matrix([[-1,2,2],[-2,1,2],[-2,2,3]])
x = np.matrix([[3],[4],[5]])

c = 10**6
def get_count(x):
        count = 0
        if x[2]<=c:
                count = 1 + get_count(A*x) + get_count(B*x) + get_count(C*x)
        return count

print get_count(x)

Hung Tran
Jun 16, 2014

This is my python program to calculate: result: 159139 Time execute: 1.1s on my machine

def count_primitive_tripple(limit):
      import math
      from fractions import gcd
      m = 0
      n = 0
      c = 0
      count = 0
      m_max = int(limit ** .5) + 1
      for n in range(1, m_max):
        for m in range(n + 1, m_max):
          m2 = m ** 2
          n2 = n ** 2
          c = m2 + n2
          if c > limit:
            break
          b = 2 * m * n
          a = m2 - n2
          if gcd(c, gcd(b, a)) == 1:
            count += 1
      print(count)
count_primitive_tripple(1000000)

Amit Patel
Apr 28, 2014

This program gives the correct output but takes lot of time..

def gcd(a, b):
    while b != 0:
    t = b
    b = a%b
    a = t
    return a


def find_triple(upper_boundary=1000000):
    cc = 0
    for c in xrange(5,upper_boundary+1):
    for b in xrange(4,c):
        for a in xrange(3,b):
            if (a*a + b*b == c*c and gcd(a,b) == 1):
                #print (a,b,c)
                cc = cc + 1
    return cc

print find_triple(1000000)

Output is : 159139

Primitive Pythagoreans

The answer is 159139.

5 solutions

0 pending reports