9
3
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!
4Out of curiosity, is this guaranteed to terminate? – Martin Ender – 2017-02-08T07:59:07.980
Let us continue this discussion in chat.
– clismique – 2017-02-08T09:31:48.593I 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 – 2017-02-08T10:46:09.643
Let us continue this discussion in chat.
– clismique – 2017-02-08T10:58:46.150until all reciprocals are distinct
-- Can you clarify what this means? – smls – 2017-02-08T12:07:23.073until the final fraction sum is a valid Egyptian fraction
-- This too. The example suggests that step 4 has to be applied again if it causes a change, even though that's not part of the stated definition of an Egyptian fraction. Maybe you mean "until it doesn't change anymore", in both cases? – smls – 2017-02-08T13:26:20.250F(3) doesn't appear to terminate for me, either. See here for my non-golfed program and its debug output, written under the assumption that we need to iterate until it doesn't change anymore.
– smls – 2017-02-08T15:35:59.4202Egyptian fractions didn't have negative values in them, so it's not really an Egyptian fraction. – mbomb007 – 2017-02-08T15:51:06.117
@mbomb007 Fixed as well. – clismique – 2017-02-09T07:02:12.510
@smls Finished editing for both of your queries. – clismique – 2017-02-09T07:08:04.707
I think step 6, as written, still doesn't explain why step 4 (canceling out negatives) is performed at the end of the reduction of
FF(2)
, since the result of previous step 5 already consisted of distinct unit fractions - just not with distinct absolute values. – smls – 2017-02-09T11:19:08.250@smls Yeah... didn't put that in, nice catch. – clismique – 2017-02-09T19:31:07.853