Longest sequence of Egyptian fractions with n as denominator

Question

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

6 ⟶ 1/2 + 1/3 + 1/6

15 ⟶ 1/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 2^nd place

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

Answer 1

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!

Answer 2

Charcoal, 50 bytes, O(2ⁿ)

Ｎθ≔ΦＥ…Ｘ²⊖θＸ²θ⊕⌕Ａ⮌⍘ι²1⁼ΠιΣ÷Πιιυ¿υ⪫⁺1/Ｉ§υ⌕ＥυＬι⌈ＥυＬι+

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

Ｎθ

Input n.

≔ΦＥ…Ｘ²⊖θＸ²θ⊕⌕Ａ⮌⍘ι²1⁼ΠιΣ÷Πιιυ

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

¿υ⪫⁺1/Ｉ§υ⌕ＥυＬι⌈ＥυＬι+

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

Ｎθ≔ΦＥ⊗…Ｘ²⁻θ²Ｘ²⊖θ⊕⌕Ａ⮌⍘ι²1⁼ΠιΣ÷Πιιυ¿υ⪫⁺1/Ｉ§υ⌕ＥυＬι⌈ＥυＬι+

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

Ｎθ≔⟦⟦θ⟧⟧ηＦ…²θＦ⮌η«≔⁺κ⟦ι⟧κ≔⁻Σ÷ΠκκΠκζ¿‹ζ⁰⊞ηκ¿∧¬ζ›ＬκＬυ≔⊞ＯΦκμθυ»⪫⁺1/Ｉυ+

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

Ｎθ≔⟦⟦θ⟧⟧η

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

Ｆ…²θＦ⮌η«

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.

¿∧¬ζ›ＬκＬυ≔⊞ＯΦκμθυ

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/Ｉυ+

Output the longest set found.

Answer 3

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!

Answer 4

Vyxal R, 89 bits^v2, 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.

Answer 5

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.

Answer 6

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

Answer 7

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)