Pagina 1 di 2

42 & C. come somma di 3 cubi di interi

Inviato: mer mag 08, 2019 11:00 am
da Gianfranco
Pasquale ha scritto qui (un-addizione-carina-t8106-15.html#p24712):
Intendevo dire qualcosa del genere :mrgreen: :twisted: :
Per chi ama "programmare" con i numeri interi, propongo di cimentarsi con uno di questi problemi ancora non risolti:

\large x^3+y^3+z^3 = k

con:
  • k = 42, 114, 165, 390, 579, 627, 633, 732, 795, 906, 921, 975;
  • x, y, z, numeri interi (positivi e negativi).

Re: 42 & C. come somma di 3 cubi di interi

Inviato: sab mag 11, 2019 3:41 pm
da Gianfranco
Per cominciare, posto il più semplice programmino che si possa scrivere (credo) per cercare le soluzioni.
E' impostato per k=18.

Codice: Seleziona tutto

'Trova le soluzioni intere di x^3+y^3+z^3=k
'nell'intervallo -10^n <= x, y, z <= 10^n

OPTION ARITHMETIC DECIMAL_HIGH
LET n=2
LET x1=-10^n
LET x2=10^n
LET y1=-10^n
LET y2=10^n
LET z1=-10^n
LET z2=10^n
k=18

FOR x=x1 TO x2
   FOR y=y1 TO y2
      FOR z=z1 TO z2
       
         IF x^3+y^3+z^3=k THEN
            PRINT x;y;z
            GOTO 100
         END if
          
      NEXT z
   NEXT y
NEXT x

100 PRINT "Finito"
     
 END
Per esaminare tutti i casi possibili (con ridondanze varie), deve eseguire il blocco dei cicli FOR per (2 \cdot 10^n)^3 volte.
Se n=30, deve eseguire il blocco circa 10^91 volte.
Se lo eseguisse 1000 volte al secondo, impiegerebbe circa 2.5*10^80 anni, pari a circa 1.6*10^70 volte l'età dell'Universo.
Anche un Buddha impallidisce di fronte a questo numero.
Proposte per velocizzare l'algoritmo?

Re: 42 & C. come somma di 3 cubi di interi

Inviato: dom mag 12, 2019 5:21 pm
da franco
Qualcosa si può fare ipotizzando, senza perdere di generalità che x, y e z siano in ordine (non strettamente) crescente

Codice: Seleziona tutto

'Trova le soluzioni intere di x^3+y^3+z^3=k
'nell'intervallo -10^n <= x, y, z <= 10^n

OPTION ARITHMETIC DECIMAL_HIGH
LET n=2
LET x1=-10^n
LET x2=10^n
LET y2=10^n
LET z2=10^n
k=18

FOR x=x1 TO x2
   FOR y=x TO y2
      FOR z=y TO z2
       
         IF x^3+y^3+z^3=k THEN
            PRINT x;y;z
            GOTO 100
         END if
          
      NEXT z
   NEXT y
NEXT x

100 PRINT "Finito"
     
 END
Mi pare che le iterazioni si riducano a poco più di 1/4 eliminando le ridondanze.
Siamo però ancora lunghi ...

Re: 42 & C. come somma di 3 cubi di interi

Inviato: mer mag 15, 2019 1:41 am
da Pasquale
Ho l'impressione che, con riferimento al testo del quesito ed in particolare ai valori di k elencati, sarà difficile trovare qualche soluzione.
A parte l'impossibile tempo occorrente per l'esecuzione della routine proposta e quindi scartata, ammettendo pure che disponessimo di un superfantastico computer in grado di ridurre iperbolicamente l'attesa di una risposta, resta il fatto che non è dato sapere quanto ampio dovrebbe essere l'intervallo entro cui eseguire la routine, specie se si fa riferimento ai particolari valori di k elencati nel testo del quesito, che sembrano scelti appositamente per rendere più difficile la soluzione del quesito con metodi elementari. Penso che necessiti studiare una strategia diversa e che sarà una bella sfida.
Dunque, qualche osservazione:

i valori assegnati alle variabili x,y,z, giostrando con valori positivi e negativi con routine di vario genere, non conducono a nessuno dei valori di k elencati fra 42 e 975 nell’ambito di ridotti intervalli possibili da trattare. Si è costretti ad ampliare sempre più l'intervallo di ricerca, finendo così nel vicolo cieco già descritto da Gianfranco.
Con valori di k leggermente diversi, individuati a titolo di studio e sperimentazione, si fa invece relativamente presto a raggiungere dei risultati, come ad esempio con:

k = 46,118,169,396,575,623,631,736,791,902,925,973

valori che ho individuato come possibili da trattare nell'ambito di un ridotto intervallo di ricerca, individuato per non rimanere del tutto a bocca asciutta.

Per velocizzare ho seguito i seguenti criteri:

ho separato in due diverse routine la ricerca dei k pari da quella dei k dispari ed in particolare ho considerato che
in riferimento a:

x^3+y^3+z^3 = k

per ottenere un k dispari, è necessario sommare 3 numeri dispari, o 1 dispari e 2 pari: D+D+D o D+P+P (a parte i segni da attribuire a ciascuno).
Si osserva che esclusa la somma di bassi valori dispari di x,y,z, che non è uguale a nessuno dei nuovi valori cercati, ben presto (D+D+D) > 973, per cui le soluzioni vanno individuate, a parte simmetrie e ridondanze, fra: D+D-D e/o D-D-D, non essendo ovviamente possibile che tutti abbiano lo stesso segno.
Una routine per tale ricerca in un intervallo breve accettabile non ha dato risultati, per cui la ometto.
Resta quindi da esaminare il caso DPP, che ho tradotto nella seguente routine:


!Ricerca k dispari = 169,575,623,631,791,925,973

!Una volta stufi di annotare i risultati,
!stoppare la routine, oppure iniziare la routine
!dalla riga 10 ed eliminare il loop finale, attribuento ad “a”
!almeno un valore di 1004, che tende a crescere ad ogni ciclo del DO-LOOP
!e rappresenta un modo diverso, anche se non esaustivo, d'impostazione
!della routine (scritta in Decimal Basic).
!I valori di x,y,z che appaiono tutti positivi nella finestra
!di esecuzione,vanno intesi col giusto segno, facendo riferimento
!alle righe d'impostazione di k1,k2,k3 e k4, che nel loro insieme rappresentano il k.

LET a=1003

DO

LET a=a+1

10 FOR x=1 TO a STEP 2 !dispari
FOR y=0 TO a STEP 2 !pari
FOR z=0 TO a STEP 2 !pari

LET k1=x^3+y^3-z^3
LET k2=-x^3+y^3+z^3
LET k3=x^3-y^3-z^3
LET k4=-x^3-y^3+z^3

SELECT CASE k1
CASE 169,575,623,631,791,925,973
PRINT "per a =";a;"e x,y,z =";x;y;z;": k1 =";k1
CASE ELSE
END SELECT


SELECT CASE k26,118
CASE 169,575,623,631,791,925,97373
PRINT "per a =";a;"e x,y,z =";x;y;z;": k2 =";k2
CASE ELSE
END SELECT


SELECT CASE k3
CASE 169,575,623,631,791,925,973
PRINT "per a =";a;"e x,y,z =";x;y;z;": k3 =";k3
CASE ELSE
END SELECT


SELECT CASE k4
CASE 169,575,623,631,791,925,973
PRINT "per a =";a;"e x,y,z =";x;y;z;": k4 =";k4
CASE ELSE
END SELECT

NEXT Z
NEXT Y
NEXT X

LOOP
END


Vi faccio grazia della routine di ricerca dei valori pari di k = 46,118,396,736,902 , similare alla precedente, con la differenza che si va alla ricerca di x,y,z del tipo PDD, unica con soluzioni nell’ambito dello stesso precedente intervallo ristretto:

OMISSIS

FOR x=0 TO a STEP 2
FOR y=1 TO a STEP 2
FOR z=1 TO a STEP 2

LET k1=x^3+y^3-z^3
LET k2=-x^3+y^3+z^3
LET k3=x^3-y^3-z^3
LET k4=-x^3-y^3+z^3
ecc.

La particolare impostazione mi ha consentito il salto STEP 2 e forse un po’ di tempo l’ho risparmiato, ma poi c’è da considerare la velocità del processore e quant’altro.

In riferimento al testo originale ed ai valori di k ivi indicati, resta da vedere se è possibile un approccio diverso, circa il quale avrei un barlume di idea da verificare nella sua validità ed eventuale praticabilità.

Scusate la lungaggine, ma spesso considero la possibilità che qualche giovane studente o appassionato possa magari gradirla, ove interessato allla tipologia di studio ed a parte il rischio non infrequente di errori, inesattezze e/o incompletezze. :oops:

Re: 42 & C. come somma di 3 cubi di interi

Inviato: mer mag 15, 2019 9:18 am
da Bruno
Pasquale :D ho letto il tuo avvincente post come fosse un romanzo, quasi tra Maigret e Miss Marple :wink:

Re: 42 & C. come somma di 3 cubi di interi

Inviato: mer mag 15, 2019 9:57 am
da franco
L'argomento è intrigante ...
butto giù qualche ulteriore considerazione.

Mantenendo l'impostazione che ho considerato nel mio intervento precedente ( $x ≤ y ≤ z$ ) posso fermare le iterazioni quando $x^3 > k$ e quando $x^3+y^3 > k$

Inoltre, anzichè fare iterzioni su $z$ posso semplicemente verificare se la radice cubica di $k - x^3+y^3$ è un intero (nel qual caso ho trovato la soluzione) o no.

Re: 42 & C. come somma di 3 cubi di interi

Inviato: mer mag 15, 2019 6:15 pm
da franco
Ho fatto una simulazione con $k=18 $ e $n=2
$

lasciamo perdere l'idea di provare tutte le combinazioni (sarebbero 8.000.000)
con il programmino non ottimizzato, interrompendolo appena trova la prima soluzione valida, la soluzione arriva dopo 3.979.301 iterazioni
con la prima proposta che avevo fatto la soluzione arriva dopo 1.186.349 iterazioni
calcolando direttamente $z$ e verificando se è intero arrivo alla soluzione con sole 10.194 iterazioni

il programma che ho scritto è questo (per Visual Basic di Excel):

Codice: Seleziona tutto

Sub TRE()

    k = Cells(1, 2)
    n = Cells(2, 2)
    
    Xmin = -10 ^ n
    Xmax = Int(k ^ (1 / 3))
    iterazioni = 0
    
    For X = Xmin To Xmax
        Ymax = Int((k - X ^ 3) ^ (1 / 3))
        For Y = X To Ymax
            iterazioni = iterazioni + 1
            Z = (k - X ^ 3 - Y ^ 3) ^ (1 / 3)
            Zint = Int(Z)
            If Zint = Z Then
                Cells(4, 2) = X
                Cells(5, 2) = Y
                Cells(6, 2) = Z
                X = Xmax
                Y = Ymax
            End If
        Next
    Next
    Cells(8, 2) = iterazioni

End Sub
Sempre tanta roba se ci tocca lavorare con valori di n alti, però è già un bel passo avanti.

ciao

Franco

Re: 42 & C. come somma di 3 cubi di interi

Inviato: mer mag 15, 2019 7:06 pm
da franco
Ulteriore ottimizzazione (che con $k=18 $ funziona alla grande)

Codice: Seleziona tutto

Sub QUATTRO()

    k = Cells(1, 2)
    Nmax = Cells(2, 2)
    For N = 1 To Nmax
        Xmin = -10 ^ N
        Xmax = Int(k ^ (1 / 3))
        iterazioni = 0
        
        For X = Xmin To Xmax
            Ymax = Int((k - X ^ 3) ^ (1 / 3))
            For Y = X To Ymax
                iterazioni = iterazioni + 1
                Z = (k - X ^ 3 - Y ^ 3) ^ (1 / 3)
                Zint = Int(Z)
                If Zint = Z Then
                    Cells(4, 2) = X
                    Cells(5, 2) = Y
                    Cells(6, 2) = Z
                    Cells(3, 2) = N
                    X = Xmax
                    Y = Ymax
                    N = Nmax
                End If
            Next
        Next
    Next
    Cells(8, 2) = iterazioni

End Sub
Sono bastate 114 iterazioni!!!

edit
c'è un errore; l'istruzione della riga 6 (iterazioni=0) deve essere messa prima del ciclo FOR-NEXT
nel caso specifico con K=18 non cambia nulla perchè la soluzione si trova già nel primo ciclo ...

42 & C. come somma di 3 cubi di interi ???

Inviato: gio mag 16, 2019 6:48 am
da panurgo
Ciao cari ed ottimi, vi suggerisco la lettura di questo...

Baci
:wink:

Re: 42 & C. come somma di 3 cubi di interi

Inviato: gio mag 16, 2019 11:11 am
da franco
Interessantissima lettura.

Sostanzialmente sta a dirci che è inutile far girare le rotelle dei nosti miseri PC per cercare tre cubi che sommino 42 & Co :)

Re: 42 & C. come somma di 3 cubi di interi

Inviato: gio mag 16, 2019 5:24 pm
da panurgo
Non so se hai notato i numeri che servono per le somme che si sanno esistere...

Re: 42 & C. come somma di 3 cubi di interi

Inviato: gio mag 16, 2019 9:07 pm
da franco
Non credo abbiano usato dei semplici loop FOR-NEXT per trovare gli addendi del 33!

Re: 42 & C. come somma di 3 cubi di interi

Inviato: ven mag 17, 2019 10:57 am
da Info
ahahaha basta un n! = n * (n-1)!

Re: 42 & C. come somma di 3 cubi di interi

Inviato: ven mag 17, 2019 10:33 pm
da Gianfranco
Cari Franco, Pasquale e Panurgo, vi ringrazio per i programmi e le spiegazioni che avete scritto.
Molto interessante ed emozionante la strategia di Pasquale. Ricordo, tra l'altro il numero 153 che è uguale alla somma dei cubi delle sue cifre, tutti positivi.
153=5^3+3^3+1^3.
Un particolare ringraziamento a Franco che mi ha fatto capire quanto è utile e facile usare il Visual Basic di Excel.
Grazie a Panurgo per la traccia di Wolfram.
Seguendo la traccia ho trovato questa pagina dove sono elencate tutte le soluzioni trovate da Andreas-Stephan Elsenhans e Joerg Jahnel nel 2007:
(https://www.uni-math.gwdg.de/jahnel/Arb ... 070419.txt)
In ogni soluzione dell'equazione:
x^3 + y^3 + z^3 = k
i valori di x, y, z sono scritti in ordine decrescente.
---
Non sono riportati i casi in cui k è un cubo o il doppio di un cubo perché:
a^3+0+0=a^3
a^3+a^3+0=2a^3
Si poteva evitare di riportare anche i casi in cui k è il triplo di un cubo.
---
Ragionando sulle soluzioni, ho notato due proprietà statistiche che possono aiutarci a limitare la ricerca:
a) il rapporto tra z e x è vicino a -1, e varia tra -0,9 e -1,2 nei casi che ho considerato.
b) mcd(x, y, z) = 1 (quasi sempre)


Ecco il programmino che calcola i rapporti per alcuni numeri.
---
DATA 6, 65, -43, -58
DATA 7, 104, 32, -105
DATA 12, 9730705, -5725013, -9019406
DATA 30, 2220422932, -283059965, -2218888517
DATA 33, 8866128975287528, -2736111468807040, -8778405442862239
DATA 39, 134476, 117367, -159380
DATA 51, 659, 602, -796
DATA 75, 435203083, 4381159, -435203231
DATA 84, 40500964, 22894759, -42805979
DATA 87, 4271, -1972, -4126
DATA 108, 1345, -948, -1165
DATA 110, 16540290030, 109938919, -16540291649
DATA 111, 892, -296, -881
DATA 143, 84942, 7023, -84958
DATA 156, 68844645625, 2232194323, -68845427846
DATA 172, 17044, 15161, -20357
DATA 173, 31629, -14543, -30569
DATA 180, 441721, 223403, -460002
DATA 195, 5227922915, -2238006277, -5087472163
DATA 213, 1646, -859, -1564
DATA 227, 51748, 24579, -53534
DATA 228, 3877, -1577, -3788
DATA 231, 737660, -344065, -711814
DATA 236, 565, -417, -476
DATA 237, 6871, 1585, -6899
DATA 264, 1279, 430, -1295
DATA 268, 5667, 5138, -6823
DATA 273, 4009, 364, -4010
DATA 276, 15131, 2396, -15151
DATA 285, 1064, -352, -1051
DATA 290, 2070897315, 426417007, -2076906362
DATA 291, 32059, -10103, -31721

RESTORE

FOR i=1 TO 32
READ k, x, y, z
PRINT k;INT(z/x * 10000)/10000
NEXT i

END
---

Re: 42 & C. come somma di 3 cubi di interi

Inviato: dom mag 19, 2019 2:35 am
da Pasquale
Salve ragazzi, ero sul punto di postare un'ultima considerazione, quando il vecchio PC mi ha abbandonato. Oggi sono riuscito, come in questo momento, a riaffacciarmi sul forum, ma la faccenda resta precaria e staremo a vedere. Intanto ho potuto leggere gli ultimi sviluppi sull'argomento.

Ad ogni modo, circa la prospettata impossibilità di esitenza di particolari k (che sospettavo fossero tutti quelli in elenco, appositamente scelti dall'autore, non a caso), volevo dire che forse occorreva cambiare l'obiettivo del quesito: dimostrare che tutti i k = 42, ......ecc. possono o non possono essere soluzioni dell'equazione X^3 + y^3 + z^3 = k, abbandonando lo studio a mezzo delle routine, se possibile.

D'altra parte, avevo notato ad esempio che se k = 42 fosse stata una soluzione, avrebbe dovuto essere vero che:

x^2 = \frac{42- (y^3 + z^3)}{x} , ove 42 sommato alla somma algebrica di due cubi avrebbe dovuto essere a sua volta un cubo (cioè x^3)

oppure che :

x =  \frac{42- (y^3 + z^3)}{x^2}, ove la somma algebrica di due cubi e 42 avrebbe dovuto essere un quadrato (cioè x^2)


Queste due realtà per altri k sono verificabili in base ai diversi valori che possono essere attribuiti alle tre variabili, ma bisogna che siano valori relativamente bassi, perché man mano che i valori crescono si allontanano "cubicamente" le distanze fra le variabili e le differenze fra loro superano il migliaio, al di sotto del quale alcuni valori sono possibili ed altri no.
Quindi, una routine limitata ad un ambito di valori riferiti ad un range ristretto di ricerca, può essere praticabile, ma man mano che si amplia il campo di osservazione........

Concludo con un'ultimo "artificio" tratto da quanto sopra, magari utile per una routine di ricerca:

x = sqrt{\frac{42- (y^3 + z^3)}{x}} , nella quale il numeratore e il denominatore del radicando devono avere segno concorde,

mentre il radicando deve essere un quadrato perfetto ( \frac{x^3}{x} )