Fatorial: diferenças entre revisões

2 504 bytes removidos ,  16h08min de 25 de maio de 2016
Foram revertidas as edições de 177.220.157.245 por fazer testes nos artigos (usando Huggle) (3.1.20)
(Foram revertidas as edições de 177.220.157.245 por fazer testes nos artigos (usando Huggle) (3.1.20))
:<math>\sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor</math>
 
Esta fórmula permite que fatoriais grandes sejam fatorados eficientemente. A única desvantagem é ter que calcular todos os números primos até n!
 
O [[Teorema de Wilson]] diz que ''(p-1)! + 1'' é um múltiplo de ''p'' se, e somente se, ''p'' for um [[número primo]].
===Um método alternativo===
É possível calcular o expoente de um número primo <math>p</math> na decomposição de <math>n!</math> escrevendo-se o número <math>n</math> como a soma das potências de <math>p</math> (de modo semelhante ao usado na [[Conversão entre sistemas numéricos]]), e depois substitui-se cada uma dessas potências pelo somatório de todas as potências menores de <math>p</math>, incluindo-se <math>p^0=1</math> e calcula-se o resultado.
Vejamos alguns exemplos para melhor clareza:
 
1) Qual é o expoente de 2 na fatoração prima de <math>14!</math>?
 
<math>14=8+4+2={\color{blue}2^3}+{\color{blue}2^2}+{\color{blue}2}</math>.
 
Substituindo-se <math>2^3</math> por <math>(1+2^1+2^2)=7</math>,
 
e depois <math>2^2</math> por <math>(1+2^1)=3</math> e
 
<math>2^1</math> por <math>1</math> (pois é igual a <math>2^0</math>) e calculando, obtemos:
 
<math>7+3+1=11</math>. Logo <math>14!</math> é múltiplo de <math>2^{11}</math> na sua decomposição em fatores primos.
 
Outro exemplo:
 
2) Se <math>n!</math> em sua fatoração prima é múltiplo de <math>5^{2016}</math>, determine o menor valor possível de <math>n</math>.
 
O caminho é o inverso: escreve-se 2016 como a soma dos somatórios de potências de 5 (dados pela tabela abaixo) e depois substitui-se cada um desses somatórios pela menor potência de 5 que é maior que o somatório.
 
{| border="2" cellpadding="2"
! n
! <math>5^n</math>
! <math>\sum_{k=0}^{n-1}5^k</math>
|-
| 0 || 1 || <math>-</math>
|-
| 1 || 5 || 1
|-
| 2 || 25 || 6
|-
| 3 || 125 || 31
|-
| 4 || 625 || 156
|-
| 5 || 3125 || 781
|-
| <math>\cdots</math>
| <math>\cdots</math>
| <math>\cdots</math>
|}
 
Então temos:
 
<math>2016=2.{\color{blue}781}+2.{\color{blue}156}+4.{\color{blue}31}+3.{\color{blue}6}</math>
 
Substituindo-se os números em azul pelas potências de 5 correspondentes na tabela acima e calculando-se, vem:
<math>{\color{red}3125}.2+{\color{red}625}.2+{\color{red}125}.4+{\color{red}25}.3=2.5^5+2.5^4+4.5^3+3.5^2=8075</math>.
 
O que significa que <math>8075!</math> em sua fatoração prima é múltiplo de <math>5^{2016}</math>.
Consideremos o número <math>8078!</math>.
 
Qual é o expoente de 5 em sua fatoração prima?
 
Sendo <math>2.5^5+2.5^4+4.5^3+3.5^2+3.5^0=8078</math>
 
Fazendo a substituição das potências de 5, usando-se a tabela acima, vem:
<math>2.781+2.156+4.31+3.6=2016</math>.
 
De fato, pois <math>8878-8075=3<5</math>.
 
== Algoritmo ==