EDIT: Estou recebendo muitos comentários sobre isso não terminando - darei a tag "resposta correta" para a primeira pessoa que me FF(3)
fornecer (como fornece na resposta) ou comprova que FF(3)
, de fato, explode indefinidamente.
Tarefa:
Sua tarefa é tornar o menor programa possível que gere a lista de recíprocos da função Fraction Frenzy ( FF(n)
), dado um número inteiro positivo n
.
Introdução:
Antes de poder introduzir a função FF, preciso primeiro explicar as frações egípcias.
Frações egípcias:
As frações egípcias são uma maneira de expressar frações como a soma de frações unitárias distintas - então, uma maneira de expressar a fração 5/8
é 1/2 + 1/8
. Não são outras somas de fração como
1/4 + 1/4 + 1/8
1/2 + 1/16 + 1/16
porque nem todas as frações são distintas ( 1/4
é repetida no primeiro exemplo e 1/16
no segundo).
Em nossa definição de frações egípcias, estamos incluindo o uso de denominadores negativos nas frações unitárias.
Função FF:
A função FF (Fraction Frenzy) é descrita assim:
FF(1)
é a fração egípcia 1/2 + 1/3 + 1/5 + 1/-30
.
FF(2)
é igual a FF(1)
"multiplicado" por si só ( FF(1)
"ao quadrado"):
(1/2 + 1/3 + 1/5 + 1/-30)(1/2 + 1/3 + 1/5 + 1/-30)
= 1/4 + 1/6 + 1/10 + 1/-60 + 1/6 + 1/9 + 1/15 + 1/-90 +
1/10 + 1/15 + 1/25 + 1/-150 + 1/-60 + 1/-90 + 1/-150 + 1/900
Esta ainda não é uma fração egípcia totalmente reduzida, porque há "repetições" em frações. Para reduzi-los, o seguinte procedimento é feito:
- Soma todas as frações de unidade "like" juntas.
- Reduza as somas para as formas mais simples - por exemplo, se uma soma da etapa
1
for2/6
, isso pode ser reduzido para1/3
. - Repita 1 e 2 até que todos os denominadores sejam distintos: por exemplo
1/2 + 2/3 + 1/5
, ao contrário de1/2 + 1/3 + 1/3
, que possui um denominador repetitivo3
. - Se houver um par de uma fração positiva e uma fração negativa que tenham um valor absoluto igual, remova os dois (por exemplo,
1/-5
e1/5
devem ser removidos). - Se as frações não forem unitárias e não puderem ser reduzidas ainda mais, divida-as em frações unitárias com um denominador igual e mantenha uma fração como está. Com os outros, multiplicá-los por
FF(1)
:(1/2 + 1/3 + 1/5 + 1/-30)
. - Repita as etapas 1 a 5 até que a soma da fração final seja uma fração egípcia válida - ou seja, todas as frações são distintas uma da outra e todas são frações unitárias.
Esta é a redução de FF(2)
:
1/4 + 1/6 + 1/10 + 1/-60 + 1/6 + 1/9 + 1/15 + 1/-90 +
1/10 + 1/15 + 1/25 + 1/-150 + 1/-60 + 1/-90 + 1/-150 + 1/900
= 1/4 + 2/6 + 1/9 + 2/10 + 2/15 + 1/25 + 2/-60 + 2/-90 + 2/-150 + 1/900 (step 1)
= 1/4 + 1/3 + 1/9 + 1/5 + 2/15 + 1/25 + 1/-30 + 1/-45 + 1/-75 + 1/900 (step 2)
= 1/3 + 1/4 + 1/5 + 1/9 + 1/15 + 1/15(1/2 + 1/3 + 1/5 + 1/-30) + (step 5)
1/25 + 1/-30 + 1/-45 + 1/-75 + 1/900
= 1/3 + 1/4 + 1/5 + 1/9 + 1/15 + 1/30 + 1/45 + 1/75 + 1/-450 +
1/25 + 1/-30 + 1/-45 + 1/-75 + 1/900
= 1/3 + 1/4 + 1/5 + 1/9 + 1/15 + 1/25 + 1/-450 + 1/900 (step 4)
Para todos n
(exceto 1
), FF(n)
é definido por "quadrado" FF(n-1)
.
Entrada e saída:
Dado um número inteiro n
, você deve exibir uma lista de todos os recíprocos de FF(n)
, classificados em ordem crescente de seus valores absolutos:
1 -> [2, 3, 5, -30]
# 1/2 + 1/3 + 1/5 + 1/-30 = FF(1), reciprocals = [2, 3, 5, -30]
2 -> [3, 4, 5, 9, 15, 25, -450, 900]
Você tem permissão para usar uma string com qualquer delimitador ou a interpretação de uma lista no seu idioma, portanto, essas saídas são aceitáveis com a entrada 1
:
2 3 5 -30 (Space-delimited)
2,3,5,-30 (Comma-delimited)
[2 3 5 -30] (Lisp-like lists)
etc. etc.
Especificações:
- Você deve gerar os resultados da
FF(n)
função exatamente como especificado acima. - Você tem a garantia de que a entrada será um número inteiro positivo - nunca será abaixo de zero e nunca será um decimal (ou fração).
Isso é código-golfe , então o código mais curto em bytes vence!
fonte
Respostas:
Haskell , 365 bytes
Experimente online!
fonte
(1%)<$>[2,4,6,12]
como um meramente procrastinates o nontermination de FF (3) a FF (4) 😠(1%)<$>[2,3,10,15]
ou(1%)<$>[3,4,6,8,12,24]
produzir nenhuma melhoria em tudo 🤔