Generazione di terne pitagoriche

1

Cristiano Teodoro

cristianoteodoro@virgilio.it

Generazione di terne pitagoriche primitive particolari

(Generation of particular Pithagorean Primitive Triples)

Sommario

Nel presente articolo viene proposto ed illustrato un nuovo algoritmo per il calcolo e la generazione di terne pitagoriche primitive aventi cateti la cui differenza è pari ad un qualsiasi valore N scelto in un definito campo di valori numerici, ad esempio tra 1 e 10¹².

Per avere dei risultati concreti con l’utilizzo di tale algoritmo, si sono realizzati due programmi scritti in linguaggio Qbasic.

Il primo programma (Allegato 1) è dedicato per un dato N alla generazione, se esistono, delle relative terne primitive. Con questo programma viene calcolato e generato per il considerato valore di N un limitato numero di terne, precisamente quelle che si possono calcolare in modo esatto sino alla cifra delle unità.

Poiché nelle operazioni aritmetiche viene utilizzata la sola doppia precisione le terne generate e presentate sono solo quelle che hanno i valori dei cateti e dell’ipotenusa composti ciascuno da non più di 15 cifre.

Il secondo programma (Allegato 2) è dedicato alla generazione di terne con cateti e ipotenusa di valore elevato in quanto le operazioni aritmetiche vengono eseguite con una adeguata aritmetica a precisione multipla anche qui con l’introduzione di un N qualsiasi scelto entro il campo 1 ÷ 10¹² di possibili suoi valori.

Eseguendo questo programma si scopre innanzitutto se per il valore scelto N esistono terne primitive o meno: se non esistono si termina il programma; se invece esistono si vanno a calcolare i valori anche molto grandi dell’ipotenusa e dei cateti relativi alla ennesima terna primitiva prescelta, ad esempio la 10000ª terna, prendendo in considerazione per l’ordine delle terne il valore crescente della ipotenusa.

Un pregio dell’algoritmo è senz’altro quello della rapidità di tempo con cui si possono avere i risultati di terne aventi i valori numerici dei cateti e dell’ipotenusa costituiti anche da migliaia di cifre.

Abstract

In this paper we propose and explain an new algorithm for the particular pithagorean primitive triples computation and generation. These triples have the N value as difference between the legs. This gap can have any value between 1 and 10¹². We obtain actual results by the implementation of two programs in Qbasic language.

The former (Allegato 1) considers the generation of possible primitive triples pertinent to requested N and compute and produce only the restricted number of primitive triples, calculated exactly until the least significant digit.

Indeed in this program we use only the double-precision arithmetic and we have exact results for triples with hypotenuse and leg, that have numerical values with a digit number ≤ 15.

The second program (Allegato 2) is pertinent to computation and generation of triples with the legs and the hypotenuse having as well big values, because we employ a multiple-precision arithmetic.

In this program, introducing any chosen N value in the range 1 ÷ 10¹² we find if for this N there are primitive triples or not.

If so we compute the big numerical values of hypotenuse and legs relative to the nth selected triple, for example the ten thousandth triple, considering for the triples serial number the increasing hypotenuse value.

The merit of this algorithm is the time rapidity for the numerical values achievement.

1 - Introduzione

In articoli comparsi recentemente su questo Sito [Fi]; [Dm] si è parlato di terne pitagoriche, del problema di trovare terne particolari e di calcolare con metodi efficienti i triangoli rettangoli aventi cateti la cui lunghezza è data da numeri interi consecutivi.

Qui ci occuperemo di un problema analogo, ma più generale rivolto sempre a considerare terne particolari ed al calcolo dei loro valori numerici.

Le terne che prenderemo in considerazione saranno quelle che possiedono insieme le tre seguenti caratteristiche:

• Terne con l’ipotenusa e cateti costituiti da numeri interi.
• Terne per le quali la differenza fra i valori numerici dei due cateti è un valore numerico prefissato N, da poter scegliere fra un qualsiasi valore nel campo 1 ≤ N ≤ Nm con Nm ad esempio pari a 10¹².
• Terne denominate primitive, cioè quelle con cateti ed ipotenusa non aventi fattori comuni, cioè primi fra loro.

Prima di passare a calcolare ed a trovare i valori numerici esatti, anche elevati, dei cateti e della ipotenusa, risulta necessario individuare per quali valori di N esistono terne con i requisiti richiesti.

In Tabella 1 si riportano ad esempio nel campo esplorato da 1 a 100 i valori di N solo in corrispondenza dei quali esistono terne primitive; in essa sono anche mostrati per ciascun N i valori avente i valori numerici più piccoli della ipotenusa e dei cateti riguardanti la terna primitiva.

Tabella 1

Con l’algoritmo che si va a proporre la ricerca della esistenza di tale tipo di terna primitiva può effettuarsi in un tempo molto contenuto per un qualsiasi N anche elevato entro il campo di esplorazione menzionato in 2).

In Tabella 2 si riportano alcuni altri esempi di valori N scelti nel campo 1 ÷ 10¹² per ciascuno dei quali esistono terne primitive; per ciascun N i valori riportati della ipotenusa e dei cateti sono relativi alla prima terna primitiva, quella cioè avente l’ipotenusa più piccola.

Tabella 2

Si può facilmente verificare che i valori numerici dell’ipotenusa e dei cateti posti sulla stessa riga non hanno fra loro fattori in comune, sono cioè coprimi, come infatti deve essere. Pertanto ogni terna riportata in tabella è di tipo primitivo.

2 - Illustrazione dell’algoritmo

2.1 Formule di Euclide e equazioni diofantee

Illustriamo ora l’algoritmo partendo dalle seguenti formule relative all’ipotenusa ed ai cateti di un triangolo rettangolo, formule già note dall’antica Grecia (Euclide, Diofanto) [Be], [Da], [CR], [H.W.]:

Cateto 1: C1 = 2mn; cateto 2: C2 = m² − n²; ipotenusa: A = m² + n²

Dove m e n sono numeri interi positivi.

Per le terne pitagoriche che vogliamo considerare, vale a dire per quelle terne che hanno i cateti che differiscono di un valore N cioè N = │C1 − C2│ od anche C1 − C2 = ±N si ha:

2mn − (m² − n²) = ±N equivalente a m² + 2mn − 2n² = ±N

Che è conveniente scrivere come segue: (m − n)² − 2n² = ±N

Posto x = m − n ed y = n risulta la seguente relazione:

x² − 2y² = ±N

Che rappresenta le due equazioni quadratiche indeterminate:

x² − 2y² = N (1)

x² − 2y² = −N (2)

Per ognuna di esse occorrerà trovare per le incognite x e y i valori numerici interi minimi che la soddisfano.

Una volta trovati tali valori, essendo m = x + y e n = y si potrà risalire ai valori dei cateti C1, C2 e della ipotenusa A tramite le formule sopra dette:

C1 = 2(x + y)y; C2 = (x + y)² − y²; A = (x + y)² + y²

x² − 2y² = N

2.2 Considerazioni sull’equazione x² − 2y² = N

Per trovare i più piccoli valori per x ed y che soddisfano l’equazione x² − 2y² = N, dato che il coefficiente di y² è piccolo ed il valore di N da prendere in considerazione è relativamente piccolo (massimo valore di N preso in esame Nm = 10¹²) si può fare ricorso alla ricerca esaustiva (brute-force search) dei suddetti valori impiegando anche così un tempo di calcolo breve.

In quanto, indicati con x₁ e y₁ rispettivamente il più piccolo valore positivo per x ed il più piccolo valore positivo per y che soddisfano l’equazione (1), essi devono trovarsi se esistono nel seguente campo limitato di interi [Fr], [Na], [Ro]:

Per x: 1 < x₁ < 2N

Per y: 1 < y₁ < N/2

Se entro i campi suddetti non si trovasse nessun valore di x o di y tali da soddisfare l’equazione (1) si può concludere che essa non è risolvibile.

Si noti che la ricerca di y₁ anche per valori di N dell’ordine di 10¹² è ristretta ad un valore non superiore a 707106.

Ad esempio per N = 10⁷ + 7 i valori di x₁ e y₁ che soddisfano la (1) sono i seguenti:

x₁ = 1014955

y₁ = 122747

Come si può facilmente verificare. Il tempo di calcolo per trovare tali valori risulta al massimo di qualche decimo di secondo (vedi più sotto Esempio 1) anche con l’utilizzo di un microprocessore non particolarmente sofisticato.

Se tuttavia si prende in considerazione un valore N per il quale non esistono terne primitive occorrerà esplorare per y tutto il suddetto campo: ad esempio per N = 10¹² + 3 si dovrà andare a saggiare y fino al valore 707106 con un tempo al massimo di qualche decimo di secondo (< 0.8 secondi) col normale computer commerciale utilizzato nei programmi sotto riportati.

Una volta trovati x₁ e y₁ per calcolare i successivi valori di x e y che soddisfano la (1) in modo da rendere molto veloce il loro calcolo si possono utilizzare le seguenti originali formule iterative:

x_k = x_k−1 + 2 · y_k−1 (3)

y_k = x_k−1 + y_k−1 (4)

Con k = 2, 3, 4 ……… e dove i valori iniziali x₁ e y₁ sono gli interi positivi più piccoli, trovati con la ricerca esaustiva che soddisfano la (1).

Non è infatti difficile dimostrare per induzione quanto segue:

a) Oltre i valori iniziali x₁ e y₁, i valori x_k e y_k trovati con le formule suddette relativi agli indici dispari di k, cioè i valori x₃, x₅, x₇, … ed i corrispondenti valori y₃, y₅, y₇, ….. sono valori che soddisfano l’equazione x² − 2y² = N (1).

b) I valori di x e y trovati con le formule suddette relativi agli indici pari di k, cioè x₂, x₄, x₆, ......... ed i corrispondenti y₂, y₄, y₆,..... sono valori che soddisfano l’equazione x² − 2y² = −N.

2.3 Considerazioni sull’equazione x² − 2y² = −N

Analogamente per l’equazione x² − 2y² = −N tramite sempre una ricerca esaustiva i più piccoli interi positivi x₁ e y₁ che soddisfano l’equazione, se esistono, devono trovarsi nel seguente campo di valori [Fr], [Na], [Ro]:

Per x: 1 < x₁ < NA

Per y: 1 < y₁ < NA/2

Dove NA = |−N|

Essendo il campo di ricerca anche qui abbastanza limitato si possono rapidamente trovare tali valori (vedi Esempio 1).

Prendendo in considerazione sempre le formule iterative (3) e (4) e considerando i valori positivi più piccoli di x e di y soddisfacenti la (2) quali valori iniziali x₁ e y₁ risulta anche qui che:

a1) Oltre i valori iniziali x₁ e y₁, i valori x_k e y_k trovati con le formule suddette relativi agli indici dispari di k, cioè i valori x₃, x₅, x₇, … ed i corrispondenti valori y₃, y₅, y₇,..... sono valori che soddisfano la x² − 2y² = −N.

b1) I valori x e y trovati con le formule suddette relativi agli indici pari di k, cioè x₂, x₄, x₆, ......... ed i corrispondenti y₂, y₄, y₆,..... sono valori che soddisfano l’equazione x² − 2y² = N.

2.4 Calcolo delle terne pitagoriche primitive

Tenendo ora presente le formule di Euclide e che m = x + y ed n = y si possono innanzitutto trovare i valori dei cateti e dell’ipotenusa della terna pitagorica più piccola che presenta le caratteristiche 1) e 2) sopra enunciate:

C₁ = 2(x₁ + y₁)y₁

C₂ = (x₁ + y₁)² − y₁²

A = (x₁ + y₁)² + y₁²

Per controllare inoltre se la terna risulta avere anche caratteristica 3), cioè se essa è primitiva, occorre verificare che i valori x₁ + y₁ e y₁ siano fra loro primi e non entrambi dispari [C.R] [Sh].

Poiché conosciamo, per quanto illustrato sopra, i successivi valori x_k e y_k soddisfacenti l’equazione, potremo ricavare con l’utilizzo delle formule iterative (3) e (4) tutte le altre terne pitagoriche anch’esse, come è facile dimostrare, tutte primitive, eseguendo i seguenti due cicli di istruzioni scritti qui in linguaggio QBasic:

1° ciclo, relativo alla equazione x² − 2y² = N con x = x₁ e y = y₁ quali valori interi positivi più piccoli soddisfacenti tale equazione:

x = x1 : y = y1

FOR h = 2 to n

xo = x

x = x + 2 · y

y = xo + y

m = x + y : n = y

A = m ^ 2 + n ^ 2

C1 = 2 * m * n :

C2 = m ^ 2 - n ^ 2

PRINT k ; x, y, A ; C1 ; C2

NEXT k

2° ciclo, relativo alla equazione x² − 2y² = −N con x = x₁ e y = y₁ quali valori interi positivi più piccoli soddisfacenti tale equazione:

x = x1 : y = y1

FOR h = 2 to n

xo = x

x = x + 2 · y

y = xo + y

m = x + y : n = y

A = m ^ 2 + n ^ 2

C1 = 2 * m * n :

C2 = m ^ 2 - n ^ 2

PRINT k ; x, y, A ; C1 ; C2

NEXT k

Si vuol mettere in evidenza che è necessario effettuare la ricerca dei valori di m e di n e quindi dei valori della ipotenusa e dei cateti sia per il valore +N che per il valore −N, in quanto, ad eccezione di N = ±1, si ottengono differenti valori nell’uno e nell’altro caso (vedasi per chiarire quanto detto relativo a N = ±47) i risultati riportati nell’Esempio 3.

Per N = ±1 risulta però sufficiente effettuare la ricerca solo per il valore N = 1.

Può anche risultare che per il valore positivo di N esistono terne primitive mentre per il valore negativo di N non esistono terne primitive o viceversa.

Ad esempio per N = 343 esistono terne primitive mentre per N = −343 non esistono. Viceversa per N = 3577 non ci sono terne primitive mentre per N = −3577 esistono terne primitive.

Per avere dei risultati concreti si sono sviluppati due programmi in linguaggio Qbasic che presentano le prestazioni desiderate.

Con il 1° programma (Allegato 1), dove ci si limita ad utilizzare la aritmetica a doppia precisione offerta dal software del QBASIC, introducendo un N qualsiasi (N = differenza di valore fra i due cateti) entro il campo 1 ÷ 10¹² di suoi possibili valori ed eseguendo il programma, si scopre innanzitutto se le terne relative a tale N sono primitive o meno: se non sono primitive si termina il programma.

Se invece esistono terne primitive si trova un limitato numero di terne primitive relative sia al valore +N che al valore −N, partendo a presentare per ognuna delle due serie di terne i risultati numerici dalla terna avente l’ipotenusa di più piccolo valore.

In effetti ci si limita a trovare ed a mostrare solo quelle terne che presentano valori numerici esatti sino alla cifra delle unità in quanto con l’uso della l’aritmetica a doppia precisione si ottengono nei calcoli risultati esatti solo se essi sono costituiti da non più di 15 cifre.

Si riporta qui di seguito qualche esempio di quello che compare sullo schermo del monitor eseguendo il programma.

Esempio 1

Quale differenza N vuoi fra i due cateti? 889701311

Le terne relative a 889701311 sono primitive.

Valori iniziali: x = 31231 y = 6545

1 1469863201 494487840 1384189151

2 8166943585 6202592544 5312891233

3 47531798309 33162262180 34051963491