Introdução
Esse projeto reúne algumas sequências famosas compostas por números inteiros. Cada sequência é descrita, é dado um pequeno exemplo, é fornecido um pequeno código para gerar mais termos da sequência e também é disponibilizado um arquivo para download com mais termos da sequência (até um dado limite, explicitado em cada caso).
Alguns arquivos estão disponíveis no formato texto (.txt), outros só no formato compactado (.rar), pois são muito grandes. Cada termo da sequência está numa linha do arquivo. Caso cada termo da sequência seja um par (ou um terno) cada número do par (ou terno) será separado por espaço e cada par (ou terno) será colocado numa linha separada. Para salvar os arquivos de texto em seu computador clique no link para visualizar o arquivo, depois vá no menu Arquivo → Salvar e escolha onde deseja salvar o arquivo.
Atenção: alguns arquivos são grandes demais (mais de 100 MiB) para serem abertos normalmente e só podem ser manipulados por meio de comandos e linguagens de programação.
Observação: o Bloco de Notas (ou Notepad) não serve para abrir os arquivos disponibilizados aqui, pois o formato de codificação é diferente. Os programas indicados são Word, WordPad ou Firefox. Isso se deve ao fato de que o formato usado pelo Bloco de Notas gera arquivos maiores do que os utilizados pelos outros programas (cerca de 10% maior). Em termos técnicos, o Bloco de Notas não interpreta LF como quebra de linha, somente CRLF.
Qualquer dúvida, sugestão ou crítica use o Fale Conosco
Índice
Números primos
Semiprimos
Superprimos
Primos gêmeos
Primos frente e verso
Primos palíndromos
Números figurados
Potências perfeitas
Fatoriais
Sequência de Fibonacci
Triângulo de Pascal
Trincas pitagóricas
Tamanho do período de 1/nNúmeros primos
Quase todo mundo já ouviu falar de números primos, mas pouca gente sabe o que é.
Número primo é o inteiro com somente dois divisores positivos distintos (1 e ele mesmo).
Exemplo: 12 tem vários divisores positivos: 1, 2, 3, 4, 6, 12
Já 17 só tem dois: 1, 17
O número 1 só tem um: 1
Assim, dos três números apresentados, só o 17 é primo.
Existem infinitos números primos.Os primeiros primos positivos são:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47Um algoritmo para testar a primalidade de um número pode ser:
Se numero<2 retorna falso Mas se numero=2 retorna verdadeiro Mas se numero divisível por 2 retorna falso Se não Para i, começando em 3, indo até √numero e incrementando de 2 em 2 Se numero divisível por i retorna falso retorna verdadeiroNo PHP isso fica:
<?php
function e_primo($num) {
if ($num<2) return false;
if ($num == 2) return true;
if ($num%2 == 0) return false;
$max = sqrt($num);
for ($i=3; $i<=$max; $i+=2)
if ($num%$i == 0) return false;
return true;
}
?>Esse algoritmo é chamado de determinista, pois ele diz se um dado inteiro é ou não primo.
Existe uma outra família de algoritmos de teste de primalidade, eles são probabilísticos: eles dizem que um dado inteiro é provavelmente primo. Esses algoritmos são bem mais rápidos que esse apresentado. Para encontrar todos os 78.498 primos entre 0 e 1.000.000 esse algoritmo leva cerca de 5.1 segundos enquanto que um algoritmo probabilístico levaria cerca de 1.1 segundo (78% mais rápido)Arquivos para download:
Primos positivos menores que 219 = 524.288 (43.390 termos): texto (285 KiB)
Primos positivos menores que 223 = 8.388.608 (564.163 termos): compactado (1,00 MiB)
Primos positivos menores que 227 = 134.217.728 (7.603.553 termos): compactado (15,0 MiB)
Primos positivos menores que 231 = 2.147.483.648 (105.097.565 termos): compactado (218 MiB)Semiprimos
Semiprimos são os números que são obtidos multiplicando dois números primos.
Exemplos: 6 = 2x3; 21 = 3x7; 121 = 11x11
Todo número primo ao quadrado gera um semiprimo.
Como existem infinitos primos, então existem infinitos semiprimos.Os primeiros semiprimos positivos são:
4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49Um modo de verificar se um número é semiprimo é achar o menor fator primo e depois verificar se o outro fator também é primo.
Exemplo: verificar se 123 é semiprimo. O menor fator primo de 123 é 3, então 123 pode ser escrito como 3x41. Agora basta avaliar se 41 é primo (veja o algoritmo para isso na sequência de números primos). Como 41 é primo, logo 123 é semiprimo.
Outro exemplo: verificar se 125 é semiprimo. O menor fator primo de 125 é 5, então 125 = 5x25. Como 25 não é primo, logo 125 não é semiprimo.
O algoritmo ficaSe numero<4 retorna falso Mas se numero divisível por 2 retorna e_primo(numero/2) Se não Para i, começando em 3, indo até √numero e incrementando de 2 em 2 Se numero divisível por i retorna e_primo(numero/i)No PHP fica:
<?php
function e_semiprimo($num) {
if ($num<4) return false;
if ($num%2 == 0) return e_primo($num/2);
$max = sqrt($num);
for ($i=3; $i<=$max; $i+=2)
if ($num%$i == 0) return e_primo($num/$i);
}
?>Arquivos para download:
Semiprimos positivos menores que 219 = 524.288 (113.307 termos): texto (748 KiB)
Semiprimos positivos menores que 223 = 8.388.608 (1.608.668 termos): compactado (2,63 MiB)
Semiprimos positivos menores que 227 = 134.217.728 (23.140.879 termos): compactado (42,0 MiB)Superprimos
Superprimo é um número primo que ocupa uma posição prima na sequência de primos.
Exemplo:Veja que os números primos 3, 5, 11, 17 ocupam posições primas (2, 3, 5, 7 respectivamente) na sequência dos números primos, por isso eles são chamados de superprimos.
Primos 2 3 5 7 11 13 17 19 23 29 Posição 1 2 3 4 5 6 7 8 9 10 Os primeiros superprimos são:
3, 5, 11, 17, 31, 41, 59, 67, 83, 109, 127, 157, 179, 191Verificar se um dado número é superprimo é um pouco difícil, é mais fácil gera-los. Para isso, primeiro deve-se gerar uma sequência de primos e depois coletar os primos que ocupam posições primas. Algoritmo para gerar os superprimos menores que 100.000:
criar lista primos criar lista superprimos adicionar 2 à primos Para i, começando em 3, indo até 100000 e incrementando de 2 em 2 Se i for primo adicionar i à primos Para cada item de primos Se índice for primo adicionar item à superprimosNo PHP fica:
<?php
$primos = array(2);
$superprimos = array();
for ($i=3; $i<1e5; $i+=2)
if (e_primo($i)) $primos[] = $i;
foreach ($primos as $n=>$primo)
if (e_primo($n+1)) $superprimos[] = $primo;
?>Esse algoritmo é lento e consome bastante memória para sequências grandes, mas serve como exemplo básico. Uma otimização seria eliminar o uso da lista de primos, armazenando somente os superprimos e o índice da sequência de primos:
criar lista superprimos indice inicia em 1 Para i, começando em 3, indo até 100000 e incrementando de 2 em 2 Se i for primo indice aumenta um Se indice for primo adicionar i à superprimosNo PHP fica:
<?php
$superprimos = array();
$indice = 1;
for ($i=3; $i<1e5; $i+=2)
if (e_primo($i)) {
$indice++;
if (e_primo($indice))
$superprimos[] = $i;
}
?>Arquivos para download:
Superprimos menores que 223 = 8.388.608 (46.382 termos): texto (353 KiB)
Superprimos menores que 227 = 134.217.728 (514.798 termos): compactado (1,36 MiB)
Superprimos menores que 231 = 2.147.483.648 (6.037.968 termos): compactado (16,7 MiB)Primos gêmeos
Primos gêmeos são dois primos que diferem de duas unidades. O menor par é (3, 5). Ainda não se sabe se existem infinitos primos gêmeos ou não.
Os primeiros pares são:
(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73), (101, 103), (107, 109), (137, 139)Verificar se dois inteiros são primos gêmeos é relativamente fácil, basta verificar se a diferença entre eles é 2 e se ambos são primos
Se |num1 - num2| = 2 E num1 for primo E num2 for primo retorna verdadeiro Se não retorna falsoPara gerar uma lista de primos gêmeos basta gerar uma lista de primos depois verificar se cada primo mais 2 também é primocriar lista primos_gemeos Para i, começando em 3, indo até 100000 e incrementando de 2 em 2 Se i for primo Se (i+2) for primo adicionar lista(i, i+2) à primos_gemeosNo PHP fica:
<?php
$primos_gemeos = array();
for ($i=3; $i<1e5; $i+=2)
if (e_primo($i) && e_primo($i+2))
$primos_gemeos[] = array($i, $i+2);
?>Arquivos para download:
Primos gêmeos menores que 223 = 8.388.608 (50.638 termos): texto (772 KiB)
Primos gêmeos menores que 227 = 134.217.728 (571.313 termos): compactado (2,64 MiB)
Primos gêmeos menores que 231 = 2.147.483.648 (6.810.670 termos): compactado (32,7 MiB)Primos frente e verso
Essa sequência é formada por primos que quando lidos de trás para frente continuam sendo primos.
Exemplo: 981.437 é um número primo e 734.189 ("981.437" invertido) tambémOs primeiros termos são:
2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 101, 107, 113, 131, 149, 151, 157, 167, 179, 181, 191, 199Verificar se um número pertence à essa sequência é fácil, basta verificar se ele é primo e seus dígitos invertidos também:
Se numero for primo E inverter(numero) for primo retorna verdadeiro Se não retorna falsoNo PHP fica:
<?php
function e_primo_frente_verso($num) {
return e_primo($num) && e_primo(strrev($num));
}
?>Arquivos para download:
Primos frente e verso menores que 223 = 8.388.608 (65.401 termos): texto (497 KiB)
Primos frente e verso menores que 227 = 134.217.728 (999.227 termos): compactado (2,35 MiB)
Primos frente e verso menores que 231 = 2.147.483.648 (13.654.038 termos): compactado (34,1 MiB)Primos palíndromos
O conjunto dos primos palíndromos é um subconjunto dos primos frente e verso.
Primo palíndromo é um primo que quando lido de trás para frente representa o mesmo número.
Exemplo: 9.127.219 é primo e é palíndromo (lido de trás para frente fica igual: 9.127.219).
O adjetivo palíndromo se aplica também a palavras e frases, exemplos: "arara" e "socorram-me, subi no ônibus em marrocos"Os primeiros termos da sequência são:
2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929Verificar se um dado número pertence à essa sequência é fácil, basta verificar se ele é palíndromo e depois verificar se ele é primo
Se inverter(numero) = numero E numero for primo retorna verdadeiro Se não retorna falsoNo PHP fica:
<?php
function e_primo_palindromo($num) {
return strrev($num)==$num && e_primo($num);
}
?>Arquivo para download:
Primos palíndromos menores que 231 = 2.147.483.648 (5.953 termos): texto (56,3 KiB)Números figurados
Números figurados são aqueles que representam o número de pontos que formam uma determinada figura geométrica (confuso!). As sequências mais famosas são dos números quadrados e dos números cúbicos. Outra um pouco menos conhecida é a dos números triangulares.
Existem dezenas de sequências, cada uma é regida por uma fórmula geral. Veja abaixo algumas delas e as fórmulas correspondentes:Números triangulares (an = (n2 + n)/2):
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190
Números quadrados (an = n2):
1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289
Número pentagonais (an = (3n2 - n)/2):
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, 176, 210, 247, 287, 330, 376
Números hexagonais (an = 2n2 - n):
1, 6, 15, 28, 45, 66, 91, 120, 153, 190, 231, 276, 325, 378, 435, 496
Números cúbicos (an = n3):
1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, 2197, 2744Gerar os termos dessas sequências é fácil, basta usar a fórmula correspondente. Para avaliar se um dado número pertence à uma das sequências basta verificar se existe um n inteiro que corresponda ao número dado, ou seja, basta isolar n nas fórmulas acimas e avaliar se ele é inteiro.
Exemplos: para avaliar se um dado número (an) é quadrado basta verificar se √an é inteiro. A expressão para cada sequência é:
Números triangulares: n = (√(8an + 1) - 1)/2
Números quadrados: n = √an
Números pentagonais: n = (√(24an + 1) + 1)/6
Números hexagonais: n = (√(8an + 1) + 1)/4
Números cúbicos: n = 3√anArquivos para download:
Números triangulares menores que 231 = 2.147.483.648 (65.535 termos): texto (640 KiB)
Números quadrados menores que 231 = 2.147.483.648 (46.340 termos): texto (452 KiB)
Números pentagonais menores que 231 = 2.147.483.648 (37.837 termos): texto (369 KiB)
Números hexagonais menores que 231 = 2.147.483.648 (32.768 termos): texto (320 KiB)
Números cúbicos menores que 231 = 2.147.483.648 (1.290 termos): texto (12,0 KiB)Potências perfeitas
Potência perfeita é uma potência na forma mk onde m e k são naturais e maiores que 1.
Algumas potências perfeitas podem ser representadas de várias formas, exemplo: 64 = 26 = 43 = 82.
Duas sequências podem ser formadas com potências perfeitas: com repetição e sem repetição (veja os exemplos abaixo).
A soma dos inversos de todos os termos da sequência de potências perfeitas com repetição é igual a 1:
Potências perfeitas com repetição:
4, 8, 9, 16, 16, 25, 27, 32, 36, 49, 64, 64, 64, 81, 81, 100, 121, 125, 128, 144, 169, 196
Potências perfeitas sem repetição:
4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 128, 144, 169, 196, 216, 225, 243, 256, 289Gerar potências perfeitas é um pouco complicado. Primeiro tem de ser estabelecido um limite L e calcular o limite para a base m. Depois deve-se pegar todas as bases possíveis e, para cada uma, calcular o limite do expoente k e calcular mk para todos os valores possíveis de k, mantendo m fixo. Após todo esse processo, deve-se ordenar os resultados em ordem crescente.
Assim temos:
m ≤ √L
k ≤ log(L)/log(m)
Exemplo:limite := 1000 criar lista potenciasNo PHP fica:
Para m, começando em 2, indo até √limite e incrementando de 1 em 1 Para k, começando em 2, indo até log(limite)/log(m) e incrementando de 1 em 1 adicionar mk à potencias Ordenar potencias
<?php
$limite = 1000;
$potencias = array();
$m_max = sqrt($limite);
for ($m=2; $m<=$m_max; $m++) {
$k_max = log($limite)/log($m);
for ($k=2; $k<=$k_max; $k++)
$potencias[] = pow($m, $k);
}
sort($potencias);
?>Verificar se um dado número é uma potência perfeita também é um pouco complicado. Primeiro deve-se fatorar o número e depois calcular o MDC (máximo divisor comum) dos expoentes dos fatores, se esse valor for diferente de 1 então o número fornecido é uma potência perfeita.
Exemplos: 140 = 22 x 51 x 71; MDC(2, 1, 1) = 1 ⇒ 140 não é uma potência perfeita
216 = 23 x 33; MDC(3, 3) = 3 ⇒ 216 é uma potência perfeita (216 = 63).
Então teremos que criar duas funções de suporte (fatorar e mdc) e mais a função principal (e_potencia_perfeita):Funcao fatorar(numero) Se numero < 2 retornar lista(numero)No PHP fica:
criar lista fatores
max := √numero
Enquanto numero for divisível por 2
somar 1 à posição 2 de fatores
dividir numero por 2
i := 3
Enquanto numero ≠ 1 E i ≤ max
Se numero for divisível por i
somar 1 à posição i de fatores
dividir numero por i
Se não
adicionar 2 unidades à i
Se numero ≠ 1
adicionar 1 à posição numero de fatores
retornar fatores Funcao mdc(numeros)
Se quantidade numeros = 1
retorna 1º numero
Mas se quantidade numeros = 2
Divisor := maior dos numeros
resto := menor dos numeros
Enquanto resto ≠ 0
dividendo := Divisor
Divisor := resto
resto := resto da divisão dividendo/Divisor
retornar divisor
Se não
retornar mdc(lista(1º numero, mdc(restante dos numeros))) Funcao e_potencia_perfeita(numero)
fatores := fatorar(numero)
Se mdc(valores de fatores) ≠ 1
retorna verdadeiro
Se não
retorna falso
<?php
function fatorar($num) {
if ($num<2)
return array($num);
$fatores = array();
$max = sqrt($num);
while ($num%2 == 0) {
@$fatores[2]++;
$num /= 2;
}
$i = 3;
while ($num != 1 && $i<=$max)
if ($num%$i == 0) {
@$fatores[$i]++;
$num /= $i;
} else
$i += 2;
if ($num != 1)
@$fatores[$num]++;
return $fatores;
}
function mdc($nums) {
if (count($nums) == 1)
return $nums[0];
else if (count($nums) == 2) {
$D = max($nums);
$r = min($nums);
while ($r != 0) {
$d = $D;
$D = $r;
$r = $d%$D;
}
return $D;
} else
return mdc(array($nums[0], mdc(array_slice($nums, 1))));
}
function e_potencia_perfeita($num) {
$fatores = fatorar($num);
if (mdc(array_values($fatores)) != 1)
return true;
else
return false;
}
?>Arquivos para download:
Potências perfeitas menores que 231 = 2.147.483.648 com repetição (48.036 termos): texto (468 KiB)
Potências perfeitas menores que 231 = 2.147.483.648 sem repetição (47.687 termos): texto (465 KiB)Fatoriais
Fatorial é representado pelo ponto de exclamação e, para números naturais, é definido como:
Exemplo: 5! = 5x4x3x2x1 = 120
Por definição, 0! = 1
Também existe o duplo fatorial, exemplos: 7!! = 7x5x3x1 = 105; 8!! = 8x6x4x2 = 384As duas sequências crescem muito rapidamente e, portanto, apresentam poucos termos menores que 231. Todos eles estão apresentados a seguir:
Fatorial: 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600
Duplo fatorial: 1, 1, 2, 3, 8, 15, 48, 105, 384, 945, 3840, 10395, 46080, 135135, 645120, 2027025, 10321920, 34459425, 185794560, 654729075Gerar os termos das duas sequências é fácil, basta usar as fórmulas. Para verificar se um dado número pertence à uma das sequências basta gerar alguns termos e verificar se o número fornecido está entre eles. Esse processo é rápido pois são poucos termos.
Exemplo: verificar se 12345 representa um número fatorial. Primeiro deve-se gerar alguns termos da sequência, limitando-se a 12345: 1, 1, 2, 6, 24, 120, 720, 5040. Agora basta verificar se o número dado está entre os valores gerados. No caso, não.
Um outro método de verificar se um dado número é fatorial é dividir esse número por 2, 3, 4, ... obtendo quocientes inteiros, até chegar em 1.
Exemplo: verificar se 3628800 é um número fatorial. 3628800/2 = 1814400, tudo ok, continuando; 1814400/3 = 604800; 604800/4 = 151200; 151200/5 = 30240; 30240/6 = 5040; 5040/7 = 720; 720/8 = 90; 90/9 = 10; 10/10 = 1. Como todas as divisões foram exatas e obteve-se 1, então esse número é fatorial.
Outro exemplo: verificar 1234567890. 1234567890/2 = 617283945; 617283945/3 = 205761315; 205761315/4 = 51440328.75 ⇒ esse número não é fatorial.Arquivos para download:
Fatoriais menores que 231 = 2.147.483.648 (13 termos): texto (63 B)
Duplo fatoriais menores que 231 = 2.147.483.648 (20 termos): texto (104 B)Sequência de Fibonacci
Essa é uma sequência relativamente famosa, tem várias conexões com a natureza (colmeias, árvores, corpo humano, coelhos, etc) e apresenta várias propriedades interessantes. Essa sequência inicia com os termos 1, 1 e cada próximo termo é a soma dos dois anteriores, então o terceiro termo é 1+1 = 2, o quarto é 2+1 = 3. Essa sequência também cresce relativamente rápido.
A razão entre um termo e o anterior a ele se aproxima da razão áurea (φ = (√5+1)/2 ≈ 1,61803398874989484820) quando se usa termos cada vez maiores:
21/13 ≈ 1,61538
6.765/4.181 ≈ 1,6180339631
1.836.311.903/1.134.903.170 ≈ 1,61803398874989484785O início da sequência é:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765Para gerar o n-ésimo termo da sequência, pode ser usado o algoritmo abaixo:
Funcao fibonacci(n) antes2 := 0 antes := 0 agora := 1 Para i, começando em 2, indo até n e incrementando de 1 em 1 antes2 := antes antes := agora agora := antes + antes2 retorna agoraNo PHP fica:
<?php
function fibonacci($n) {
$antes2 = 0;
$antes = 0;
$agora = 1;
for ($i=2; $i<=$n; $i++) {
$antes2 = $antes;
$antes = $agora;
$agora = $antes+$antes2;
}
return $agora;
}
?>Para verificar se um dado número faz parte da sequência basta usar uma estratégia parecida com os número fatoriais: gerar a sequência e buscar pelo número.
Arquivo para download:
Termos da sequência menores que 231 = 2.147.483.648 (46 termos): texto (279 B)Triângulo de Pascal
Essa não é uma sequência como as outras apresentadas aqui, já que os termos não pertencem à mesma linha. Os termos dessa sequência devem ser dispostos na forma de um triângulo. Os termos são definidos pela fórmula:
Onde n é a linha onde o termo se encontra (começando em 0) e r é a coluna (começando em 0).
Cada linha começa com 1, termina com 1 e os outros termos são iguais à soma dos dois termos acima.O início do triângulo é:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 Gerar os termos do triângulo é fácil, basta usar a fórmula. Verificar se um dado número pertence ao triângulo também é fácil, já que todos os inteiros positivos estão presentes no triângulo. Por outro lado, encontrar a linha e a colução (ou seja, a posição) do termo é bem difícil. Alguns números aparecem várias vezes (ou infinitas, no caso do 1).
Arquivo para download:
Triângulo com todos os termos menores que 231 = 2.147.483.648 (34 linhas, 595 termos): texto (3,12 KiB)Trincas pitagóricas
Trinca pitagórica é um terno (três números) de inteiros (a, b, c) que satisfazem:
a2 + b2 = c2
a < b < c
Assim, cada trinca representa um triângulo retângulo de lados inteiros (catetos a, b e hipotenusa c)
Cada trinca pode gerar infinitas outras. Para isso basta multiplicar (a, b, c) por um inteiro k para obter (ak, bk, ck) que também é uma trinca pitagórica.
Quando mdc(a, b, c) = 1 dá-se o nome de trinca pitagórica primitiva, pois ela não foi obtida pelo processo acima (multiplicar uma trinca por um inteiro).As menores trincas pitagóricas, ordenando por a, são:
(3, 4, 5), (5, 12, 13), (6, 8, 10), (7, 24, 25), (8, 15, 17), (9, 12, 15), (9, 40, 41), (10, 24, 26), (11, 60, 61), (12, 16, 20), (12, 35, 37), (13, 84, 85), (14, 48, 50)
As menores trincas pitagóricas primitivas, ordenando por a, são:
(3, 4, 5), (5, 12, 13), (7, 24, 25), (8, 15, 17), (9, 40, 41), (11, 60, 61), (12, 35, 37), (13, 84, 85), (15, 112, 113), (16, 63, 65), (17, 144, 145), (19, 180, 181)Verificar se três inteiros dados formam uma trinca pitagórica é fácil, basta ordena-los e avaliar se o maior ao quadrado é igual à soma dos quadrados dos menores.
Existem vários métodos diferentes para se gerar trincas pitagóricas. O mais óbvio é chutar valores para (a, b, c) e verificar se a trinca é pitagórica. Logicamente esse método é extremamente demorado e impraticavel.
Uma otimização seria chutar valores para b, c; obter a de modo que a relação pitagórica seja válida e avaliar se o número a encontrado é inteiro e menor que os outros dois. Esse método é um pouco melhor, já que só serão chutados dois números e será obtido o menor deles (a), porém esse algoritmo é um pouco estranho quando se deseja encontrar todas as trincas pitagóricas até um certo limite.
O método que escolhemos para gerar os valores aqui apresentados foi encontrar b, c para um dado a:
a2 + b2 = c2
a2 = c2 - b2
a2 = (c + b)(c - b)
a2 = xy
O próximo passo é encontrar dois inteiros (x, y) tal que x > y > 0 e xy = a2. Feito isso, pode-se montar o sistema, resolver em b, c e verificar se b, c são naturais:
Perceba que x e y são divisores de a2, então para encontrar tais números temos que encontrar os divisores de a2 e, para isso, devemos fatorar a2.
Isso pode ser feito mais rapidamente se fatorarmos a e depois duplicarmos todos os expoentes.
Para gerar trincas primitivas basta seguir o mesmo caminho e no final, depois de encontrar b, c, verificar se mdc(a, b, c) = 1.
(Os algoritmos para fatorar um número e calcular o mdc já foram apresentados na sequência de potências perfeitas)Funcao divisores(fatores) criar lista divs adicionar 1 à divs Para cada fator e expoente de fatores Para cada divisor de divs Para i, começando em 1, indo até expoente e incrementando de 1 em 1 adicionar divisor*fatori à divs retorna divs Funcao gerar_trincas(a) criar lista trincas fatores := fatorar(a) Para cada fator e expoente de fatores dobrar expoente divs := divisores(fatores) Para cada divisor de divisores x := divisor Se x > a y := a2/x b := (x - y)/2 c := (x + y)/2 Se b > a E b for inteiro adicionar lista(a, b, c) à trincas retorna trincasNo PHP fica:
<?php
function divisores($fatores) {
$divs = array(1);
foreach ($fatores as $fator=>$exp)
foreach ($divs as $div)
for ($i=1; $i<=$exp; $i++)
$divs[] = $div*pow($fator, $i);
return $divs;
}
function gerar_trincas($a) {
$trincas = array();
$fatores = fatorar($a);
foreach ($fatores as $fator=>$exp)
$fatores[$fator] *= 2;
$divs = divisores($fatores);
foreach ($divs as $divisor) {
$x = $divisor;
if ($x>$a) {
$y = $a*$a/$x;
$b = ($x-$y)/2;
$c = ($x+$y)/2;
if ($b>$a && round($b) == $b)
$trincas[] = array($a, $b, $c);
}
}
return $trincas;
}
?>Arquivos para download:
Trincas pitagóricas com a, b, c menores que 215 = 32.768 (47.063 termos): texto (761 KiB)
Trincas pitagóricas com a, b, c menores que 219 = 524.288 (984.543 termos): compactado (7,00 MiB)
Trincas pitagóricas com a, b, c menores que 223 = 8.388.608 (19.454.697 termos): compactado (152 MiB)
Trincas pitagóricas primitivas com a, b, c menores que 215 = 32.768 (5.213 termos): texto (83,0 KiB)
Trincas pitagóricas primitivas com a, b, c menores que 219 = 524.288 (83.440 termos): compactado (663 KiB)
Trincas pitagóricas primitivas com a, b, c menores que 223 = 8.388.608 (1.335.078 termos): compactado (11,5 MiB)
Trincas pitagóricas primitivas com a, b, c menores que 227 = 134.217.728 (21.361.453 termos): compactado (221 MiB)Tamanho do período de 1/n
Algumas divisões não são exatas e formam dízimas periódicas, ou seja, uma parte decimal que se repete. O exemplo mais clássico é 1/3 = 0,333... O período é "3", ou seja, 1 dígito. Divisões exatas não tem período (1/8 = 0,125) e, portanto, o tamanho do período é zero.
Exemplos: 1/6 = 0,1666...; período = "6"; tamanho = 1
1/7 = 0,142857142857142857...; período = "142857"; tamanho = 6Os primeiros termos são:
0, 0, 1, 0, 0, 1, 6, 0, 1, 0, 2, 1, 6, 6, 1, 0, 16, 1, 18, 0, 6, 2, 22, 1, 0, 6, 3, 6, 28, 1, 15, 0, 2, 16, 6, 1, 3, 18, 6, 0, 5, 6, 21, 2, 1, 22, 46, 1, 42, 0, 16Existem várias formas de se gerar essa sequência, uma delas é calcular 1/n com várias casas decimais e buscar pelo período. Esse método é um pouco complicado, já que alguns períodos tem centenas de dígitos e, geralmente, a precisão usada nos cálculos do computador é de 14 algarismos significativos, ou seja, muito menor do que o necessário para encontrar certos períodos.
Outro método seria fazer a divisão normal (euclidiana) passo-a-passo e ir armazenando todos os restos encontrados, pois eles vão dizer a resposta: quando um valor do resto se repetir então a divisão vai entrar num ciclo e produzir os períodos:
Veja que o resto 3 repetiu na 2ª e 8ª divisão, então a 9ª divisão será igual à 3ª e assim por diante. Isso quer dizer que o período tem 8 - 2 = 6 dígitos.
- 1/7 = 0 resto 7
- 10/7 = 1 resto 3
- 30/7 = 4 resto 2
- 20/7 = 2 resto 6
- 60/7 = 8 resto 4
- 40/7 = 5 resto 5
- 50/7 = 7 resto 1
- 10/7 = 1 resto 3
Esse é o algoritmo:criar lista restos resto := 1 Enquanto resto não está em restos adiciona resto à restos resto := resto x 10 resto := resto da divisão de resto por numero Se resto = 0 retorna 0 retorna quatidade de restos - posição de resto em restosNo PHP fica:
<?php
function tamanho_periodo($n) {
$restos = array();
$resto = 1;
while (!in_array($resto, $restos)) {
$restos[] = $resto;
$resto *= 10;
$resto %= $n;
if ($resto == 0)
return 0;
}
return count($restos)-array_search($resto, $restos);
}
?>Arquivo para download:
Tamanho dos perídos de 1/n com n menor que 215 = 32.768 (32.767 termos): texto (134 KiB)
Tamanho dos perídos de 1/n com n menor que 219 = 524.288 (524.287 termos): compactado (1,08 MiB)