# Fraction Frenzy!

EDIT: I'm getting a lot of comments about this not terminating - I will give the "correct answer" tag to either the first person who gives me FF(3) (as in provides it in their answer) or proves that FF(3) does indeed blow up indefinitely.

Your task is make the smallest program possible that generates the list of reciprocals of the Fraction Frenzy function (FF(n)) given a positive integer n.

## Introduction:

Before I can introduce the FF function, I have to first explain Egyptian fractions.

### Egyptian Fractions:

Egyptian fractions are a way of expressing fractions as the sum of distinct unit fractions - so one way to express the fraction 5/8 is 1/2 + 1/8. It is not other fraction sums like

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


because not all of their fractions are distinct (1/4 is repeated in the first example, and 1/16 in the second).

In our definition of Egyptian fractions, we are including the use of negative denominators in the unit fractions as well.

### FF function:

The FF (Fraction Frenzy) function is described like so:

FF(1) is the Egyptian fraction 1/2 + 1/3 + 1/5 + 1/-30.

FF(2) is equal to FF(1) "multiplied" by itself (FF(1) "squared"):

  (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


This is not a fully reduced Egyptian fraction yet, because there are "repeats" in fractions. To reduce them, the following procedure is done:

1. Sum all "like" unit fractions together.
2. Reduce the sums to their simplest forms - so for example, if a sum from step 1 is 2/6, that can be reduced to 1/3.
3. Repeat 1 and 2 until all denominators are distinct: for example, 1/2 + 2/3 + 1/5, as opposed to 1/2 + 1/3 + 1/3, which has a repeating denominator 3.
4. If there is a pair of one positive and one negative fraction that have an equal absolute value, remove both of them (e.g. 1/-5 and 1/5 must both be removed).
5. If fractions are not unit and cannot be reduced further, split it up into unit fractions with a equal denominator, and keep one fraction as it is. With the other ones, multiply them by FF(1): (1/2 + 1/3 + 1/5 + 1/-30).
6. Repeat steps 1-5 until the final fraction sum is a valid Egyptian fraction - i.e. all fractions are distinct from one another, and they are all unit fractions.

This is the reduction of 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)


For all n (except for 1), FF(n) is defined by "squaring" FF(n-1).

## Input and Output:

Given an integer n, you must output a list all of the reciprocals of FF(n), sorted in ascending order of their absolute values:

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]


You are allowed to use a string with any delimiter, or your language's interpretation of a list, so these outputs are all acceptable with the input 1:

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


## Specs:

• You must output the results of the FF(n) function exactly as specified above.
• You are guaranteed that the input will be a positive integer - it will never be below zero, and it will never be a decimal (or fraction).

This is , so shortest code in bytes wins!

• Out of curiosity, is this guaranteed to terminate? – Martin Ender Feb 8 '17 at 7:59
• – clismique Feb 8 '17 at 9:31
• I confirm that FF(3) seems to blow up. Did you not test this up to about FF(10) before posting to the sandbox? – Peter Taylor Feb 8 '17 at 10:46
• – clismique Feb 8 '17 at 10:58
• Egyptian fractions didn't have negative values in them, so it's not really an Egyptian fraction. – mbomb007 Feb 8 '17 at 15:51

import Data.Function;import Data.List;import Data.Ratio;n=numerator;d=denominator
r=until=<<((==)=<<)$filter(/=0).map(sum).groupBy((==)ond).sortBy(compareond) 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)]

• Using (1%)<$>[2,4,6,12] as 1 merely procrastinates the nontermination from FF(3) to FF(4) 😠 – Roman Czyborra Feb 12 '17 at 17:49 • (1%)<$>[2,3,10,15] or (1%)<\$>[3,4,6,8,12,24] yield no improvement at all 🤔 – Roman Czyborra Feb 12 '17 at 18:13