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.

• Command Master: 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 ...
• Command Master: (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
• Anm: @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.
• Jos Woolley: 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?
• Anm: @JosWoolley I have added a rule saying that output any one solution when 2 or more exists, and mentioned the example

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!

• Command Master: Is this a bruteforce \$O(2^n)\$ solution?
• Arnauld: Yes it is. I've added the time complexity in the header.

Answer 2

Charcoal, 50 bytes, O(2n)

Nθ≔ΦE...X2⊖θX2θ⊕⌕A⮌⍘ι21=ΠιΣ÷Πιιυ¿υ⪫+1/I§υ⌕EυLι⌈EυLι+

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

Nθ

Input n.

≔ΦE...X2⊖θX2θ⊕⌕A⮌⍘ι21=ΠιΣ÷Πιιυ

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⊗...X2−θ2X2⊖θ⊕⌕A⮌⍘ι21=ΠιΣ÷Πιιυ¿υ⪫+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...2θF⮌η«≔+κ⟦ι⟧κ≔−Σ÷ΠκκΠκζ¿‹ζ0⊞ηκ¿∧¬ζ›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...2θ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.

¿‹ζ0⊞ηκ

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.

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!

• Anm: Is this DFS approach O(2^n)?
• Ajax1234: @Anm Yes, that is correct
• ceilingcat: 217 bytes

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.

• Arnauld: 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.)
• Adamátor: @Arnauld Vyxal's power set built-in sorts the subsets by length.
• emanresu A: powerset actually doesn't sort by length due to needing to work nicely with infinite lists.
• Kevin Cruijssen: 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,...\$?
• lyxal: @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.

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.

• Anm: What would the time complexity of this be?
• Jos Woolley: @Anm Apologies. There was an issue with the previous solution, which I've now fixed and also added the order.

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)

• Anm: Nice! Although the question specified that the program may not output any real number if a solution does not exist
• Kevin Cruijssen: @Anm Good point. It will now output an empty string for invalid results (and I've golfed it by 1 byte as well).