Newsgroup: it.hobby.enigmi
Titolo: Fattoriale fattorizzato

56 fattoriale, e' uguale il prodotto dei primi 56 numeri naturali:
1*2*3*....*55*56 dove il piu' piccolo e'=1.
Esprimi 56! come prodotto di 56 interi non necessariamente differenti,
in modo che il piu' piccolo sia piu' grande possibile.
ciao :) dario

 ha scritto nel messaggio
news:398848BC...@mclink.it...

Trovo una soluzione, non so se sia quella ottima, dove il piu' piccolo
fattore vale 15.
spoiler
v
v
v
v
v
v
v
In primo luogo calcolo (valore approssimato)
56! = 7.109986 * 10^74
Poi calcolo la radice 56esima di questo numero, che risulta 21.70903472
Devo quindi cercare fattori che si discostino il meno possibile dalla
radice.
Scomponendo 56! (o meglio scomponendo tutti i fattori da 2 a 56), trovo:
2 ^ 53
3 ^ 26
5 ^ 13
7 ^ 9
11 ^ 5
13 ^ 4
17 ^ 3
19 ^ 2
23 ^ 2
29 ^ 1
31 ^ 1
37 ^ 1
41 ^ 1
43 ^ 1
47 ^ 1
53 ^ 1
e cerco di accorpare i fattori nel modo migliore possibile:
(5*3) ^ 9
(2*2*2*2) ^ 11
17 ^ 3
19 ^ 2
(7*3) ^ 9
(11*2) ^ 5
23 ^ 2
(13*2) ^ 4
29 ^ 1
31 ^ 1
37 ^ 1
41 ^ 1
43 ^ 1
(5*3*3) ^ 4
47 ^ 1
53 ^ 1
a dire il vero mi avanzava un fattore 81 (3*3*3*3), ma non sono riuscito a
dargli una sistemazione utile (ho solo aumentato 4 dei fattori 3*5)
ciao
paolo

ciao :) dario
. SPOILER
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Ho eseguito tutte le operazioni con Mathematica
(56!)=2^53*3^26*5^13*7^9*11^5*13^4*17^3*19^2*23^2*29*31*37*41*43*47*53
La radice 56esima di (56!) e' pari a 21,709 
E' ovvio, si potrebbe dimostrare per induzione, che il minimo cercato non puo' 
essere superiore a questo valore. Poiche' lavoriamo con fattori interi, il 
minimo cercato non puo' essere superiore a 21. Posso quindi considererare i 
fattori superiori a 21 singolarmente nella scomposizione cercata,
in quanto se li moltiplicassi per un altro numero "sprecherei" fattori 
preziosi.
Chiamiamo con S il prodotto dei fattori fin qui utilizzati, F il numero dei 
fattori utilizzati, R il numero dei fattori mancanti = 56 - F, M = (56!/S)^
(1/R)
A) Consideriamo il nostro traguardo pari a 19
S1 = 53 * 47 * 43 * 41 * 37 * 31 * 29 * 23^2, F1 = 9,  R1 = 47, M1 = 19,82
Rifacciamo il ragionamento.
Il nostro minimo cercato non puo' quindi essere superiore a 19.
S2 = S1 * 19^2, F2 = 11, R2 = 45, M2 = 19,85
Abbiamo sistemato tutti i fattori >= 19. Ora dobbiamo sistemare gli altri 
fattori
Supponiamo che il minimo sia effettivamente 19
Allora i tre 17 li devo moltiplicare per qualcosa, non devo "sprecare" fattori 
e quindi li moltiplico * 2 (34>19)
S3 = S2 * (17*2)^3, F3 = 14, R3 = 42, M3 = 19,10
I quattro 13 li moltiplico ancora per 2 (26>19)
S4 = S3 * (13*2)^4, F4 = 18, R4 = 38, M4 = 18,49
Notiamo che il nuovo minimo possibile e' 18
I cinque 11 li moltiplico ancora per 2 (22>18)
S5 = S4 * (11*2)^5, F5 = 23, R5 = 33, M5 = 18,02
Ora devo sistemare I nove 7. 18/7=2 e qualcosa, quindi li moltiplico per 3 (21>
18)
S6 = S5 * (7*3)^9, F6 = 32, R6 = 24, M6 = 17,01
Attenzione ! ora il nuovo minimo possibile e' 17.
La scomposizione fin qui effettuata non e' piu' conveniente, perche' abbiamo 
sprecato dei fattori per trasformare i 17 in numeri maggiori di 19, quando non 
era necessario.
B) Consideriamo il nostro traguardo pari a 17
Ripartiamo da S2
S2 = S1 * 19^2, F2 = 11, R2 = 45, M2 = 19,85
I tre 17 li consideriamo questa volta singoli
S3 = S2 * 17^3, F3 = 14, R3 = 42, M3 = 20,07
I Quattro 13 li moltiplico per due
S4 = S3 * (13*2)^4, F4 = 18, R4 = 38, M4 = 19,53
I cinque 11 li moltiplico per due
S5 = S4 * (11*2)^5, F5 = 23, R5 = 33, M5 = 19,19
Moltiplichiamo I nove 7 per 3 (21>17, 14<17)
S6 = S5 * (7*3)^9, F6 = 32, R6 = 24, M6 = 18,55
Moltiplichiamo I tredici 5 per 4 (20>17, 15<17)
S7 = S6 * (5*2*2)^13, F7 = 45, R7 = 11, M7 = 16,98
NOOOO Siamo finiti sotto il 17, il nuovo minimo possibile e' 16
I nostri ragionamenti, da B) in poi, restano comunque ancora validi
A questo punto mi restano da ottenere 11 fattori da 18 due e 17 tre, maggiori 
di 16
Capiamo subito che e' impossibile
Si vede facilmente che il minimo raggiungibile e' 12
1 tre per fattore 1 due per fattore abbiamo 6 in tutti i fattori restano 7 due 
e 6 tre
con i 6 tre otteniamo 6 18, con 5 due 6 12, restano due due, otteniamo 4 12, 6 
18 e 2 24
Non siamo pero' sicuri che sia la scomposizione migliore. Sappiamo che male che 
vada il minimo e' 12.
C) Consideriamo il nostro traguardo pari a 15
Ripartiamo da S6
S6 = S5 * (7*3)^9, F6 = 32, R6 = 24, M6 = 18,55
Moltiplichiamo i tredici 5 questa volta semplicemente per 3
S7 = S6 * (5*3)^13, F7 = 45, R7 = 11, M7 = 23,85
A questo punto mi restano da ottenere 11 fattori a 44 due e da 4 tre
Infilando 4 due in ogni fattore, questo e' sicuramente >= di 2^4=16. La 
condizione e' soddisfatta.
Concludendo, una delle scomposizioni cercate possibili e'
S = 53 * 47 * 43 * 41 * 37 * 31 * 29 * 23^2 * 19^2 * 17^3 * 26^4 * 22^5 * 21^9 
* 15^13 * 16^11 * 48^4
Il minimo fattore considerato e' 15.
Non credo ci siano ragionamenti piu' brevi.
Scusate per la terminologia pessima che ho usato, ma credo
di essermi fatto capire... e' mezzanotte e sono stanco :)
Ciao
Paolo Zavarise