Concurso/Encontro Nacional de Programação em Lógica
CeNPL’02
Universidade de
Coimbra / Instituto Politécnico de Coimbra
11-13 de Abril de
2002
Problema nº 8
QUASE
Introdução
Nós, os da
informática, somos bons em potências de 2. Todos sabemos que 210 é
1024 e que com quatro bytes podemos representar números inteiros entre
–231 e 231-1, ou seja, entre cerca de menos dois mil
milhões e cerca de mais dois mil milhões.
Também sabemos
que o único factor primo de uma potência de 2 é 2. Logo, todos os divisores de
uma potência de 2 são potências de 2. Claro, dirá você. Mas então vejamos isto
sob uma perspectiva diferente. Dado um número inteiro positivo x, será que existe uma potência de 2 da qual x é “quase” um divisor? Por definição, diremos que
um número inteiro x maior que 1 é quase
divisor de y se x
for divisor de y ou x
for divisor de y + 1 ou x
for divisor de y – 1. (Repare que o problema
só tem interesse se desconsiderarmos a potência de expoente zero, 20,
pois todos os números inteiros positivos seriam quase divisores de 1.)
Pois bem, um
momento de reflexão mostra que se x for ímpar,
então sim, existe uma potência de 2 da qual x
é quase divisor. De facto, existindo uma, existe uma infinidade, mas estamos
interessados apenas na menor de todas. Qual será ela, para um dado x?
Escreva um programa Prolog quase(+X, -N) que, dado um número inteiro X ímpar, instancie N com o expoente da menor potência de 2 tal que X é quase divisor de 2N. O número representado por X pertence ao intervalo 21+1..109-1.
O programa será invocado através do predicado
quase(X, N)
que deverá ter o primeiro argumento instanciado com um inteiro pertencente
ao intervalo 21+1..109-1.
O programa deverá instanciar N, o segundo argumento, com o expoente da menor potência de 2 tal que X é quase divisor de 2N.
?- quase(5, N).
N = 2
Yes
Correcto: 22 = 4 e 5 é um divisor de 4 + 1.
?- quase(25, N).
N = 10
Yes
Correcto: 210 = 1024 e 25 é um divisor de 1024 + 1.
?- quase(2001, N).
N = 308
yes
?- quase(999999999, N).
N = 667332
yes