# Longest sequence of Egyptian fractions with n as denominator

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

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.

• 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 ... Sep 30 at 11:54
• (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 Sep 30 at 11:54
• @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.
– Anm
Sep 30 at 13:15
• 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? Sep 30 at 19:38
• @JosWoolley I have added a rule saying that output any one solution when 2 or more exists, and mentioned the example
– Anm
Sep 30 at 19:41

# 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!

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

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

# 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:q+=[(d[1:],c+[d],U)]
q+=[(d[1:],c,r)]
return'+'.join(f'1/{i}'for i in max(t,key=len)+[n])


Try it online!

• Is this DFS approach O(2^n)?
– Anm
Oct 2 at 9:15
• @Anm Yes, that is correct Oct 2 at 11:53

# VyxalR, 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.

• 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.) Sep 30 at 14:37
• @Arnauld Vyxal's power set built-in sorts the subsets by length. Sep 30 at 19:25
• powerset actually doesn't sort by length due to needing to work nicely with infinite lists. Oct 2 at 7:42
• 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,...$? Oct 2 at 8:50
• @KevinCruijssen that's handled by powerset sorting subsets by length.  will always be in the list of valid subsets, but it won't always be the longest/last item. Oct 2 at 10:03

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

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

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


# 05AB1E, 23 22 bytes

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


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.

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)

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