Scrivere un numero enorme come prodotto di tre numeri

[Sdavas]

Ecco un problema delle gare a squadre di Roma:

In quanti modi posso scrivere 3033030^4 come prodotto di tre numeri interi positivi? Dare come risposta le 4 cifre meno
significative del risultato (cioè migliaia, centinaia decine ed unità).
(Osservazione: due prodotti contenenti gli stessi fattori, anche se in ordine diverso, sono da considerarsi identici e quindi
vanno contati una sola volta)

Il numero scomposto in fattori è: 2^4*3^4*5^4*7^4*11^4*13^4*101^4.
Ho considerato dapprima tutte le terne in cui almeno un fattore è un 1: essendo i divisori in tutto 5^7, i casi citati dovrebbero essere 39063.
Non riesco però a trovare una strategia per calcolare i rimanenti casi nei quali nessuno dei tre fattori è un uno.

Qualcuno ha qualche idea?
Ringrazio in anticipo.
Saluti.
RobStam

[orsoulx]

Proverei con

28477656

Ciao

[Sdavas]

Grazie.
Io ho provato a considerare tutte le combinazioni di esponenti utilizzando un grafo ad albero ma con 7 fattori mi risulta ingestibile la determinazione dei casi uguali. Le terne di esponenti del primo fattore possono essere (4,0,0); (3,1,0); (2,2,0) e (2,1,1).

Ognuna di queste combinandosi con ciascuna delle altre, anche permutate dà 15^6*4 risultati possibili.
Come si possono poi considerare i "doppioni"?

Ringrazio ancora,
RobStam.

[orsoulx]

"RobStam":Come si possono poi considerare i "doppioni"?

Probabilmente esistono metodi più eleganti e rapidi; ho adottato un procedimento molto 'spartano' impedendo ai doppioni di nascere.

Esistono solo 2 tipologie di ripartizione dei singoli fattori primi: [0, 1, 3] che rende immediatamente distinguibili i tre Fattori (uso il maiuscolo per indicare i Fattori grandi: prodotti di fattori primi ) cercati e [0, 2, 2], [2, 1, 1] e [4, 0, 0] che possono lasciare terne con coppie di Fattori uguali.
Indicando con $ C_n $ il numero di terne di Fattori con una coppia di uguali, dopo aver considerato $ n $ fattori primi diversi, e con $ D_n $ quelle, invece distinguibili; abbiamo $ C_1=3 $ e $ D_1=1 $.
Aggiungendo un ulteriore fattore primo si possiamo ottenere ancora terne di Fattori con una coppia di uguali solo se le coppie di fattori uguali si dispongono come la coppia di Fattori uguali, dunque $ C_{i+1}=3 C_i $, da cui $ C_n=3^n $. Mentre da una terna di Fattori con coppia di uguali si possono sempre ottenere 6 terne di Fattori distinguibili ( tre aggiungendo [0, 1, 3] ed altri tre aggiungendo uno degli altri, ma con la coppia sfalsata). D'altra parte, come hai notato, da ciascuna terna di Fattori distinguibili si ottengono sempre 15 terne di Fattori distinguibili con un fattore primo in più. Perciò $ D_{i+1}=15 D_i+6 C_i=15 D_i+2 C_{i+1} $.
Iterando sei volte (i calcoli sono semplici, perché la moltiplicazione per 15 si può fare moltiplicando per 30 e dividendo per 2) si arriva a $ C_7=2187; D_7=28475469 $, che sommati danno il risultato cercato.

Ciao

[Sdavas]

Grazie di tutto, veramente un ottimo metodo per evitare i doppioni!