Un milione

[axpgn]

In quanti modi diversi posso esprimere il numero $1.000.000$ come prodotto di tre interi positivi?
(Le fattorizzazioni che differiscono solo per l'ordine dei fattori non sono considerate diverse.)

Cordialmente, Alex

[orsoulx]

139

Ciao

[axpgn]

(me n'ero dimenticato ... )

Cordialmente, Alex

[Erasmus_First]

Due domande a orsoulx, (ma può rispondermi anche axpgn):
1) I tre fattori devono essere distinti o tra i 139 modi c'è anche (per esempio) 100·100·100 ?
2) axpgn dice espressamente «[...] come prodotto di tre interi positivi». Va dunque bene anche 1·1·1000000 ?
_______


-----------
[ot]... Mumble , mumble ...
Per associazione di idee – cioè: un numero intero e il conteggio di quante terne di numeri interi positivi in una precisa rela zione con esso – mi viene un mente un quiz dove c'entra il numero 15015•
Vado a "postare" il quiz che m'è venuto in mente.
Ciao ciao a tutti[/ot]

[axpgn]

1) $100*100*100$ è compreso
2) Sì

"Erasmus_First":... (ma può rispondermi anche axpgn):

Com'è buono Lei!

Cordialmente, Alex

[Erasmus_First]

[ot]

"axpgn":Com'è buono Lei!

Tu dixisti! Tu quoque qui mihi respondisti,
Vale.[/ot]
_______

[orsoulx]

"axpgn":me n'ero dimenticato ...

Non vedo il problema: fra i miei numerosi difetti penso non ci sia (per ora) la fretta.

Ho affrontato il quesito, o meglio la sua generalizzazione (sostituendo ad $ 1.000.000 $ un numero qualsiasi, es $ 2^6*3^5*5^9$), con due approcci diversi trovando una relazione 'strana':
$ ((n+2),(2))= 6 \floor ((n^2+6)/12)+3 \floor (n/2)+2 (n^2 mod 3)+1$
che mette in relazione i due percorsi. L'algoritmo mi pare funzioni egregiamente.

Ciao

[axpgn]

@orsoulx

Non so se ho capito bene: avresti trovato un modo "alternativo" di esprimere quel "famoso" coefficiente binomiale? Che sarebbe una bella scoperta
Però, sempre se ho capito bene, come c'entra questo con la discussione originale? In particolare cosa sarebbe $n$?

Cordialmente, Alex

[orsoulx]

..e bisogna sempre spiegarti tutto! Allora no. La relazione è un sottoprodotto dei due procedimenti che ho provato per risolvere il problema in generale. Al più quell'uguaglianza mi serve per eliminare uno delle 'parte intera' del secondo membro utilizzando il primo membro che mi è più simpatico. $ n$ è un naturale qualsiasi...

...nella fattispecie uno degli esponenti della fattorizzazione del numero di cui si cerca quante sono le scomposizioni in triprodotti.
$ 1.000.000 $ è un caso particolarmente semplice, perché ha due soli fattori primi e con la medesima molteplicità: in questo caso l'algoritmo che ho trovato si riduce ad una funzione della sola molteplicità.

Ciao

[axpgn]

"orsoulx":..e bisogna sempre spiegarti tutto!

E che ci vuoi fare ... ...


Ho pensato questo ...

Dato [size=150]$N=p_1^(e_1)*p_2^(e_2)*...*p_n^(e_n)$[/size], ogni sua scomposizione in tre fattori sarà così

[size=150]$(p_1^(e_(11))*p_2^(e_(21))*...*p_n^(e_(n1)))*(p_1^(e_(12))*p_2^(e_(22))*...*p_n^(e_(n2)))*(p_1^(e_(13))*p_2^(e_(23))*...*p_n^(e_(n3)))$[/size]

con [size=150]$e_(i1)+e_(i2)+e_(i3)=e_i$[/size].

Di queste "addizioni" ce ne dovrebbero essere, per ciascun primo $P_i=((e_i+1)(e_i+2))/2$ e quindi le scomposizioni totali saranno $T=P_1*P_2*...P_n$, però ordinate.

Se $N$ è un cubo allora esisterà una e una sola scomposizione in cui i tre fattori saranno uguali, altrimenti no.
Se due fattori sono uguali allora avremo tre scomposizioni "simili" e due da scartare; in tal caso avremo una situazione di questo tipo:
$(p_1^(e_(1x))*p_2^(e_(2x))*...*p_n^(e_(nx)))*(p_1^(e_(1x))*p_2^(e_(2x))*...*p_n^(e_(nx)))*(p_1^(e_1-2*e_(1x))*p_2^(e_2-2*e_(2x))*...*p_n^(e_n-2*e_(nx)))$
con $e_(ix)$ che varia da $0$ a $\lfloor e_i/2 \rfloor $, perciò le scomposizioni di questo tipo sono $S=(\lfloor e_1/2 \rfloor +1) * (\lfloor e_2/2 \rfloor +1) * ... * (\lfloor e_n/2 \rfloor +1) $ il tutto da dividere per tre (sottraendo uno oppure no se $N$ è un cubo oppure no).
Se i tre fattori sono diversi allora avremo sei situazioni simili da cui concludendo le scomposizioni non ordinate sarebbero $(T-3S)/6+S$ (invece se $N$ è un cubo $(T-3S-1)/6+S+1$)

Forse ...

Cordialmente, Alex

[orsoulx]

@Alex,

senza forse. I nostri procedimenti sono sostanzialmente identici. Scomposto il numero in fattori primi, quali questi siano non ha alcuna importanza: conta solo quanti sono e la molteplicità con cui compaiono.
Evito gli indici per comodità, tanto ci capiamo (spesso). Se $ n $ è l'esponente con cui compare un certo fattore primo, questo produce $ floor (n/2 ) $ terne con due elementi uguali ( ed il terzo diverso) a cui occorre aggiungerne ancora una se $ n $ non è divisibile per $ 3 $; se, invece è divisibile per $ 3 $ quella da aggiungere sarà una terna di elementi tutti uguali.
Vi sono poi terne con tutti elementi diverse e queste sono l'arrotondamento di $ n^2/12 $, che si può scrivere come $ floor ((n^2+k)/12) $ con $ k \in [3..7] $.
Volendo evitare questo arrotondamento si può, come dici, considerare che il totale delle terne ordinate è $ ((n+2),(2)) $. Se da queste togliamo $ 3 floor((n+2)/2) $, e aggiungiamo $ 2 $ quando $ n $ è un multiplo di tre, troviamo esattamente il sestuplo di quanto vogliamo (la formula nasceva da questa uguaglianza).
Stabilito quante sono le terne di ciascun tipo per ogni fattore occorre ancora studiare cosa capita quando si combinano con le loro sorelline, ma questa è una parte più lunga, ma anche più semplice.

Ciao
Edit: corretti due denominatori $ 12 $ invece di $ 6 $.