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.
Task:
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:
- Sum all "like" unit fractions together.
- Reduce the sums to their simplest forms - so for example, if a sum from step
1
is2/6
, that can be reduced to1/3
. - Repeat 1 and 2 until all denominators are distinct: for example,
1/2 + 2/3 + 1/5
, as opposed to1/2 + 1/3 + 1/3
, which has a repeating denominator3
. - 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
and1/5
must both be removed). - 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)
. - 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 code-golf, so shortest code in bytes wins!