python - teorema - Generando trillizos pitagóricos únicos y ordenados

teorema de pitagoras primaria

Question

Este es un programa que escribí para calcular trillizos pitagóricos. Cuando ejecuto el programa, imprime cada conjunto de tripletes dos veces debido a la instrucción if. ¿Hay alguna manera de decirle al programa que solo imprima una nueva serie de trillizos una vez? Gracias.

import math

def main():
    for x in range (1, 1000):
        for y in range (1, 1000):
            for z in range(1, 1000):
                if x*x == y*y + z*z:
                    print y, z, x
                    print ''-''*50

if __name__ == ''__main__'':
    main()  

Answer 1

Debe definir x <y <z.

for x in range (1, 1000):
    for y in range (x + 1, 1000):
            for z in range(y + 1, 1000):

Otra buena optimización sería usar solo xey, y calcular zsqr = x * x + y * y. Si zsqr es un número cuadrado (o z = sqrt (zsqr) es un número entero), es un triplete, de lo contrario no. De esta forma, solo necesita dos bucles en lugar de tres (para su ejemplo, eso es aproximadamente 1000 veces más rápido).

Answer 2

Escribí ese programa en Ruby y es similar a la implementación de Python. La línea importante es:

if x*x == y*y + z*z && gcd(y,z) == 1:

Luego debe implementar un método que devuelva el mayor divisor común (gcd) de dos números dados. Un ejemplo muy simple en Ruby nuevamente:

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

El método completo de Ruby para encontrar los trillizos sería:

def find_triple(upper_boundary)

  (5..upper_boundary).each {|c|
    (4..c-1).each {|b|
      (3..b-1).each {|a|
        if (a*a + b*b == c*c && gcd(a,b) == 1)
          puts "#{a} /t #{b} /t #{c}"
        end
      }
    }
  }
end

Answer 3

Sí hay.

De acuerdo, ahora querrás saber por qué. ¿Por qué no limitarlo para que z> y? Tratar

for z in range (y+1, 1000)

Answer 4

Los algoritmos enumerados anteriormente para generar tripletas pitagóricas son todas modificaciones del enfoque ingenuo derivado de la relación básica a^2 + b^2 = c^2 donde (a, b, c) es una tripleta de enteros positivos. Resulta que los trillizos pitagóricos satisfacen algunas relaciones bastante notables que pueden usarse para generar todos los trillizos pitagóricos.

Euclid descubrió la primera relación de ese tipo. Él determinó que para cada triple pitagórica (a, b, c) , posiblemente después de un reordenamiento de b hay números enteros relativamente primos positivos m y n con m > n , al menos uno de los cuales es par, y un entero positivo k tal que

a = k (2mn)
b = k (m^2 - n^2)
c = k (m^2 + n^2)

Luego, para generar trillizos pitagóricos, genere enteros positivos primos relativamente grandes m y n de paridad diferente, y un entero positivo k y aplique la fórmula anterior.

struct PythagoreanTriple {
    public int a { get; private set; }
    public int b { get; private set; }
    public int c { get; private set; }

    public PythagoreanTriple(int a, int b, int c) : this() {
        this.a = a < b ? a : b;
        this.b = b < a ? a : b;
        this.c = c;
    }

    public override string ToString() {
        return String.Format("a = {0}, b = {1}, c = {2}", a, b, c);
    }

    public static IEnumerable<PythagoreanTriple> GenerateTriples(int max) {
        var triples = new List<PythagoreanTriple>();
        for (int m = 1; m <= max / 2; m++) {
            for (int n = 1 + (m % 2); n < m; n += 2) {
                if (m.IsRelativelyPrimeTo(n)) {
                    for (int k = 1; k <= max / (m * m + n * n); k++) {
                        triples.Add(EuclidTriple(m, n, k));
                    }
                }
            }
        }

        return triples;
    }

    private static PythagoreanTriple EuclidTriple(int m, int n, int k) {
        int msquared = m * m;
        int nsquared = n * n;
        return new PythagoreanTriple(k * 2 * m * n, k * (msquared - nsquared), k * (msquared + nsquared));
    }
}

public static class IntegerExtensions {
    private static int GreatestCommonDivisor(int m, int n) {
        return (n == 0 ? m : GreatestCommonDivisor(n, m % n));
    }

    public static bool IsRelativelyPrimeTo(this int m, int n) {
        return GreatestCommonDivisor(m, n) == 1;
    }
}

class Program {
    static void Main(string[] args) {
        PythagoreanTriple.GenerateTriples(1000).ToList().ForEach(t => Console.WriteLine(t));            
    }
}

El artículo de Wikipedia sobre Fórmulas para generar triples pitagóricos contiene otras fórmulas similares.

Answer 5

Los algoritmos se pueden ajustar para velocidad, uso de memoria, simplicidad y otras cosas.

Aquí hay un algoritmo pythagore_triplets ajustado para la velocidad, a costa del uso de la memoria y la simplicidad. Si todo lo que quieres es velocidad, este podría ser el camino a seguir.

Cálculo de list(pythagore_triplets(10000)) toma 40 segundos en mi computadora, frente a 63 segundos para el algoritmo de ΤΖΩΤΖΙΟΥ y posiblemente días de cálculo para el algoritmo de Tafkas (y todos los demás algoritmos que utilizan 3 bucles incorporados en lugar de solo 2).

def pythagore_triplets(n=1000):
   maxn=int(n*(2**0.5))+1 # max int whose square may be the sum of two squares
   squares=[x*x for x in xrange(maxn+1)] # calculate all the squares once
   reverse_squares=dict([(squares[i],i) for i in xrange(maxn+1)]) # x*x=>x
   for x in xrange(1,n):
     x2 = squares[x]
     for y in xrange(x,n+1):
       y2 = squares[y]
       z = reverse_squares.get(x2+y2)
       if z != None:
         yield x,y,z

>>> print list(pythagore_triplets(20))
[(3, 4, 5), (5, 12, 13), (6, 8, 10), (8, 15, 17), (9, 12, 15), (12, 16, 20)]

Tenga en cuenta que si va a calcular los primeros mil millones de trillizos, este algoritmo se bloqueará antes incluso de que comience, debido a un error de falta de memoria. Entonces el algoritmo de ΤΖΩΤΖΙΟΥ es probablemente una opción más segura para valores altos de n.

Por cierto, aquí está el algoritmo de Tafkas, traducido a python para el propósito de mis pruebas de rendimiento. Su defecto es requerir 3 bucles en lugar de 2.

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

def find_triple(upper_boundary=1000):
  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):
          yield a,b,c

Answer 6

Los triples pitagóricos son un buen ejemplo para reclamar " bucles considerados dañinos ", porque los bucles nos seducen para pensar en contar, a menudo la parte más irrelevante de una tarea.

(Voy a seguir con el pseudocódigo para evitar sesgos del lenguaje, y para mantener el pseudocódigo simplificado, no optimizaré los cálculos múltiples de, por ejemplo, x * x e y * y ).

Versión 1 :

for x in 1..N {
    for y in 1..N {
        for z in 1..N {
            if x * x + y * y == z * z then {
                // use x, y, z
            }
        }
    }
}

es la peor solución Genera duplicados y atraviesa partes del espacio que no son útiles (por ejemplo, siempre que z < y ). Su complejidad de tiempo es cúbica en N

La versión 2 , la primera mejora, proviene de requerir que x < y < z mantenga, como en:

for x in 1..N {
    for y in x+1..N {
        for z in y+1..N {
            if x * x + y * y == z * z then {
                // use x, y, z
            }
        }
    }
}

lo que reduce el tiempo de ejecución y elimina las soluciones duplicadas. Sin embargo, sigue siendo cúbico en N ; la mejora es solo una reducción del coeficiente de N -cubed.

No tiene sentido continuar examinando los valores crecientes de z después de z * z < x * x + y * y ya no se cumple. Ese hecho motiva a la Versión 3 , el primer paso para alejarse de la iteración de fuerza bruta sobre z :

for x in 1..N {
    for y in x+1..N {
        z = y + 1
        while z * z < x * x + y * y {
            z = z + 1
        }
        if z * z == x * x + y * y and z <= N then {
            // use x, y, z
        }
    }
}

Para N de 1000, esto es aproximadamente 5 veces más rápido que la Versión 2, pero sigue siendo cúbico en N

La siguiente idea es que y son las únicas variables independientes; z depende de sus valores, y el último valor de z considerado para el valor anterior de y es un buen valor de búsqueda inicial para el próximo valor de y . Eso lleva a la Versión 4 :

for x in 1..N {
    y = x+1
    z = y+1
    while z <= N {
        while z * z < x * x + y * y {
            z = z + 1
        }
        if z * z == x * x + y * y and z <= N then {
            // use x, y, z
        }
        y = y + 1
    }
}

que permite que z "barra" los valores de arriba x solo una vez. No solo es 100 veces más rápido para N de 1000, sino que es cuadrático para N , por lo que la aceleración aumenta a medida que N crece.

Me he encontrado con este tipo de mejora con la frecuencia suficiente como para desconfiar de "contar bucles" para cualquier uso menos trivial (por ejemplo, atravesar una matriz).

Actualización: Aparentemente debería haber señalado algunas cosas sobre V4 que son fáciles de pasar por alto.

1. Ambos ciclos while están controlados por el valor de z (uno directamente, el otro indirectamente a través del cuadrado de z ). El while interior en realidad está acelerando el while exterior, en lugar de ser ortogonal a él. Es importante observar lo que están haciendo los bucles, no simplemente contar cuántos bucles hay.

2. Todos los cálculos en V4 son estrictamente una aritmética entera. La conversión a / desde coma flotante, así como los cálculos de coma flotante, son costosos en comparación.

3. V4 se ejecuta en memoria constante, requiriendo solo tres variables enteras. No hay matrices o tablas hash para asignar e inicializar (y, potencialmente, para causar un error de falta de memoria).

4. La pregunta original permitió que todos los x de x , y , y x varíen en el mismo rango. V1..V4 siguió ese patrón.

A continuación hay un conjunto de tiempos no muy científicos (utilizando Java en Eclipse en mi computadora portátil más vieja con otras cosas en ejecución ...), donde el "uso x, y, z" se implementó instanciando un objeto Triple con los tres valores y ponerlo en una ArrayList. (Para estas corridas, N se estableció en 10,000, que produjo 12,471 triples en cada caso).

Version 4:           46 sec.
using square root:  134 sec.
array and map:      400 sec.

El algoritmo de "matriz y mapa" es esencialmente :

squares = array of i*i for i in 1 .. N
roots = map of i*i -> i for i in 1 .. N
for x in 1 .. N
    for y in x+1 .. N
        z = roots[squares[x] + squares[y]]
        if z exists use x, y, z

El algoritmo "usar raíz cuadrada" es esencialmente :

for x in 1 .. N
    for y in x+1 .. N
        z = (int) sqrt(x * x + y * y)
        if z * z == x * x + y * y then use x, y, z

El código real para V4 es:

public Collection<Triple> byBetterWhileLoop() {
    Collection<Triple> result = new ArrayList<Triple>(limit);
    for (int x = 1; x < limit; ++x) {
        int xx = x * x;
        int y = x + 1;
        int z = y + 1;
        while (z <= limit) {
            int zz = xx + y * y;
            while (z * z < zz) {++z;}
            if (z * z == zz && z <= limit) {
                result.add(new Triple(x, y, z));
            }
            ++y;
        }
    }
    return result;
}

Tenga en cuenta que x * x se calcula en el ciclo externo (aunque no me molesté en almacenar en caché z * z ); optimizaciones similares se realizan en las otras variaciones.

Estaré encantado de proporcionar el código fuente de Java bajo pedido para las otras variaciones que yo programe, en caso de que haya implementado mal algo.

Answer 7

Versión 5 a Joel Neely.

Dado que X puede ser máximo de ''N-2'' e Y puede ser máximo de ''N-1'' para el rango de 1..N. Dado que Z max es N y Y max es N-1, X puede ser máximo de Sqrt (N * N - (N-1) * (N-1)) = Sqrt (2 * N - 1) y puede comenzar desde 3 .

MaxX = ( 2 * N - 1 ) ** 0.5

for x in 3..MaxX {
  y = x+1
  z = y+1
  m = x*x + y*y
  k = z * z
  while z <= N {
     while k < m {
        z = z + 1
        k = k + (2*z) - 1
    }
    if k == m and z <= N then {
        // use x, y, z
    }
    y = y + 1
    m = m + (2 * y) - 1
  }
 }

Answer 8

Solo estoy revisando, pero he estado usando el siguiente código para hacer triples pitagóricos. Es muy rápido (y he intentado algunos de los ejemplos aquí, aunque los aprendí y escribí el mío y volví y revisé aquí (hace 2 años)). Creo que este código encuentra correctamente todas las tripletas pitagóricas hasta (nombra tu límite) y bastante rápido también. Usé C ++ para hacerlo.

ullong no tiene firma por mucho tiempo y creé un par de funciones para cuadrar y enraizar mi función de raíz básicamente dicho si la raíz cuadrada del número dado (después de hacerla número entero (integral)) al cuadrado no es igual al número devuelve -1 porque no es rootable. _square y _root hacen lo que se esperaba de la descripción anterior, conozco otra forma de optimizarlo pero aún no lo he probado ni probado.

generate(vector<Triple>& triplist, ullong limit) {
cout<<"Please wait as triples are being generated."<<endl;
register ullong a, b, c;
register Triple trip;
time_t timer = time(0);

for(a = 1; a <= limit; ++a) {
    for(b = a + 1; b <= limit; ++b) {
        c = _root(_square(a) + _square(b));

        if(c != -1 && c <= limit) {
            trip.a = a; trip.b = b; trip.c = c;

            triplist.push_back(trip);

        } else if(c > limit)
            break;
    }
}

timer = time(0) - timer;
cout<<"Generated "<<triplist.size()<<" in "<<timer<<" seconds."<<endl;
cin.get();
cin.get();

}

Déjenme saber lo que todos ustedes piensan. Genera todas las tripletas primitivas y no primitivas de acuerdo con el docente al que la entregué. (Ella lo probó hasta 100 si no recuerdo mal).

Los resultados de la v4 proporcionada por un codificador anterior aquí son

A continuación hay un conjunto de tiempos no muy científicos (utilizando Java en Eclipse en mi computadora portátil más vieja con otras cosas en ejecución ...), donde el "uso x, y, z" se implementó instanciando un objeto Triple con los tres valores y ponerlo en una ArrayList. (Para estas corridas, N se estableció en 10,000, que produjo 12,471 triples en cada caso).

Versión 4: 46 seg. usando la raíz cuadrada: 134 seg. matriz y mapa: 400 seg.

Los resultados de la mía son cuántos triples generar: 10000

Por favor espere mientras se generan los triples. Generado 12471 en 2 segundos.

Eso es antes de que empiece a optimizar a través del compilador. (Recuerdo haber conseguido previamente 10000 a 0 segundos con toneladas de opciones especiales y esas cosas). Mi código también genera todos los triples con 100,000 como el límite de la altura side1,2, hyp puede ir en 3.2 minutos (creo que el límite de 1,000,000 tarda una hora).

Modifiqué un poco el código y reduje el límite de 10.000 a 1 segundo (sin optimizaciones). Además de eso, con un pensamiento cuidadoso, el mío se puede dividir en trozos y enhebrar en rangos dados (por ejemplo, 100,000 se dividen en 4 trozos iguales para 3 cpu''s (1 extra para consumir tiempo de CPU por las dudas) con rangos de 1 a 25,000 (empiece en 1 y limítelo a 25,000), de 25,000 a 50,000, de 50,000 a 75,000 y de 75,000 hasta el final. Puedo hacer eso y ver si lo acelera (tendré hebras prefabricadas y no las incluiré en la cantidad real) de tiempo para ejecutar la función triple. Necesitaría un temporizador más preciso y una forma de concatenar los vectores. Creo que si 1 CPU de 3,4 GHZ con 8 GB de RAM está a su disposición puede hacer 10.000 como lim en 1 segundo, luego 3 CPU debería hacer eso en 1/3 por segundo (y redondeo a segundo más alto como es atm).

Answer 9

def pyth_triplets(n=1000):
    "Version 1"
    for x in xrange(1, n):
        x2= x*x # time saver
        for y in xrange(x+1, n): # y > x
            z2= x2 + y*y
            zs= int(z2**.5)
            if zs*zs == z2:
                yield x, y, zs

>>> print list(pyth_triplets(20))
[(3, 4, 5), (5, 12, 13), (6, 8, 10), (8, 15, 17), (9, 12, 15), (12, 16, 20)]

El algoritmo V.1 tiene monótonamente incrementando los valores de x .

EDITAR

Parece que esta pregunta todavía está viva :)
Desde que volví y revisé el código, probé un segundo enfoque que es casi 4 veces más rápido (alrededor del 26% del tiempo de CPU para N = 10000) como mi sugerencia anterior, ya que evita muchos cálculos innecesarios:

def pyth_triplets(n=1000):
    "Version 2"
    for z in xrange(5, n+1):
        z2= z*z # time saver
        x= x2= 1
        y= z - 1; y2= y*y
        while x < y:
            x2_y2= x2 + y2
            if x2_y2 == z2:
                yield x, y, z
                x+= 1; x2= x*x
                y-= 1; y2= y*y
            elif x2_y2 < z2:
                x+= 1; x2= x*x
            else:
                y-= 1; y2= y*y

>>> print list(pyth_triplets(20))
[(3, 4, 5), (6, 8, 10), (5, 12, 13), (9, 12, 15), (8, 15, 17), (12, 16, 20)]

Tenga en cuenta que este algoritmo tiene valores z crecientes.

Si el algoritmo se convirtió en C, donde, estando más cerca del metal, las multiplicaciones toman más tiempo que las adiciones, se pueden minimizar las multiplicaciones necesarias, dado el hecho de que el paso entre cuadrados consecutivos es:

(x + 1) ² - x² = (x + 1) (x + 1) - x² = x² + 2x + 1 - x² = 2x + 1

así que todo el interior x2= x*x y y2= y*y se convertiría en adiciones y restas como esta:

def pyth_triplets(n=1000):
    "Version 3"
    for z in xrange(5, n+1):
        z2= z*z # time saver
        x= x2= 1; xstep= 3
        y= z - 1; y2= y*y; ystep= 2*y - 1
        while x < y:
            x2_y2= x2 + y2
            if x2_y2 == z2:
                yield x, y, z
                x+= 1; x2+= xstep; xstep+= 2
                y-= 1; y2-= ystep; ystep-= 2
            elif x2_y2 < z2:
                x+= 1; x2+= xstep; xstep+= 2
            else:
                y-= 1; y2-= ystep; ystep-= 2

Por supuesto, en Python, el bytecode adicional producido realmente ralentiza el algoritmo en comparación con la versión 2, pero apostaría (sin verificar :) que V.3 es más rápido en C.

Saludos a todos :)

Answer 10

Debe tenerse en cuenta que para a, b y c no es necesario que recorra todo el camino hasta N.

Para a, solo tiene que pasar de 1 a int(sqrt(n**2/2))+1 , para b, a+1 a int(sqrt(n**2-a**2))+1 , y para c desde int(sqrt(a**2+b**2) a int(sqrt(a**2+b**2)+2 .

Answer 11

Juste extendí la respuesta de Kyle Gullion para que los triples se clasifiquen por hipotenusa, luego el lado más largo.

No usa numpy, pero requiere SortedCollection (u SortedList) como este

def primitive_triples():
""" generates primitive Pythagorean triplets x<y<z
sorted by hypotenuse z, then longest side y
through Berggren''s matrices and breadth first traversal of ternary tree
:see: https://en.wikipedia.org/wiki/Tree_of_primitive_Pythagorean_triples
"""
key=lambda x:(x[2],x[1])
triples=SortedCollection(key=key)
triples.insert([3,4,5])
A = [[ 1,-2, 2], [ 2,-1, 2], [ 2,-2, 3]]
B = [[ 1, 2, 2], [ 2, 1, 2], [ 2, 2, 3]]
C = [[-1, 2, 2], [-2, 1, 2], [-2, 2, 3]]

while triples:
    (a,b,c) = triples.pop(0)
    yield (a,b,c)

    # expand this triple to 3 new triples using Berggren''s matrices
    for X in [A,B,C]:
        triple=[sum(x*y for (x,y) in zip([a,b,c],X[i])) for i in range(3)]
        if triple[0]>triple[1]: # ensure x<y<z
            triple[0],triple[1]=triple[1],triple[0]
        triples.insert(triple)

def triples():
""" generates all Pythagorean triplets triplets x<y<z 
sorted by hypotenuse z, then longest side y
"""
prim=[] #list of primitive triples up to now
key=lambda x:(x[2],x[1])
samez=SortedCollection(key=key) # temp triplets with same z
buffer=SortedCollection(key=key) # temp for triplets with smaller z
for pt in primitive_triples():
    z=pt[2]
    if samez and z!=samez[0][2]: #flush samez
        while samez:
            yield samez.pop(0)
    samez.insert(pt)
    #build buffer of smaller multiples of the primitives already found
    for i,pm in enumerate(prim):
        p,m=pm[0:2]
        while True:
            mz=m*p[2]
            if mz < z:
                buffer.insert(tuple(m*x for x in p))
            elif mz == z: 
                # we need another buffer because next pt might have
                # the same z as the previous one, but a smaller y than
                # a multiple of a previous pt ...
                samez.insert(tuple(m*x for x in p))
            else:
                break
            m+=1
        prim[i][1]=m #update multiplier for next loops
    while buffer: #flush buffer
        yield buffer.pop(0)
    prim.append([pt,2]) #add primitive to the list

el código está disponible en el módulo math2 de mi biblioteca de Python . Está probado contra algunas series del OEIS (código aquí en la parte inferior), lo que me permitió encontrar un error en A121727 :-)

Answer 12

Pregunta anterior, pero aún así ingresaré mis cosas. Hay dos formas generales de generar triples pitagóricos únicos. Uno es por escala, y el otro es mediante el uso de esta fórmula arcaica.

Qué escala básicamente toma una n constante, entonces multiplica una base triple, digamos 3,4,5 por n. Entonces tomando n ser 2, obtenemos 6,8,10 nuestro próximo triple.

Escalada

def pythagoreanScaled(n):
    triplelist = []
    for x in range(n):
        one = 3*x
        two = 4*x
        three = 5*x
        triple = (one,two,three)
        triplelist.append(triple)
return triplelist

El método de fórmula usa el hecho de que si tomamos un número x, calculamos 2 m, m ^ 2 + 1 y m ^ 2-1, esos tres siempre serán un triplete pitagórico.

Fórmula

def pythagoreantriple(n):
    triplelist = []
    for x in range(2,n):
        double = x*2
        minus = x**2-1
        plus = x**2+1
        triple = (double,minus,plus)
        triplelist.append(triple)
    return triplelist

Answer 13

Sustancialmente más rápido que cualquiera de las soluciones hasta ahora. Encuentra trillizos a través de un árbol ternario.

Wolfram dice:

Hall (1970) y Roberts (1977) prueban que es un triple pitagórico primitivo si y solo si

(a,b,c)=(3,4,5)M

donde M es un producto finito de las matrices U, A, D.

Y ahí tenemos una fórmula para generar cada triple primitivo.

En la fórmula anterior, la hipotenusa es cada vez mayor, por lo que es bastante fácil verificar la duración máxima.

En Python:

import numpy as np

def gen_prim_pyth_trips(limit=None):
    u = np.mat('' 1  2  2; -2 -1 -2; 2 2 3'')
    a = np.mat('' 1  2  2;  2  1  2; 2 2 3'')
    d = np.mat(''-1 -2 -2;  2  1  2; 2 2 3'')
    uad = np.array([u, a, d])
    m = np.array([3, 4, 5])
    while m.size:
        m = m.reshape(-1, 3)
        if limit:
            m = m[m[:, 2] <= limit]
        yield from m
        m = np.dot(m, uad)

Si quieres todos los triples y no solo los primitivos:

def gen_all_pyth_trips(limit):
    for prim in gen_prim_pyth_trips(limit):
        i = prim
        for _ in range(limit//prim[2]):
            yield i
            i = i + prim

list(gen_prim_pyth_trips(10**4)) demoró 2,81 milisegundos para volver con 1593 elementos, mientras que list(gen_all_pyth_trips(10**4)) tardó 19,8 milisegundos en volver con 12471 elementos

Como referencia, la respuesta aceptada (en python) tomó 38 segundos para 12471 elementos.

Solo por diversión, establecer el límite superior en la list(gen_all_pyth_trips(10**6)) un millón list(gen_all_pyth_trips(10**6)) regresa en 2,66 segundos con elementos de 1980642 (casi 2 millones de triples en 3 segundos). list(gen_all_pyth_trips(10**7)) hace que mi computadora se list(gen_all_pyth_trips(10**7)) rodillas a medida que la lista se hace tan grande que consume hasta el último trozo de ram. Al hacer algo como sum(1 for _ in gen_all_pyth_trips(10**7)) supera esa limitación y regresa en 30 segundos con 23471475 elementos.

Para obtener más información sobre el algoritmo utilizado, consulte los artículos sobre Wolfram y Wikipedia .

Answer 14

from  math import sqrt
from itertools import combinations

#Pythagorean triplet - a^2 + b^2 = c^2 for (a,b) <= (1999,1999)
def gen_pyth(n):
if n >= 2000 :
  return
ELEM =   [  [ i,j,i*i + j*j ] for i , j in list(combinations(range(1, n +   1 ), 2)) if sqrt(i*i + j*j).is_integer() ]
print (*ELEM , sep = "/n")


gen_pyth(200)