[Desafio] Fracções

[Warrior 68]

No outro dia deparei-me com um problema interessante e decidi partilhar. Não é propriamente fácil mas como tem motivação histórica achei curioso.

Há muitos desafios que nos pedem para recuperarmos fracções tendo por base a sua representação decimal.

A verdade é que a divisão de dois números A e B pode dar origem a uma dízima infinita com um período que pode ir no máximo até B. Por exemplo 1/7 = 0,142857 142857 142857... Recuperar 1/7 tendo este período já foi colocado como desafio no forum várias vezes (por exemplo aqui).

Algo que menos pessoas sabem é que, tendo o resultado de uma fracção A/B, é possível recuperar eficientemente A e B se descobrirmos os primeiros NA+NB+1 dígitos. Ou seja, se nos disserem que o dividendo tem NA dígitos e o divisor NB, então podemos recuperar a fracção inicial muito rapidamente. No caso do 1/7, bastam-nos os 3 dígitos 142.

O desafio é esse mesmo. Como recuperar A e B conhecendo só parte da representação decimal?

Portanto eu pergunto, qual é a fracção A/B, com A e B de 5 dígitos cada, cuja representação decimal inicia com este número "16764004988"? Que método é que pode ser usado para o descobrir, sem recorrer ao computador?

Contexto: ZAPMAIL

Antes do Fax se ter difundido, a FedEx procurou instalar um serviço de entrega de correspondência mais rápido para as empresas. Os documentos eram digitalizados nos correios e enviados pela rede para outra estação FedEx que os imprimia e entregava no destinatário no mesmo dia. As empresas conseguiam entregar os documentos mais rapidamente e a FedEx poupava somas significativas ao reduzir a frota de transportes. (Este sistema foi descontinuado com elevados prejuízos quando poucos anos mais tarde o Fax se espalhou e as empresas não estavam dispostas a pagar para um serviço que tinham gratuito)

Uma das primeiras preocupações foi a forma como poderiam encriptar os documentos pela rede. A proposta foi terem os dois terminais a escolherem dois números co-primos A e B, obterem a divisão A/B e com o seu resultado em binário fazerem XORs no documento, encriptando-o. Na outra extremidade, e conhecendo-se o mesmo A e B, a operação podia ser revertida aplicando exactamente o mesmo processo.

Infelizmente os documentos por vezes continham espaços em branco consecutivos, sendo possível recuperar uma parte do resultado da divisão. Mais tarde se demonstrou que com B números consecutivos se conseguia quebrar a encriptação e este método foi abandonado.

Edited April 4, 2014 by Warrior

[Warrior 68]

Edit: mudado para os primeiros nA+nB+1 dígitos.

[Pedro Ribeiro I 4]

Deveras interessante. Sorry for the bump, mas isto é deveras interessante

[Warrior 68]

Oh, nunca mais me lembrei de colocar aqui a solução..

Vou ver se arranjo um tempo para escrevê-la.

[Pedro Ribeiro I 4]

Se faz favor Warrior. Hoje vou tentar resolver

[Pedro Ribeiro I 4]

Bem, hoje em química descobri como achar o B, falta-me o A. Sem computador só fiz para números com um dígito, não sei como funciona com mais dígitos. Vou continuar a ver e depois digo algo. Obrigado pelo desafio Warrior

[Pedro Ribeiro I 4]

Afinal, não funciona xb funciona apenas em casos limitados...

[Warrior 68]

Ok, já passou demasiado tempo desde o post inicial, não vou entrar em grandes detalhes nesta explicação mas não hesitem em perguntar se não tiver ficado claro.

O problema é aparentemente simples, temos um número X = A/B e sabemos que X = 0.16764004988... Queremos então encontrar A e B, cada um com no máximo 5 dígitos.

Isto é a mesma coisa do que perguntar qual é a melhor aproximação de X usando uma fracção com até 5 dígitos no numerador e denominador.

A resposta rápida é: podemos obter a resposta usando fracções contínuas. É um conceito bastante simples mas que normalmente não é muito abordado.

Começamos com o nosso número X. Uma coisa evidente que nós sabemos, é que:

Mas sendo X = 0.16764004988.., podemos substituir X na expressão acima:

E agora temos o mesmo problema. Qual a melhor forma de representar 5.965161.. utilizando uma fracção? Podemos representar aquele número através da parte inteira + 1/parte_decimal:

E o problema repete-se novamente: qual a melhor forma de representar 1.0360958..? Podemos repetir o passo anterior inúmeras vezes. Obteríamos algo deste género:

Podemos ver facilmente porque motivo estas fracções se chamam fracções contínuas, porque se encadeiam continuamente umas nas outras.

A questão aqui é: quão próximos de X estamos neste momento? Se ignorarmos as "reticências", podemos descobrir que

Estamos perto de 0.16764004988, mas ainda não estamos lá! De qualquer modo, A e B ainda só têm 3 dígitos no máximo. O enunciado diz que podiam ir até 5. Para não se ocuparem páginas a escrever fracções na vertical, uma outra notação surgiu para representar fracções contínuas. A fracção anterior pode ser representada por [0; 5, 1, 27, 1, 2]. Muito mais compacto. O curioso sobre as fracções contínuas é que elas garantem que são a melhor aproximação até àquele denominador. Ou seja, 86/513 é a melhor aproximação de 0.16764004988 entre todas as fracções com denominador <= 513.

Se continuarem o processo anterior, a fracção contínua que melhor descreve o nosso X é [0;5,1,27,1,2,2,1,1,1,3,1,2,1]. Se calcularem a fracção que representa, verão que obtêm 13577/80989 = 0.167640049883.. Começa com o nosso valor de X!

Se quisessem prolongar a fracção, veriam que o próximo valor na sequência seria 45. Contudo, [0;5,1,27,1,2,2,1,1,1,3,1,2,1,45] = 620954/3704091 . Claramente fora dos 5 dígitos pedidos no problema!

Este processo pode parecer muito moroso, mas é extremamente rápido de efectuar numa calculadora. Só têm de retirar a parte inteira ao resultado e dividir 1 por esse valor.

As fracções contínuas têm muitas outras propriedades interessantes na representação de números. Todos os números racionais possuem uma fracção contínua finita. As fracções contínuas infinitas são nada mais do que soluções irracionais de equações quadradas (por exemplo, raiz quadrada de 3).

[Pedro Ribeiro I 4]

Muito interessante... obrigado Warrior, vou tentar estudar isto