De acordo com o site Wolfram Math (http://mathworld.wolfram.com/Squarefree.html), não se conhece nenhum algoritmo em tempo polinomial (polynomial time) para determinar se um dado número é livre de quadrados ou não. O problema que você sugere parece ser ainda mais difícil, porque para encontrar o N-ésimo número livre se teria primeiro que determinar que tal número é de fato livre, de modo que eu suspeito que a resposta à sua pergunta seja negativa. O mesmo site dá um resultado de Landau com uma fórmula assintótica para o número Q(n) de inteiros <= n que sejam livres de quadrados: Q(n) = 6n/(Pi^2) + O(n^(1/2)). Portanto, se você precisar somente de um resultado aproximado, esta fórmula ajuda. Abraços, Domingos _____
From: [email protected] [mailto:[email protected]] On Behalf Of Rhilbert Rivera Sent: Saturday, August 28, 2010 8:57 AM To: [email protected] Subject: [obm-l] Livres de Quadrados Amigos, Existe uma categoria de números inteiros positivos apelidada de "números livres de quadrados perfeitos maiores que 1" como sendo aqueles que não possuem nenhum tipo de quadrado perfeito em sua decomposição em fatores primos. Por exemplo, a sequência dos primeiros "números livres" então seria: 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, ... O problema consiste em encontrar o N-ésimo "número livre", sendo que N pode assumir valores extraordinariamente grandes como N = 2 * (10 elevado a 10). Minha pergunta é, se não há uma maneira mais rápida e direta de se encontrar o N-ésimo número livre sem ter que encontrar antes os N - 1 números livres anteriores, pois até com computadores acho que é complicado contar tantos elementos assim. Obrigado (- _ -) [ ]'s
