Fattoriale dispari

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Avatar utente
Cammy87
Messaggi: 144
Iscritto il: 10 mag 2005, 19:50
Località: Serra Riccò

Fattoriale dispari

Messaggio da Cammy87 » 05 apr 2006, 18:57

Calcolare le ultime quattro cifre del numero:
$ 1\cdot 3\cdot 5\cdot ... \cdot9997\cdot 9999 $

Io l'ho fatto, ma forse con un sistema un po' lungo. Probabilmente c'è un metodo più furbo, che mi è sfuggito. :D

Avatar utente
Santana
Messaggi: 72
Iscritto il: 05 feb 2006, 19:01
Contatta:

Re: Fattoriale dispari

Messaggio da Santana » 05 apr 2006, 20:52

Cammy87 ha scritto:Calcolare le ultime quattro cifre del numero:
$ 1\cdot 3\cdot 5\cdot ... \cdot9997\cdot 9999 $

Io l'ho fatto, ma forse con un sistema un po' lungo. Probabilmente c'è un metodo più furbo, che mi è sfuggito. :D
Se intendi le ultime quattro cifre a destra è semplice 0000. :D

Ah che distratto, il fattoriale è dispari...

Calcolo l'ultima cifra (quella più a destra?) abbiamo

$ 1\cdot 3\cdot 5\cdot7\cdot 9 \-= 5 \mod 10 $

essendo $ 5^n \-= 5 \mod 10 \forall n \in N^+ $ l'ultima cifra è 5.

Avatar utente
Martin
Messaggi: 15
Iscritto il: 28 mar 2006, 18:03
Contatta:

Messaggio da Martin » 05 apr 2006, 21:39

Salute a tutti, sono nuovo :)

Dunque, il numero termina socuramente per 5 poichè è un multiplo dispari di 5 (è sempre assente il fattore 2).

Dunque

(scusate ma sto ancora prendendo familiarità col latex)
$ 1*3*5*...*9999 $ è come scrivere $ \frac{10000!}{2*4*6*...*10000} $

Il valore 10000! mi aspetto che abbia 1000 zeri poichè ci sono 1000 multipli di 10, da cui 1000 2*5
Tutti i 2 vengono semplificati nella frazione e resta dunque $ 5^{1000}. $
Mi accorgo che tutte le potenze pari di 5 terminano con 25 (la seconda) e poi con 625 (dalla quarta in su),
quindi il nuumero terminerà con 625.
La quarta cifra credo si possa trovare allo stesso modo ma non ho verificato :)

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 05 apr 2006, 22:20

Se può essere utile $ 5^n $, se $ n\geq4 $ e $ 4|n $, finisce per 0625. Ma non riesco a capire (mea culpa, oppure culpa della verifica che non hai ancora fatto) perchè il fattoriale debba finire con 625: non è una potenza di 5. Dunque, perché dovrebbe finire per 625?
A proposito: benvenuto nel forum Martin!
"Sei la Barbara della situazione!" (Tap)

Avatar utente
Santana
Messaggi: 72
Iscritto il: 05 feb 2006, 19:01
Contatta:

Messaggio da Santana » 06 apr 2006, 12:57

piever ha scritto:Se può essere utile $ 5^n $, se $ n\geq4 $ e $ 4|n $, finisce per 0625. Ma non riesco a capire (mea culpa, oppure culpa della verifica che non hai ancora fatto) perchè il fattoriale debba finire con 625: non è una potenza di 5. Dunque, perché dovrebbe finire per 625?
A proposito: benvenuto nel forum Martin!
$ 5^4=625 $ un piccolo errore di calcolo, tutto qui...

Ciao Ciao :D

darkcrystal
Messaggi: 699
Iscritto il: 14 set 2005, 11:39
Località: Chiavari

Messaggio da darkcrystal » 06 apr 2006, 13:52

Beh, dico anch'io la mia. Chiedere le ultime quattro cifre equivale a chiedere la congruenza modulo 10000, ossia $ 2^4*5^4 $
Modulo $ 5^4 $ questo numero è zero, in quanto ci sono ben più di quattro multipli di 5 nel prodotto
Per calcolare la congruenza modulo 16, invece, il mio procedimento è questo: divido i 5000 valori in gruppi da 8:
1-3-5-7-9-11-13-15
17-19-21-23-25-27-29-31
...
in cui compaiono tutte le classi di congruenza dispari modulo 16. Il prodotto dei termini in un gruppo è congruo (si verifica facilmente) a 1 modulo 16, quindi il prodotto di tutti i gruppi è congruo a 1 mod 16.
Detto questo, per il teorema cinese, sappiamo che esiste una sola soluzione modulo 10000 del sistema $ x \equiv 0 (\mod 5^4) $ e $ x \equiv 1 (\mod 16) $. Si verifica facilmente che $ 625 \equiv 1 (\mod 16) $ e quindi abbiamo trovato la nostra soluzione: 0625.

Ciao!
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein

Membro dell'EATO

Avatar utente
Cammy87
Messaggi: 144
Iscritto il: 10 mag 2005, 19:50
Località: Serra Riccò

Messaggio da Cammy87 » 06 apr 2006, 14:41

La tua risposta, darkcrystal, è giusta: il numero termina per 0625!!!!
:D Il tuo procedimento è anche molto più rapido del mio, seppur concettualmente simile.

Avevo trovato che il fattoriale doveva essere $ \equiv1\pmod{16} $ e$ \equiv0\pmod{5^4} $, ma per trovare il valore giusto ho dovuto controllare tutte le possibili terminazioni di un numero multiplo di $ 5^4 $, e vedere quali fossero effettivamente $ \equiv1\pmod{16} $.

Con il teorema cinese del resto si evitano un bel po' di conti e di divisioni.
Ciao ciao :wink:

afullo
Messaggi: 937
Iscritto il: 01 gen 1970, 01:00
Località: Almese (TO)
Contatta:

Messaggio da afullo » 06 apr 2006, 23:23

La mia soluzione è simile alle vostre:

Innanzitutto, poiché all’interno della produttoria c’è il fattore 625, e 625*16=10000, ne consegue che gli unici modi in cui può terminare questo numero sono: 0625, 1250, 1875, 2500, 3125, 3750, 4375, 5000, 5625, 6250, 6875, 7500, 8125, 8750, 9375, 0000. Poiché però non sono presenti fattori pari, possiamo tranquillamente scartare le terminazioni pari: restano quindi 0625, 1875, 3125, 4375, 5625, 6875, 8125, 9375. Resta ora da determinare la congruenza modulo 16 del prodotto di tutti gli altri fattori. Ma 1*3*5*7*9*11*13*15 = 2.027.025 = 126.689*16+1, ovvero il prodotto è congruo a 1 modulo 16. Allora è congruo a 1 modulo 16 anche ogni prodotto del tipo (16n+1) * (16n+3) * (16n+5) * (16n+7) * (16n+9) * (16n+11) * (16n+13) * (16n+15). Facendo variare n fra 0 e 624 si ottengono tutti i fattori della produttoria considerata, che dunque è anch’essa congrua a 1 modulo 16. Dovevamo però determinare il resto della divisione modulo 16 di tutti i fattori escluso il 625; però questo è congruo a 1, quindi il quoziente è anch’esso congruo a 1. Di conseguenza possiamo affermare che il prodotto è della forma 625*(16m+1) = 10000*m+625, dunque il numero termina per 0625.
Ultima modifica di afullo il 07 apr 2006, 19:37, modificato 1 volta in totale.

Avatar utente
Martin
Messaggi: 15
Iscritto il: 28 mar 2006, 18:03
Contatta:

Messaggio da Martin » 07 apr 2006, 19:08

Mi son presentato facendo un problema e ciò fatto una figuraccia :oops:
Speriamo vada meglio in futuro...
Qualcuno può spiegarmi comunque perchè il metodo funziona?

afullo
Messaggi: 937
Iscritto il: 01 gen 1970, 01:00
Località: Almese (TO)
Contatta:

Messaggio da afullo » 07 apr 2006, 19:38

che cosa non hai capito esattamente? :wink:

Avatar utente
Martin
Messaggi: 15
Iscritto il: 28 mar 2006, 18:03
Contatta:

Messaggio da Martin » 07 apr 2006, 19:55

Riguardando tutto ho capito perchè funziona.....dal falso ho implicato il vero ( 8) )
però non capisco.....perchè le cifre di un numero si determinano con le congruenze? (so cosa sono e che proprietà hanno....ma essendo dei resti non capisco perchè riguardino le ultime cifre)

afullo
Messaggi: 937
Iscritto il: 01 gen 1970, 01:00
Località: Almese (TO)
Contatta:

Messaggio da afullo » 07 apr 2006, 20:11

Le ultime cifre di un numero si determinano con le congruenze in quanto l'ultima cifra di un numero è pari alla congruenza modulo 10 di quel numero, le ultime due cifre sono pari alla congruenza modulo 100, le ultime tre alla congruenza modulo 1000... le ultime n alla congruenza modulo 10^n.

tutto chiaro adesso? 8)

Avatar utente
Martin
Messaggi: 15
Iscritto il: 28 mar 2006, 18:03
Contatta:

Messaggio da Martin » 07 apr 2006, 20:23

*mumble mumble* si chiaro, infatti l'ultima cifra è lo scarto (dunque il resto) del numero dal multiplo di 10 precedente, grazie! :)

afullo
Messaggi: 937
Iscritto il: 01 gen 1970, 01:00
Località: Almese (TO)
Contatta:

Messaggio da afullo » 08 apr 2006, 21:02

Di niente, è stato un piacere! 8)

Avatar utente
EUCLA
Messaggi: 771
Iscritto il: 21 apr 2005, 19:20
Località: Prato

Messaggio da EUCLA » 11 apr 2006, 19:11

scusa afullo se quindi devi calcolare le n cifre finali in base k
si usano le congr. modulo $ k^n $?

Rispondi