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

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 2nd place

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

Improve this question
\$\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\$ Commented 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\$ Commented 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\$ Commented 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\$ Commented 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\$ Commented Sep 30, 2023 at 19:41

7 Answers 7

Reset to default
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!

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

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.

Improve this answer
\$\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!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Is this DFS approach O(2^n)? \$\endgroup\$ Commented Oct 2, 2023 at 9:15
  • \$\begingroup\$ @Anm Yes, that is correct \$\endgroup\$ Commented Oct 2, 2023 at 11:53
  • \$\begingroup\$ 217 bytes \$\endgroup\$ Commented Sep 9 at 15:51
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.

Improve this answer
\$\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\$ Commented Sep 30, 2023 at 14:37
  • 2
    \$\begingroup\$ @Arnauld Vyxal's power set built-in sorts the subsets by length. \$\endgroup\$ Commented 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\$ Commented 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\$ Commented 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\$ Commented 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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ What would the time complexity of this be? \$\endgroup\$ Commented 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\$ Commented 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)) } }
Improve this answer
\$\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)
Improve this answer
\$\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\$ Commented 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\$ Commented Oct 2, 2023 at 12:39

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.