quadrati e cubi, la congettura di Catalan generalizzata

Un post su Quora.com sulla relazione tra quadrati e cubi mi ha incuriosito: nella sequenza: 25, 26, 27, l’elemento centrale 26 separa un quadrato perfetto (25 = 52) da un cubo perfetto (27 = 33). Esistono altri esempi di relazione di questo tipo?
La questione si presta a una divertente esplorazione con poche righe di codice, alla ricerca di quadrati e cubi separati da 2 o più posizioni. Se si includessero nella ricerca anche potenze maggiori del cubo, il tutto si trasformerebbe nel tema della Congettura di Catalan generalizzata. Come si costruisce questo codice? Per partire basta un po’ di dimestichezza con Python
.


La congettura di Catalan

Nel 1844 il matematico franco-belga Eugène Charles Catalan congetturò che l’equazione: xa – yb = 1 ammettesse un’unica soluzione negli interi: 32 – 23 = 1. La congettura si rivelò poi vera nel 2002, grazie al matematico rumeno Preda Mihăilescu.
Con parole diverse, si può dire che l’unico caso di cubo seguito immediatamente da un quadrato sia il caso 8, 9.

Nel post su Quora, partendo dal caso simile: 25, 26, 27, ci si chiede se esistono altri casi di quadrati e cubi non contigui, ma separati da due posizioni.

Poche righe di Python

L’algoritmo più semplice che mi è venuto in mente consiste nel generare progressivamente i numeri al cubo e verificare l’eventuale presenza di un quadrato nelle vicinanze. Sia questo codice che quello descritto nel seguito sono scaricabili da qui.

max_n = 100000
for n in range(2,max_n+1):
    cubo = n*n*n
    for k in [-2, 2]:
        if cubo+k > 1:
            m = int((cubo + k)**0.5)
            if m * m == cubo + k:
                print (cubo, cubo+k)

Vengono cioè stampati i numeri cubocubo + 2cubo – 2, solo se uno di questi due è un quadrato perfetto.
Il programma è molto veloce. Esplorando i numeri da 2 a 100.000, si generano i cubi fino a 1.000.000.000.000.000. Il risultato però è laconico: l’unico caso trovato è proprio 27 (cubo), 25 (quadrato).

Una prima generalizzazione

Una piccola estensione al codice consente di esplorare il caso in cui quadrati e cubi siano separati da un numero di posizioni diverso da 2.

max_n = 100000
for k0 in range(1,21):
    n_casi = 0
    print ("quadrati e cubi separati da",k0,":")
    for n in range(2,max_n+1):
        cubo = n*n*n
        for k in [-k0, k0]:
            if cubo+k > 1:
                m = int((cubo + k)**0.5)
                if m * m == cubo + k:
                    print (f"{cubo:,}".replace(',','.'),",",f"{(cubo+k):,}".replace(',','.'))
                    n_casi += 1
    print ("n.ro di casi trovati:",n_casi)

Due sono le modifiche sostanziali:

  1. è stato inserito un ciclo esterno, per variare da 1 a 20 il numero di posizioni da considerare;
    • for k0 in range(1,21);
  2. la stampa dei due valori è stata arricchita del separatore delle migliaia, per maggiore leggibilità;
    • print (f”{cubo:,}”.replace(‘,’,’.’),”,”,f”{(cubo+k):,}”.replace(‘,’,’.’));
    • da notare la palla al piede del sistema anglosassone di separare le migliaia con la virgola, invece che con il punto, che costringe a una sostituzione di caratteri (.replace(‘,’,’.’)).

Il risultato si fa interessante. Ecco la stampa di alcuni dei valori trovati (ho omesso i casi in cui non sono stati trovati risultati, più altri casi intermedi):

8 , 9
n.ro di casi trovati: 1

quadrati e cubi separati da 2 :
27 , 25
n.ro di casi trovati: 1

...

quadrati e cubi separati da 4 :
8 , 4
125 , 121
n.ro di casi trovati: 2

...

quadrati e cubi separati da 8 :
8 , 16
97.336 , 97.344
n.ro di casi trovati: 2

quadrati e cubi separati da 9 :
27 , 36
216 , 225
64.000 , 64.009
n.ro di casi trovati: 3

...

quadrati e cubi separati da 17 :
8 , 25
64 , 81
512 , 529
79.507 , 79.524
140.608 , 140.625
143.384.152.904 , 143.384.152.921
n.ro di casi trovati: 6

...

Come si vede:

  • sono presenti i due casi già noti (8, 9 e 25, 27);
  • il primo caso di più di una soluzione si ha per una separazione pari a 4 (8, 4 e 125, 121);
  • il primo caso di ricchezza di soluzioni si ha per una separazione pari a 17, con ben 6 soluzioni diverse.

Un’estensione semplice ma inefficiente

La modifica apportata al codice è molto limitata (è stata dettata più che altro da pigrizia mentale), ma si dimostra decisamente inefficiente quando si estende il campo di ricerca a valori di separazione più ampi. Di fatto si ripete l’intero ciclo di generazione dei cubi per ciascun valore di separazione esaminato. Questa cattiva scalabilità dell’algoritmo limita il campo di esplorazione fattibile.

Un algoritmo  più efficiente consiste nel generare una sola volta i cubi e, per ciascun cubo, generare i valori di separazione di interesse.
Questa diversa struttura obbliga però a memorizzare i valori via via trovati, per poi raggruppare (e stampare) i casi relativi a ciascun valore di separazione. La memorizzazione avviene in un dizionario e il programma si divide in effetti in due parti:

  1. memorizzazione delle soluzioni;
  2. raggruppamento e stampa.

Questa la prima parte, che produce il dizionario lista:

lista = dict()
min_n = 2
max_n = 500000000
max_dist = 1000
for n in range(min_n,max_n+1):
    cubo = n*n*n
    if cubo > max_dist:
        m_min = int((cubo-max_dist)**0.5)
    else:
        m_min = 2
    m_max = int((cubo+max_dist)**0.5)+1
    for m in range(m_min,m_max):
        quadrato = m * m
        dist = cubo - quadrato
        if dist < 0: dist = -dist if (dist != 0) and not (dist > max_dist): 
            if dist not in lista:
                lista[dist] = [[cubo,quadrato]]
            else:
                lista[dist].append([cubo,quadrato])

E questa è la seconda parte, che raggruppa e stampa:

max_llista = 0
tot_coppie = 0
for i in sorted(lista):
    llista = len(lista[i])
    tot_coppie += llista
    if llista > max_llista:
        max_llista, mdist = llista,i
    if llista == 1:
        x = "coppia"
    else:
        x = "coppie"
    print (i,"-->",llista,x)
    for j in lista[i]:
        print ("\t",f"{j[0]:,}".replace(',','.'),",",f"{j[1]:,}".replace(',','.'))

Si noti la raffinatezza del distinguere quando si trova una sola coppia da quello in cui si trovano più coppie.

Il risultato dell’esplorazione estesa

L’ottimizzazione del codice permette di estendere il campo di ricerca, esplorando in pochi minuti i cubi fino a 125.000.000.000.000.000.000.000.000 e i valori di separazione fino a 1.000.

Si confermano le soluzioni trovate con l’algoritmo precedente, per i valori di separazione fino a 20, senza aggiungere nuove soluzioni.

Appena oltre il limite di 20 del programma precedente, si trova il primo risultato interessante:

24 --> 2 coppie
	 1.000 , 1.024
	 542.939.080.312 , 542.939.080.336

Il primo caso con più di 6 soluzioni si ha per un valore di separazione pari a 100:

100 --> 7 coppie
	 125 , 25
	 125 , 225
	 1.000 , 900
	 8.000 , 8.100
	 13.824 , 13.924
	 39.304 , 39.204
	 18.821.096.000 , 18.821.096.100

Interessante notare la sequenza quadrato – cubo – quadrato: 25, 125, 225.

E proprio 225 è il valore di separazione con più soluzioni, 10:

225 --> 10 coppie
	 64 , 289
	 216 , 441
	 1.000 , 1.225
	 3.375 , 3.600
	 27.000 , 27.225
	 216.000 , 216.225
	 5.832.000 , 5.832.225
	 37.933.056 , 37.933.281
	 43.243.551 , 43.243.776
	 373.425.320.872.841.544 , 373.425.320.872.841.769

La congettura di Catalan generalizzata considera non solo quadrati e cubi, ma qualunque potenza. L’algoritmo di esplorazione diventa decisamente più complesso e, naturalmente, il numero di casi trovati aumenta.
Un riscontro si trova confrontando i risultati dell’algoritmo descritto in questo articolo con quelli riportati dalla voce di Wikipedia relativa alla congettura.
Il primo caso di soluzione che coinvolge una potenza diversa da quadrato e cubo è relativa al valore di separazione 3: 125 e 128, rispettivamente pari a 53 e 27.
Dalla generalizzazione della congettura di Catalan esce arricchito anche il caso relativo al valore di separazione pari a 17, grazie a un’addizionale soluzione, con la coppia 32 e 49, uguali, rispettivamente, a 25 e 72.

Immagine di apertura di tigerlily713 da Pixabay.

Scritto da:

Pasquale

Mi chiamo Pasquale Petrosino, radici campane, da alcuni anni sulle rive del lago di Lecco, dopo aver lungamente vissuto a Ivrea.
Ho attraversato 40 anni di tecnologia informatica, da quando progettavo hardware maneggiando i primi microprocessori, la memoria si misurava in kByte, e Ethernet era una novità fresca fresca, fino alla comparsa ed esplosione di Internet.
Tre passioni: la Tecnologia, la Matematica per diletto e le mie tre donne: la piccola Luna, Orsella e Valentina.
Potete contattarmi scrivendo a: p.petrosino@inchiostrovirtuale.it