Re: [obm-l] k-esimo numero da sequencia

Cara de boa,isto e dificil...Um problema da OMR pedia pra provar que o troço tinha termos cada vez mais longe entre si.E nao tive nenhum lampejo de ideias.

>From: "Cláudio \(Prática\)"

>Reply-To: obm-l@mat.puc-rio.br

>To:

>Subject: Re: [obm-l] k-esimo numero da sequencia

>Date: Wed, 5 Feb 2003 18:30:35 -0200

>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)"

>To:

>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"

>To:

>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 é

>=========================================================================

>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 é

>=========================================================================

>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 é

>=========================================================================