10
\$\begingroup\$

Background

From Wikipedia: An Egyptian fraction is the sum of distinct unit fractions. That is, each fraction in the expression has a numerator equal to 1 and a denominator that is a positive integer, and all the denominators differ from each other. The value of an expression of this type is a positive rational number a/b. Every positive rational number can be represented by an Egyptian fraction.

Task

Write a function that given \$ n \$, outputs the longest sequence of Egyptian fractions (that sum up to 1) where \$ n \$ is the largest denominator.

Rules

  • If no solution exists, you may output anything or nothing except any real number
  • If there are two or more solutions, output any one of them
  • Assume \$ n \$ is not two and is a natural number
  • Your output must be in descending order
  • You must not output duplicates
  • Each individual fraction must be separated by a plus symbol (+). Spaces are optional. However the plus symbol should not come after the last fraction.
  • Your code does not need to practically handle very high \$ n \$, but it must work in theory for all \$ n \$ for which a solution exists
  • You may use any standard I/O method
  • Standard loopholes are forbidden

Examples

61/2 + 1/3 + 1/6

151/3 + 1/4 + 1/6 + 1/10 + 1/12 + 1/15

20:

1/4 + 1/5 + 1/6 + 1/9 + 1/10 + 1/15 + 1/18 + 1/20

or

1/3 + 1/5 + 1/9 + 1/10 + 1/12 + 1/15 + 1/18 + 1/20

2016:

1/15 + 1/22 + 1/24 + 1/25 + 1/30 + 1/32 + 1/33 + 1/39 + 1/40 + 1/42 + 1/44 + 1/45 + 1/48 + 1/55 + 1/56 + 1/60 + 1/63 + 1/64 + 1/65 + 1/66 + 1/70 + 1/72 + 1/78 + 1/80 + 1/84 + 1/85 + 1/88 + 1/90 + 1/91 + 1/96 + 1/99 + 1/104 + 1/110 + 1/112 + 1/119 + 1/120 + 1/130 + 1/132 + 1/135 + 1/136 + 1/150 + 1/154 + 1/156 + 1/160 + 1/165 + 1/168 + 1/170 + 1/171 + 1/175 + 1/180 + 1/182 + 1/184 + 1/189 + 1/190 + 1/195 + 1/198 + 1/200 + 1/208 + 1/210 + 1/220 + 1/225 + 1/230 + 1/238 + 1/240 + 1/260 + 1/270 + 1/272 + 1/275 + 1/288 + 1/299 + 1/300 + 1/306 + 1/320 + 1/324 + 1/325 + 1/330 + 1/340 + 1/345 + 1/368 + 1/400 + 1/405 + 1/434 + 1/459 + 1/465 + 1/468 + 1/476 + 1/480 + 1/495 + 1/496 + 1/527 + 1/575 + 1/583 + 1/672 + 1/765 + 1/784 + 1/795 + 1/810 + 1/840 + 1/875 + 1/888 + 1/900 + 1/918 + 1/920 + 1/975 + 1/980 + 1/990 + 1/1000 + 1/1012 + 1/1050 + 1/1088 + 1/1092 + 1/1100 + 1/1104 + 1/1113 + 1/1125 + 1/1196 + 1/1200 + 1/1224 + 1/1258 + 1/1309 + 1/1330 + 1/1386 + 1/1395 + 1/1425 + 1/1440 + 1/1470 + 1/1480 + 1/1484 + 1/1488 + 1/1512 + 1/1620 + 1/1650 + 1/1680 + 1/1728 + 1/1729 + 1/1800 + 1/1824 + 1/1836 + 1/1840 + 1/1848 + 1/1850 + 1/1870 + 1/1890 + 1/1950 + 1/1980 + 1/1995 + 1/2000 + 1/2016

or

...

Criteria

  1. For first place: shortest code in bits wins

  2. For second place: fastest code wins.

    So if a code is the shortest and fastest, the second fastest code will be given 2nd place

P.S: The background definition and some rules are taken from this and this question respectively.

\$\endgroup\$
8
  • 5
    \$\begingroup\$ Nice first challenge! Some suggestions: from the testcases, it seems like \$n\$ has to be the greatest denominator, and they don't have to be consecutive — you should clarify that in the challenge text. Additionally, I'd suggest having a looser output format — I don't see why we can't output as [2,3,6], for example, or why the order is important. For the scoring criteria, saying "shortest code wins, with time as tiebreaker" would be clearer. You should ... \$\endgroup\$ Sep 30, 2023 at 11:54
  • 4
    \$\begingroup\$ (cont.) clarify on which tests the speed is determined. It's quite unlikely that a language will have two solutions with the same length but significantly different time, so the tiebreaker might not be relevant. I suggest first posting challenges to the sandbox in the future \$\endgroup\$ Sep 30, 2023 at 11:54
  • 3
    \$\begingroup\$ @CommandMaster Thank you for your valuable feedback. I have changed the framing to remove 'consecutive' as it is not required. For the scoring criteria, I have omitted the tiebreaker part. Also I agree for you on the output format, but someone has already submitted an answer so its too late now, but I will keep that in mind. Thank you for bringing my attention to the sandbox. \$\endgroup\$
    – Anm
    Sep 30, 2023 at 13:15
  • \$\begingroup\$ Perhaps worth mentioning that 1/3 + 1/5 + 1/9 + 1/10 + 1/12 + 1/15 + 1/18 + 1/20 is an equally valid solution for your third test case? \$\endgroup\$ Sep 30, 2023 at 19:38
  • 1
    \$\begingroup\$ @JosWoolley I have added a rule saying that output any one solution when 2 or more exists, and mentioned the example \$\endgroup\$
    – Anm
    Sep 30, 2023 at 19:41

7 Answers 7

2
\$\begingroup\$

JavaScript (ES6), 103 bytes, \$O(2^n)\$

Returns an empty string if there's no solution.

f=(n,a=o=[],p=0,q=1)=>n?f(n-1,["1/"+n,...a],p*n+q,q*n,p&&f(n-1,a,p,q))&&o.join`+`:o=p-q|o[a.length]?o:a

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Is this a bruteforce \$O(2^n)\$ solution? \$\endgroup\$ Sep 30, 2023 at 12:25
  • \$\begingroup\$ Yes it is. I've added the time complexity in the header. \$\endgroup\$
    – Arnauld
    Sep 30, 2023 at 12:28
2
\$\begingroup\$

Charcoal, 50 bytes, O(2ⁿ)

Nθ≔ΦE…X²⊖θX²θ⊕⌕A⮌⍘ι²1⁼ΠιΣ÷Πιιυ¿υ⪫⁺1/I§υ⌕EυLι⌈EυLι+

Try it online! Link is to verbose version of code. Explanation:

Nθ

Input n.

≔ΦE…X²⊖θX²θ⊕⌕A⮌⍘ι²1⁼ΠιΣ÷Πιιυ

Get the powerset of [1..n-1] and see which sets' reciprocals sum to 1 when 1/n is included.

¿υ⪫⁺1/I§υ⌕EυLι⌈EυLι+

If any were found then output the longest.

53 bytes for a version that is twice as fast because it gets the powerset of [2..n-1]:

Nθ≔ΦE⊗…X²⁻θ²X²⊖θ⊕⌕A⮌⍘ι²1⁼ΠιΣ÷Πιιυ¿υ⪫⁺1/I§υ⌕EυLι⌈EυLι+

Try it online! Link is to verbose version of code.

71 66 bytes for an algorithm that is slightly faster because it stops considering fractions once the sum exceeds 1 (I don't know how this affects the time complexity though):

Nθ≔⟦⟦θ⟧⟧ηF…²θF⮌η«≔⁺κ⟦ι⟧κ≔⁻Σ÷ΠκκΠκζ¿‹ζ⁰⊞ηκ¿∧¬ζ›LκLυ≔⊞OΦκμθυ»⪫⁺1/Iυ+

Try it online! Link is to verbose version of code. Explanation:

Nθ≔⟦⟦θ⟧⟧η

Input n and start with 1/n as a required fraction.

F…²θF⮌η«

For each integer from 2 to n-1, loop over all of the sets so far.

≔⁺κ⟦ι⟧κ≔⁻Σ÷ΠκκΠκζ

Create a new set containing the current integer and calculate the excess of the sum of reciprocals.

¿‹ζ⁰⊞ηκ

If the excess is negative i.e. the sum is less than 1 then add this to the list of sets to check next iteration.

¿∧¬ζ›LκLυ≔⊞OΦκμθυ

If the excess is zero i.e. the sum is 1 and this set is longer than any previously found set then set this as the longest found set so far.

»⪫⁺1/Iυ+

Output the longest set found.

\$\endgroup\$
2
\$\begingroup\$

Python3, 246 bytes:

def f(n):
 q,t=[([*range(2,n)],[],1-(1/n))],[]
 while q:
  d,c,r=q.pop(0)
  if[]==d:continue
  if round(r,5)==0:t+=[c];continue
  if(U:=r-(1/d[0]))>=0:q+=[(d[1:],c+[d[0]],U)]
  q+=[(d[1:],c,r)]
 return'+'.join(f'1/{i}'for i in max(t,key=len)+[n])

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Is this DFS approach O(2^n)? \$\endgroup\$
    – Anm
    Oct 2, 2023 at 9:15
  • \$\begingroup\$ @Anm Yes, that is correct \$\endgroup\$
    – Ajax1234
    Oct 2, 2023 at 11:53
1
\$\begingroup\$

Vyxal R, 89 bitsv2, 11.125 bytes

ṗ't?=;Ė'∑1=;t\+j

Try it Online!

+~3 bytes due to reading the specs

Me when when fraction type automatically. Powerset is sorted by length by default, so the last item is guaranteed to be the longest.

\$\endgroup\$
5
  • \$\begingroup\$ Is the tail really guaranteed to be the longest sequence? (I asked myself a similar question when writing my answer but decided to explicitly test the lengths for now.) \$\endgroup\$
    – Arnauld
    Sep 30, 2023 at 14:37
  • 2
    \$\begingroup\$ @Arnauld Vyxal's power set built-in sorts the subsets by length. \$\endgroup\$
    – xigoi
    Sep 30, 2023 at 19:25
  • 1
    \$\begingroup\$ powerset actually doesn't sort by length due to needing to work nicely with infinite lists. \$\endgroup\$
    – emanresu A
    Oct 2, 2023 at 7:42
  • \$\begingroup\$ How do you distinguish between the valid output 1 (aka 1/1) for \$n=1\$ and invalid outputs 1 for \$n=2,3,4,5,7,8,9,10,11,...\$? \$\endgroup\$ Oct 2, 2023 at 8:50
  • \$\begingroup\$ @KevinCruijssen that's handled by powerset sorting subsets by length. [1] will always be in the list of valid subsets, but it won't always be the longest/last item. \$\endgroup\$
    – lyxal
    Oct 2, 2023 at 10:03
1
\$\begingroup\$

Excel, 168 bytes, \$O(2^n)\$

=LET(
    a,SEQUENCE(,A1),
    b,IF(MOD(INT(SEQUENCE(2^A1,,0)/2^(a-1)),2),1/a,),
    IFERROR(TEXTJOIN("+",,
        "1/"&TOCOL(1/TAKE(FILTER(b,TAKE(b,,-1)*(MMULT(b,TOCOL(a^0))=1)),-1),2))
    ,"")
)

Input in cell A1.

\$\endgroup\$
2
  • \$\begingroup\$ What would the time complexity of this be? \$\endgroup\$
    – Anm
    Sep 30, 2023 at 19:56
  • 1
    \$\begingroup\$ @Anm Apologies. There was an issue with the previous solution, which I've now fixed and also added the order. \$\endgroup\$ Oct 1, 2023 at 9:23
1
\$\begingroup\$

Scala, 345 bytes

Port of @Ajax1234's Python answer in Scala.

Golfed version. Try it online!

n=>{var q=Queue((2 to n-1 toList,List[Int](),1-1.0/n));var t=List[List[Int]]()
while(q.nonEmpty){val(d,c,r)=q.dequeue;if(d.nonEmpty){if(BigDecimal(r).setScale(5,BigDecimal.RoundingMode.HALF_UP).toDouble==0)t=c::t
val u=r-1.0/d.head;if(u>=0)q+=((d.tail,d.head::c,u));q+=((d.tail,c,r))}};(t.maxBy(_.size) :+n).sorted.map(i=>s"1/$i").mkString("+")}

Ungolfed version. Try it online!

import scala.collection.mutable.Queue

object Main {
  def f(n: Int): String = {
    var q: Queue[(List[Int], List[Int], Double)] = Queue((List.range(2, n), List(), 1 - (1.0/n)))
    var t: List[List[Int]] = List()
    while (q.nonEmpty) {
      val (d, c, r) = q.dequeue()
      if (d.isEmpty) {
        // if d is empty, continue with the next iteration
      } else if (BigDecimal(r).setScale(5, BigDecimal.RoundingMode.HALF_UP).toDouble == 0) {
        t = c :: t
      } else {
        val u = r - (1.0/d.head)
        if (u >= 0) {
          q += ((d.tail, d.head :: c, u))
        }
        q += ((d.tail, c, r))
      }
    }
    val maxList = t.maxBy(_.length) :+ n
    maxList.sorted.map(i => s"1/$i").mkString("+")
  }

  def main(args: Array[String]): Unit = {
    println(f(6))
    println(f(15))
    println(f(20))
  }
}
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 23 22 bytes

LæʒIå}DzOT.òÏéθ„1/ì'+ý

Will output nothing if there are no results.

There is a bug in the filter builtin ʒ for decimals 1.0 (which should be 05AB1E-truthy). So the second filter ʒ...Θ} has been replaced with D...Ï for -1 byte, without changing its functionality.

Try it online or verify test cases until it times out.

Explanation:

L          # Push a list in the range [1, (implicit) input-integer]
 æ         # Get the powerset of this list
  ʒ  }     # Filter this list of lists by:
   Iå      #  It contains the input-integer
  D     Ï  # Filter it further by:
   z       #  Take 1/v for each value `v` in the list
    O      #  Sum them together
     T.ò   #  Round it to 10 decimal digits to account for floating point inaccuracies
           #  (only 1 is truthy in 05AB1E)
  é        # After the filters: sort the remaining list by length (shortest to longest)
   θ       # Pop and push the last/longest valid list
  „1/ì     # Prepend "1/" in front of each integer
      '+ý '# And join these strings with "+"-delimiter
           # (after which the resulting string is output implicitly as result)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Nice! Although the question specified that the program may not output any real number if a solution does not exist \$\endgroup\$
    – Anm
    Oct 2, 2023 at 12:08
  • 1
    \$\begingroup\$ @Anm Good point. It will now output an empty string for invalid results (and I've golfed it by 1 byte as well). \$\endgroup\$ Oct 2, 2023 at 12:39

Your Answer

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

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