[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] k-esimo numero da sequencia
Caro Matteus:
Infelizmente tenho que admitir que o algoritmo abaixo está furado. Ele
produz uma sequência crescente de números da forma desejada, mas não todos
eles - de fato, ele produz a sequência 1, 2, 4, 8, 16,.....
Eu pensei um pouco mais sobre o problema e cheguei à conclusão de que é bem
mais difícil do que eu imaginava.
Por exemplo, com o caso mais simples - nos. da forma 2^a * 3^b, a sequência
será:
N 1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72
a 0 1 0 2 1 3 0 2 4 1 3 0 5 2 4 1
6 3
b 0 0 1 0 1 0 2 1 0 2 1 3 0 2 1 3
0 2
Repare que a sequência de pares (a,b) que produzem todos os N em ordem
crescente não parece obedecer nenhuma lei de formação óbvia.
Por enquanto, só o que dá pra sugerir é um algoritmo extremamente
ineficiente que toma cada número natural, remove os fatores 2, 3 e 5 e, se
estes forem os únicos fatores, adiciona este número à sequência. Em seguida
toma o número natural seguinte, e assim por diante.
Problema interessante. Vou pensar mais um pouco.
Um abraço,
Claudio
----- Original Message -----
From: "Cláudio (Prática)" <claudio@praticacorretora.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Tuesday, February 04, 2003 8:37 AM
Subject: Re: [obm-l] k-esimo numero da sequencia
Caro Matteus:
O algoritmo abaixo cria uma sequência X tal que X(1) = 1 ( = 2^0 * 3^0 *
5^0 ) e X(N) = N-ésimo inteiro positivo da forma 2^a * 3^b * 5^c. A
ordenação é a usual (m < n <==> X(m) < X(n) )
"Input" N
a = 0
b = 0
c = 0
K = 1
(***) X(K) = 1
P = 2^(a+1) * 3^b * 5^c
Flag = 1
Se P > 2^a * 3^(b+1) * 5^c então ( P = 2^a * 3^(b+1) * 5^c e Flag =
2 )
Se P > 2^a * 3^b * 5^(c+1) então ( P = 2^a * 3^b * 5^(c+1) e Flag =
3 )
Se Flag = 1 então a = a+1
Se Flag = 2 então b = b+1
Se Flag = 3 então c = c+1
K = K+1
Se K <= N então Retorna para (***)
Fim
Espero que isso ajude.
Um abraço,
Claudio.
----- Original Message -----
From: "matteus barreto" <matteusbarreto@yahoo.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Monday, February 03, 2003 6:04 PM
Subject: [obm-l] k-esimo numero da sequencia
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.
_______________________________________________________________________
Busca Yahoo!
O serviço de busca mais completo da Internet. O que você pensar o Yahoo!
encontra.
http://br.busca.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>
=========================================================================
=========================================================================
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>
=========================================================================
=========================================================================
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>
=========================================================================