[obm-l] K-ésimo número da sequência: A Ressurreição

[Helder Suzuki <heldersuzuki@xxxxxxxxxxxx>]

matteus barreto escreveu:
>Sera que alguem  poderia me sugerir, se nao uma forma
>fechada, um passo a passo (um algoritmo) para se
>encontrar o k-esimo numero da sequencia:
>
>    1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15..., ou seja,
os
>números da forma (2^a)*(3^b)*(5^c), com a, b, c
>pertencentes ao conjunto dos inteiros nao negativos.
>Ja pensei bastante a respeito mas sem resultados mais
>concludentes.

Olá a todos!

Me deparei recentemente com um problema de informática
exatamente igual a este problema, consistia em
encontrar o k-ésimo número da sequencia dado k.
(também encontrei outro que pedia o mesmo, mas para
uma sequencia com (a1^b1)*(a2^b2)*...*(an^bn), dado
a1, a2, ..., an primos e k)

O primeiro algorítimo que me veio a cabeça é bem
simples, consiste em varrer os números a partir do 1 e
verificar se o número pertence a sequencia,
verificando se contém fatores primos diferentes de 2,
3 e 5.
A complexidade de tempo desse algorítimo é muito
parecida com a do algorítimo semelhante para achar
números primos.

Este primeiro algorítimo gastou cerca de 2 horas (aqui
no meu computador) para encontrar o 1500-ésimo número
da sequencia, e o programa de correção de problemas
simplesmente deu timeout (o máximo de tempo permitido
é 5 segundos, em um pentium 700).
Tempo: O(t^k), para algum t
Espaço: O(constante)

O segundo algorítimo foi feito explorando uma
propriedade dos números dessa sequencia.
é observável que:
A(i) = A(k)*n,
para algum k tal que 1 <= k < i, e n = 2, 3 ou 5. 

Se conhecemos o valor de A(i-1), A(i-2), ..., A(1)
podemos obter A(i) em menos de i passos.
Basta tentar achar o n(2, 3 ou 5) e achar k(1<=k<i),
tal que A(k)*n é mínimo.(A(i)=A(k)*n)

Sabendo que A(1) = 1, podemos achar A(2).
Sabendo A(1) e A(2), achamos A(3).
....
achamos finalmente A(k).

Este algorítimo encontrou o 1500-ésimo elemento em
cerca de 12 milisegundos, mas necessitara de espaço
para armazenar todos os 1499 elementos necessários
para calcular o 1500.

Tempo: O(k^2)
Espaço: O(K)


Grato,
Helder Toshiro Suzuki

_______________________________________________________________________
Yahoo! Mail
O melhor e-mail gratuito da internet: 6MB de espaço, antivírus, acesso POP3, filtro contra spam. 
http://br.mail.yahoo.com/
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================