Fraction Frenzy!

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:

  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!

clismique

Posted 2017-02-08T07:32:18.797

Reputation: 6 600

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.593

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 – 2017-02-08T10:46:09.643

Let us continue this discussion in chat.

– clismique – 2017-02-08T10:58:46.150

until all reciprocals are distinct -- Can you clarify what this means? – smls – 2017-02-08T12:07:23.073

until 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.250

F(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.420

2Egyptian 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

Answers

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)]

Try it online!

Roman Czyborra

Posted 2017-02-08T07:32:18.797

Reputation: 604

Hmm… i run into an apparently infinite loop when splitting the largest non-unit and rechecking at a time as presented and had already done so when splitting the smallest non-unit in leftwards reverse or globally all non-units before rechecking but perhaps i should not fail to nondeterministically pick non-units from in between whether one cancels out enough others to reach a finite FF(3)? – Roman Czyborra – 2017-02-12T17:19:48.233

Using (1%)<$>[2,4,6,12] as 1 merely procrastinates the nontermination from FF(3) to FF(4) – Roman Czyborra – 2017-02-12T17:49:00.343

(1%)<$>[2,3,10,15] or (1%)<$>[3,4,6,8,12,24] yield no improvement at all – Roman Czyborra – 2017-02-12T18:13:00.423