Fracción Frenzy!

9

EDITAR: Recibo muchos comentarios acerca de que esto no termina: le daré la etiqueta de "respuesta correcta" a la primera persona que me dé FF(3)(como lo proporciona en su respuesta) o prueba que FF(3)realmente explota indefinidamente.

Tarea:

Su tarea es hacer posible el programa más pequeño que genere la lista de recíprocos de la función Fraction Frenzy ( FF(n)) dado un entero positivo n.

Introducción:

Antes de poder introducir la función FF, primero tengo que explicar las fracciones egipcias.

Fracciones Egipcias:

Las fracciones egipcias son una forma de expresar fracciones como la suma de fracciones unitarias distintas, por lo que una forma de expresar la fracción 5/8es 1/2 + 1/8. No es otra suma de fracciones como

1/4 + 1/4 + 1/8
1/2 + 1/16 + 1/16

porque no todas sus fracciones son distintas ( 1/4se repite en el primer ejemplo y 1/16en el segundo).

En nuestra definición de fracciones egipcias, también incluimos el uso de denominadores negativos en las fracciones unitarias.

Función FF:

La función FF (Fraction Frenzy) se describe así:

FF(1)es la fracción egipcia 1/2 + 1/3 + 1/5 + 1/-30.

FF(2)es igual a FF(1)"multiplicado" por sí mismo ( FF(1)"cuadrado"):

  (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 no es una fracción egipcia totalmente reducida todavía, porque hay "repeticiones" en las fracciones. Para reducirlos, se realiza el siguiente procedimiento:

  1. Suma todas las fracciones unitarias "me gusta" juntas.
  2. Reduzca las sumas a sus formas más simples, por ejemplo, si una suma del paso 1es 2/6, eso se puede reducir a 1/3.
  3. Repita 1 y 2 hasta que todos los denominadores sean distintos: por ejemplo 1/2 + 2/3 + 1/5, en oposición a 1/2 + 1/3 + 1/3, que tiene un denominador repetitivo 3.
  4. Si hay un par de una fracción positiva y una negativa que tienen un valor absoluto igual, elimine ambas (por ejemplo, 1/-5y 1/5ambas deben eliminarse).
  5. Si las fracciones no son unidades y no se pueden reducir aún más, divídalas en fracciones unitarias con un denominador igual y mantenga una fracción como está. Con los otros, multiplican por FF(1): (1/2 + 1/3 + 1/5 + 1/-30).
  6. Repita los pasos del 1 al 5 hasta que la suma de la fracción final sea una fracción egipcia válida, es decir, todas las fracciones son distintas entre sí y todas son fracciones unitarias.

Esta es la reducción 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(excepto para 1), FF(n)se define por "cuadratura" FF(n-1).

Entrada y salida:

Dado un número entero n, debe generar una lista de todos los recíprocos de FF(n), ordenados en orden ascendente de sus 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]

Se le permite usar una cadena con cualquier delimitador, o la interpretación de una lista de su idioma, por lo que estas salidas son aceptables con la entrada 1:

2 3 5 -30   (Space-delimited)
2,3,5,-30   (Comma-delimited)
[2 3 5 -30] (Lisp-like lists)
etc. etc.

Especificaciones:

  • Debe generar los resultados de la FF(n)función exactamente como se especificó anteriormente.
  • Se le garantiza que la entrada será un número entero positivo: nunca estará por debajo de cero y nunca será un decimal (o fracción).

Este es el , por lo que gana el código más corto en bytes.

clismique
fuente
44
Por curiosidad, ¿se garantiza que esto terminará?
Martin Ender
Continuemos esta discusión en el chat .
clismique
Confirmo que FF (3) parece explotar. ¿No probó esto hasta aproximadamente FF (10) antes de publicar en el sandbox?
Peter Taylor
Continuemos esta discusión en el chat .
clismique
2
Las fracciones egipcias no tenían valores negativos en ellas, por lo que no es realmente una fracción egipcia.
mbomb007

Respuestas:

1

Haskell , 365 bytes

import Data.Function;import Data.List;import Data.Ratio;n=numerator;d=denominator
r=until=<<((==)=<<)$filter(/=0).map(sum).groupBy((==)`on`d).sortBy(compare`on`d)
p s=let(o,q)=span((<2).abs.n)s in case q of []->o;(a:b)->let j=a-1%d a*signum a in p.r$o++[a-j]++map(*j)e++b
s s=(*)<$>s<*>s;e=(1%)<$>[2,3,5,-30];f=iterate(p.r.s)e;o i=[abs(d q)*signum(n q)|q<-f!!(i-1)]

Pruébalo en línea!

Roman Czyborra
fuente
Hmm ... me encuentro con un bucle aparentemente infinito al dividir la no unidad más grande y volver a verificar en un momento como se presentó y ya lo había hecho al dividir la no unidad más pequeña a la izquierda hacia atrás o globalmente todas las no unidades antes de volver a verificar, pero tal vez debería ¿No dejará de elegir de manera no determinista las no unidades intermedias si uno cancela lo suficiente para alcanzar un FF finito (3)?
Roman Czyborra
Usar (1%)<$>[2,4,6,12]como 1 simplemente posterga la no determinación de FF (3) a FF (4) 😠
Roman Czyborra
(1%)<$>[2,3,10,15]o (1%)<$>[3,4,6,8,12,24]no produce ninguna mejora en absoluto 🤔
Roman Czyborra