9
\$\begingroup\$

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!

\$\endgroup\$
12
  • 4
    \$\begingroup\$ Out of curiosity, is this guaranteed to terminate? \$\endgroup\$ Feb 8, 2017 at 7:59
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$
    – clismique
    Feb 8, 2017 at 9:31
  • \$\begingroup\$ I confirm that FF(3) seems to blow up. Did you not test this up to about FF(10) before posting to the sandbox? \$\endgroup\$ Feb 8, 2017 at 10:46
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$
    – clismique
    Feb 8, 2017 at 10:58
  • 2
    \$\begingroup\$ Egyptian fractions didn't have negative values in them, so it's not really an Egyptian fraction. \$\endgroup\$
    – mbomb007
    Feb 8, 2017 at 15:51

1 Answer 1

1
\$\begingroup\$

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!

\$\endgroup\$
3
  • \$\begingroup\$ 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)? \$\endgroup\$ Feb 12, 2017 at 17:19
  • \$\begingroup\$ Using (1%)<$>[2,4,6,12] as 1 merely procrastinates the nontermination from FF(3) to FF(4) 😠 \$\endgroup\$ Feb 12, 2017 at 17:49
  • \$\begingroup\$ (1%)<$>[2,3,10,15] or (1%)<$>[3,4,6,8,12,24] yield no improvement at all 🤔 \$\endgroup\$ Feb 12, 2017 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.