Newsgroup: it.hobby.enigmi
Titolo: Triangoli numerici

I seguenti triangoli numerici TN di ordine 2 e 3, hanno 2
caratteristiche:
a) Non ci sono numeri ripetuti nello stesso triangolo. 
b) Ogni numero, a partire dalla seconda fila, e' la somma dei 2 numeri
sottostanti.
   3
 1   2
    9
  3   6
1   2   4
Quello che ci interessa e' minimizzare il numero piu' alto per ciascuna
piramide di ordine n.
Con questa ottica vediamo subito che la piramide di ordine 3, puo'
essere migliorata con:
    8
  3   5
2   1   4
Scriviamo allora PN 2(3), PN 3(8).
Quali sono i risultati migliori per PN 4,5,6,7.....
:) dario

 ...
Mi sono dedicato, per cominciare, a PN 5.
Mi ero fatto un modello mentale intuitivo
e sono arrivato a questa soluzione:
          50
       20   30
    12    8   22
  9    3    5   17
7    2    1   4   13
Ho applicato immediatamente la mia Darwin Machine
http://www.geocities.com/liviozuc/darwin.html
che mi ha sorpreso con questa che credo ottimale:
          43
        23   20
     15   8    12
  10    5    3    9
6    4    1    2    7
Ora vado avanti perche' non ho trovato ancora uno 
straccio di algoritmo, salvo mettere l'uno al centro.   :o)
Ciao
Livio
-- 
Posted from 
twingo.tiscalinet.it
 [195.130.224.85] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 straccio di algoritmo, salvo mettere l'uno al centro.   :o)
Ho provato con questo algoritmo, non sono sicuro che dia sempre la sol.
ottimale
partendo dal TN2:
.   3
. 2   1
aggiungi il piu' piccolo n. non ancora utilizzato (4) alla base, accanto al
piu' piccolo dei due estremi (1), e quindi procedi verso l'alto
.     8
.   3   5
. 2   1   4
ancora aggiungi 7 accanto a 2 (non puoi aggiungere 6 perche' darebbe somma
8, gia' utilizzato)
.       20
.     12  8
.   9   3   5
. 7   2   1   4
ora aggiungi 6 accanto a 4
.         43
.       20  23
.     12  8   15
.   9   3   5   10
. 7   2   1   4   6
che e' la tua soluzione per TN5.
procedendo, aggiungi 11 accanto a 6
.           108
.         43  65
.       20  23  42
.     12  8   15  27
.   9   3   5   10  17
. 7   2   1   4   6  11
eccetera.
pero', se trovato il TN5, aggiungi 11 a sinistra, trovi un risultato minore.
.            103
.          60  43
.        40  20  23
.      28  12  8   15
.   19  9   3   5   10
. 11  7   2   1   4   6
forse, per ogni passaggio, scelto il n. da aggiungere alla base, bisogna
verificare le due possibilita' dx e sn.
ciao
paolo

 I seguenti triangoli numerici...
Intervento n.2
Qualche passetto avanti.
Pare che ciascun triangolo contenga tutti
quelli di ordine inferiore:
PN 1(1) <- Pn 2(3) <- PN 3(8) <- PN 4(20) <- PN 5(43) <- PN 6(102)  <-
...
--------------------------------------------------------------------------
            \
             \
            / \
           /102\
          / \   \
         / 43\ 59\
        /   / \   \
       / 23/ 20\ 39\
      /   / \   \   \
     / 15/ 8 \ 12\ 27\
    /   /   / \   \   \
   / 10/ 5 / 3 \ 9 \ 18\
  /   /   / \   \   \   \
 / 6 / 4 / 1 \ 2 \ 7 \ 11\
/___/___/_____\___\___\___\
PN 1(1) e' il piu' piccolo ed e' baricentrico.
Il triangolo insieme di tutti i triangoli numerici
cresce una volta a destra, una volta a sinistra.
Il numero nuovo da aggiungere alla base va 'ricercato'
incominciando dal piu' basso lasciato libero dell'insieme
precedente.
Bisogna dimostrarlo?
Non c'e' un matematico da quelle parti?    :o)
Ciao
Livio
-- 
Posted from 
laguna.tiscalinet.it
 [195.130.224.86] 


 :) dario
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Con l'aiuto del calcolatore ho trovato questi risultati (riporto solo la
base dei triangoli). Naturalmente ogni soluzione ha la sua corrispondente
speculare:
PN 4(20)
2  3  1  6
4  1  2  7
4  2  1  7
PN 5(43)
6  4  1  2  7    (La stessa di Livio, complimenti alla tua Darwin Machine!)
PN 6(98)
8  6  1  3  2  10
PN 7(212)
11  7  2  1  4  6  13
Non garantisco che siano i risultati migliori, in particolare per PN 7. Per
forza di cose ho dovuto limitare il range di numeri da provare e non è detto
che il risultato migliore si ottenga usando nella base numeri "piccoli". Ho
visto infatti che, limitando la ricerca per PN 7 a valori della base <= 12
si trova una soluzione che dà come risultato 219 (7, 9, 2, 1, 4, 6, 12).
Forse ottimizzando un po' il programma potrei ridurre i tempi e provare
valori ancora più alti, ma al momento mi accontento (e poi è ora di andare a
dormire). :-)
Ciao
Giorgio

 ha scritto nel messaggio
news:39F3534C...@tiscalinet.it...

L'idea è buona, ma nel caso di PN 6 c'è una soluzione migliore (vedi mio
altro post). Però si può notare che PN 6 si sviluppa dalla prima soluzione
di PN 4 (vedi sempre il mio altro post). Può darsi che ci siano due sviluppi
separati per triangoli con lato pari e con lato dispari... Adesso però vi
lascio e vado proprio a dormire. :)
Ciao a tutti
Giorgio

 
39F3534C...@tiscalinet.it
">news:39F3534C...@tiscalinet.it...

MA POTEVI ANDARE A DORMIRE MEZZ'ORA PRIMA ????    :0)   :o)   ;))  
Guardando le ore degli interventi, 22:53.56 il mio, 22:55.05 il tuo, la
mia congettura ha probabilmente battuto un record on-line: e' durata
esattamente 69 minuti secondi!!! Agli antipodi di quelle di Fermat.
Tutta l' ascii-costruzione e' crollata come un castello di carte:
         / 4
        /   
       / 23/
      /   / 
     / 15/ 8       SCRASH!!!
    /   /      4\
   / 10/ 5 /  34\56  3
  /   /   / 56\\2\56\76
 / 6 / 4 / 1 /79\\8///3\57
/___/___/____@@###@@##@@#__\
Un po' e' colpa della Darwin Machine, che imita troppo bene la natura:
ottimizza... ma non trova l'ideale se non per t che tende all'infinito.
(Anche se aveva fatto il fatidico 'salto fuori dal minimo relativo'
capitando nella sequenza 10,2,3,1,6,15 che io ho avventatamente
bloccato). Va comunque meglio per processi fisici dove non importi se
2+2=3.997
Ma sicuramente e' colpa mia: la regola che i numeri generati da somme
non debbano ripetersi e' 'irragionevole', non e' probabilmente
riconducibile ad algoritmi semplici come quello che ho immaginato, o,
forse, a nessun algoritmo. (E il forse e' d'obbligo). Se non ci fosse
quella regola su tutto il triangolo, ma solo sulla base, la sequenza
sarebbe facilmente predicibile, sarebbe crescente dal centro alla
periferia. Ma quella regola introduce delle discontinuita' imprevedibili
che finiscono per promuovere altre sequenze apparentemente meno
promettenti. Qui la brute force potrebbe essere l'unica strada.
Lunedi' 23/10 ore 0:28
Buona notte!
Livio
-- 
Posted from 
twingo.tiscalinet.it
 [195.130.224.85] 


Qualche riflessione...
Cerchiamo innanzitutto l'espressione per il numero piu' alto (che 
chiamero' NumeroAlto) per ciascuna piramide di ordine n.
Si puo' dimostrare abbastanza facilmente che, essendo b[1]...b[n] gli 
elementi della base, questa espressione e' data da (scrivo tutte le formule 
in linguaggio Mathematica... tanto sono facilmente comprensibili anche a 
chi non lo usa):
NumeroAlto = Sum[Binomial[n-1,i-1]*b[i],{i, 1, n}]
Notiamo che NumeroAlto si puo' esprimere come prodotto di una matrice 
orizzontale 1*n pari all'ennesima riga del triangolo di Tartaglia per una 
matrice verticale n*1 pari agli elementi della base della nostra piramide 
scritti in colonna.
Per continuare l'analisi credo sia interessante considerare il problema 
"semplice", ovvero evitare ripetizioni di numeri solo nella base, e non in 
tutta la piramide. In seguito considereremo il problema originario, e 
potremmo studiare quanto le condizioni originarie modifichino il problema, 
e se c'e' una regolarita' nelle differenti soluzioni.
Come gia' sottolineato, in questo caso la soluzione migliore del problema, 
considerando numeri>=1 e' appunto quella, come sottolinea Livio, "crescente 
dal centro alla periferia" (esempi)
base 4: 3-1-2-4
base 5: 4-2-1-3-5
base 6: 5-3-1-2-4-6
Calcoliamo quanto vale NumeroAlto nel caso descritto...
mi risparmio la dimostrazione banale dalla formula precedente...
Per il caso di n dispari questa e'
NumeroAlto = Sum[Binomial[n-1,i-1]*(2n-4i+3),{i,1,(n+1)/2}]
E' interessante dare questa formula in pasto al Matematica, che la 
semplifica immediatamente nella seguente funzione, continua e derivabile:
NumeroAlto = 2^(1-n)+3*Gamma[n]*Hypergeometric2FlRegularized[1,(3-n)/2,(3
+n)/2,-1]/Gamma[(1/2)*(-1+n)+4*Gamma[n]*Hypergeometric2FlRegularized[2,(5-
n)/2,(5+n)/2,-1]/Gamma[(1/2)*(-3+n)
Evitando di studiare questa espressione, con qualche piccola prova si puo' 
verificare che funziona pure per gli n pari !!!
Detto questo, indichiamo quanto vale NumeroAlto nella soluzione del 
problema semplice, a seconda della dimensione della base
N      NumeroAlto
2	3
3	7
4	16
5	35
6	76
7	162
8	344
9	723
10	1516
11	3158
12	6568
13	13598
14	28120
15	57956
16	119344
17	245123
18	503116
19	1030542
20	2109704
...
Consideriamo le soluzioni del problema complesso calcolate da Giorgio con 
"forza bruta". Chiamo ideale la soluzione del problema semplice.
N -Ideale-Compl-Differenza
2 -   3  -   3 -  0
3 -   7  -   8 -  1    	
4 -  16  -  20 -  4
5 -  35  -  43 -  8
6 -  76  -  98 - 22
7 - 162  - 212 - 50
L'ideale sarebbe descrivere Differenza con una funzione semplice di N.
Questo purtroppo non sembra possibile (non sembra non vuol dire che non lo 
sia)
Ad esempio, nel caso ideale si puo' notare una certa "regolarita'": il 
rapporto R[n]=Soluzione[n]/Soluzione[n-1] e' una funzione decrescente.
Questa regolarita' sembra perdersi nel problema complesso, in cui questo 
rapporto e' molto piu' irregolare.
Concludendo... probabilmente l'unico modo per risolvere il problema e' 
utilizzare la "brute force"
Ciao
Paolo Zavarise

 :) dario
Se siamo tutti d'accordo che questo problema si risolve solo con la
brute force, converrete che il problema si fa interessante laddove la
brute force mostra la lingua fuori per i mezzi tecnologici (o peggio in
assoluto, pragmaticamente parlando, come ne 'Le scimmiette' che ho
postato piu' sopra).
Questo potrebbe essere il caso dei triangoli numerici di ordine 20, che
ne dite?
Ne ho costruito uno qua sotto che probabilmente non e' l'ottimo. Pero'
finche' nessuno lo batte, restera' un record.
Qualcuno ci vuole provare? (se qualcuno ci prova, poi ci riprovo   :o)
 20)   3406656
 19)   1635413  1771243
 18)   832257  803156  968087
 17)   449257  383000  420156  547931
 16)   254042  195215  187785  232371  315560
 15)   147610  106432  88783  99002  133369  182191
 14)   86516  61094  45338  43445  55557  77812  104379
 13)   50453  36063  25031  20307  23138  32419  45393  58986
 12)   29028  21425  14638  10393  9914  13224  19195  26198  32788
 11)   16410  12618  8807  5831  4562  5352  7872  11323  14875  17913
 10)   9109  7301  5317  3490  2341  2221  3131  4741  6582  8293  9620
 9)   4976  4133  3168  2149  1341  1000  1221  1910  2831  3751  4542 
5078
 8)   2688  2288  1845  1323  826  515  485  736  1174  1657  2094 
2448  2630
 7)   1445  1243  1045  800  523  303  212  273  463  711  946  1148 
1300  1330
 6)   777  668  575  470  330  193  110  102  171  292  419  527  621 
679  651
 5)   418  359  309  266  204  126  67  43  59  112  180  239  288  333 
346  305
 4)   224  194  165  144  122  82  44  23  20  39  73  107  132  156 
177  169  136
 3)   120  104  90  75  69  53  29  15  8  12  27  46  61  71  85  92 
77  59
 2)   66  54  50  40  35  34  19  10  5  3  9  18  28  33  38  47  45 
32  27
 1)   36  30  24  26  14  21  13  6  4  1  2  7  11  17  16  22  25  20 
12  15
Ciao a tutti.
Livio
-- 
Posted from 
mta16-acc.tin.it
 [212.216.176.47] 


 sottostanti...
Senti, senti, senti....
-----------------------------------------------------------------
Greetings from the On-Line Encyclopedia of Integer Sequences!
Matches (up to a limit of 30) found for       1 3 8 20 43 : 
[It will take a few minutes to search the table]
ID Number: A028307
Sequence:  1,3,8,20,43,98,212,465,1000,2144,4497,9504
Name:      Form a triangle with n numbers in top row;
           all other numbers are the sum of their parents.
           E.g.: 4 1 2 7; 5 3 9; 8 12; 20. 
           The numbers must be positive and distinct and 
           the final number is to be minimized.
Links:     Problem 401 here suggested this sequence
Example:   Solutions for n=1,2,... are 1; 1 2; 2 1 4; 4 1 2 7;...
Keywords:  nonn
Offset:    1
Author(s): Mauro Fiorentini Milano Italy
-----------------------------------------------------------------
Sembra che Mauro Fiorentini la sappia lunga sull'argomento!!!
Ciao
