32
\$\begingroup\$

An Egyptian fraction is a representation of a rational number using the sum of distinct unit fractions (a unit fraction is of the form \$ \frac 1 x \$ where \$ x \$ is a positive integer).

For all[1] positive integers \$ n \ne 2 \$, there exists at least one Egyptian fraction of \$ n \$ distinct positive integers whose sum is \$ 1 \$. For example, for \$ n = 4 \$: $$ \frac 1 2 + \frac 1 4 + \frac 1 6 + \frac 1 {12} = 1 $$ Here is another possible output: $$ \frac 1 2 + \frac 1 3 + \frac 1 {10} + \frac 1 {15} = 1 $$

The number of possible outputs is given by A006585 in the OEIS.

[1]: I cannot find a direct proof of this, but I can find a proven lower bound on A006585, which has this as an obvious consequence. If you can find (or write!) a better / more direct proof that a representation exists for all \$ n \ne 2 \$ I would love to hear it.

Task

Given \$ n \$, output a list of positive integers representing the denominators of at least one valid solution of length \$ n \$.

You may alternatively output a list of rational numbers which are unit fractions, but only if they are an exact representation of the value (so not floating-point).

Test cases

I only list a few possible outputs. Here is a Ruby program which can verify any solution.

n     outputs
1     {1}
3     {2, 3, 6}
4     {2, 4, 6, 12} or {2, 3, 10, 15} or {2, 3, 9, 18} or {2, 4, 5, 20} or {2, 3, 8, 24} or {2, 3, 7, 42} or ...
5     {2, 4, 10, 12, 15} or {2, 4, 9, 12, 18} or {3, 4, 5, 6, 20} or {2, 5, 6, 12, 20} or {2, 4, 8, 12, 24} or {2, 4, 7, 14, 28} or ...
8     {4, 5, 6, 9, 10, 15, 18, 20} or {3, 5, 9, 10, 12, 15, 18, 20} or {3, 6, 8, 9, 10, 15, 18, 24} or {4, 5, 6, 8, 10, 15, 20, 24} or {3, 5, 8, 10, 12, 15, 20, 24} or {4, 5, 6, 8, 9, 18, 20, 24} or ...
15    {6, 8, 9, 11, 14, 15, 18, 20, 21, 22, 24, 28, 30, 33, 35} or {7, 8, 10, 11, 12, 14, 15, 18, 20, 22, 24, 28, 30, 33, 36} or {6, 8, 10, 11, 12, 15, 18, 20, 21, 22, 24, 28, 30, 33, 36} or {6, 8, 10, 11, 12, 14, 18, 20, 21, 22, 24, 28, 33, 35, 36} or {5, 8, 11, 12, 14, 15, 18, 20, 21, 22, 24, 28, 33, 35, 36} or {5, 8, 10, 11, 14, 15, 18, 21, 22, 24, 28, 30, 33, 35, 36} or ...

Rules

  • You may output the numbers in any order
  • If you choose to output all possible solutions, or a particular subset of them, you must not output duplicates. This includes lists which are the same under some permutation.
  • You may assume \$ n \$ is a positive integer, and is not \$ 2 \$
  • 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
  • This is , so the shortest code in bytes wins
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Sandbox \$\endgroup\$
    – pxeger
    Jan 18 at 8:16
  • 22
    \$\begingroup\$ An inductive proof can work like this: There is a solution for \$n=3\$, \$\frac 1 2 + \frac 1 3 + \frac 1 6\$. If we have a solution for \$n=i\$ there is also a solution for \$n=i+2\$, simply take the smallest fraction and replace it with itself multiplied by the solution for \$n=3\$, since it was the smallest and all the resulting fractions are smaller than it all the resulting fractions must be unique. And the whole sum is still 1. Now with the base cases of \$n=3\$ and \$n=4\$ we use induction to show every \$n>2\$ has a solution. \$\endgroup\$
    – Wheat Wizard
    Jan 18 at 13:19
  • 9
    \$\begingroup\$ @WheatWizard nice one! dingledooper found a better inductive proof, replacing the smallest fraction 1/n with 1/(n+1) + 1/n(n+1) \$\endgroup\$
    – justhalf
    Jan 18 at 20:12
  • 5
    \$\begingroup\$ Another inductive proof: if x1, x2, ..., xn is the solution for n, then: 2, 2*x1, 2*x2, ..., 2*xn is a solution for n+1. (in other words, replace all fractions 1/m with 1/2m and add 1/2.) \$\endgroup\$ Jan 19 at 22:22

18 Answers 18

29
\$\begingroup\$

Python 2, 42 bytes

f=lambda n,x=1:1/n*[x]or[x+1]+f(n-1,x*-~x)

Try it online!

The key thing to observe is that 1/n = 1/(n+1) + 1/(n*(n+1)). Therefore we can always obtain a solution with n fractions, by using a solution with n-1 fractions, and "splitting" the last fraction in two.

\$\endgroup\$
4
  • \$\begingroup\$ dingledoopper big brain i luv the solution +1 \$\endgroup\$
    – DialFrost
    Jan 18 at 9:39
  • 4
    \$\begingroup\$ @pxeger ZaMoC had arrived at the same solution it seems, although we both found them independently. \$\endgroup\$ Jan 18 at 9:40
  • 3
    \$\begingroup\$ Very nice! My Haskell attempt actually produced the same solutions (with bruteforcing), but I failed to see the pattern \$\endgroup\$
    – ovs
    Jan 18 at 9:40
  • \$\begingroup\$ Great, great solution! When crafting my original ungolfed one, I found out that a lot of the denominators that were being returned were similar or the same, for instance with n=5 the last fraction was 1/1806, and with n=6 the last fraction was 1/1807 and the last one was like 3.26 million, like in yours, but I failed to notice the pattern (how stupid of me). \$\endgroup\$
    – ophact
    Jan 18 at 9:44
13
\$\begingroup\$

Vyxal, 10 bytes

¡ɾṗ'Ė∑1=;t

Try it Online!

Bruteforcer. \$O\left(2^{n!}\right)\$ time complexity, searches for fractions with reciprocals \$ n! \$ which seems to be enough.

¡          # Factorial
 ɾṗ        # All combinations of 1...n
   '    ;  # Filtered by...
    Ė∑     # Sum of reciprocals
      1=   # is 1?
         t # Get the last one
\$\endgroup\$
2
  • 8
    \$\begingroup\$ Welcome to CGCC! This is a great first post, and I hope you enjoy your stay! Also welcome to Vyxal too :D \$\endgroup\$
    – lyxal
    Jan 18 at 8:56
  • 3
    \$\begingroup\$ Dunno Vyxal well enough but wonder if you can get combinations without replacement of length n first for the same byte count and then drop the t since we may output a list of all of them? \$\endgroup\$ Jan 18 at 14:00
12
\$\begingroup\$

Wolfram Language (Mathematica), 32 bytes

Using Sylvester's sequence A000058

Nest[##&[#^2+#,1+#,##2]&,1,#-1]&

Try it online!

-8 bytes from @att

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 32 bytes returning a Sequence in descending order (34 bytes for list output) \$\endgroup\$
    – att
    Jan 18 at 22:42
8
\$\begingroup\$

Factor, 48 bytes

[ 1 - 2 [ 3 dupn . sq - abs 1 + ] repeat 1 - . ]

Try it online!

Port of @ZaMoC's Mathematica answer. It prints the first n terms of Sylvester's sequence, subtracting 1 from the last number.

The old way that doesn't quite work:

[ [1,b] dup 1 rotate v* ]
\$\endgroup\$
0
7
\$\begingroup\$

R, 44 38 bytes

-6 bytes thanks to Dominic van Essen

function(n)2^(1:n)*.75^(n:1<3)-(n<2)/2

Try it online!

First Attempt

function(n){k<-1:n;2^k*.75^(k>n-2)-(n==1)/2}

Try it online!

Port of my Excel answer.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ This is great, and I think you can save some more bytes by scrapping the definition of k and flipping the 1:n>n-2 to n:1<3, like this \$\endgroup\$ Jan 19 at 9:03
  • 1
    \$\begingroup\$ ...and one more by changing n==1 to n<2... \$\endgroup\$ Jan 19 at 9:11
  • \$\begingroup\$ Thanks for the suggestions. I have a lot to learn about R. \$\endgroup\$
    – Axuary
    Jan 19 at 14:02
6
\$\begingroup\$

Ruby, 70 40 34 bytes

->n{a=1;(2..n).map{a*=q=1+a;q}<<a}

Try it online!

Based on dingledooper's python answer. Some bytes saved by following Kevin Cruijssen's advice.

\$\endgroup\$
1
  • \$\begingroup\$ a*=a+1 can be a*=q, right? \$\endgroup\$ Jan 18 at 11:40
6
\$\begingroup\$

R, 55 57 bytes

Edit: Thanks to Anders Kaseorg (and +2 bytes) for bug-spotting

function(n){while(n<-n-1)T=c((k=T[1]+1)*T[1],k,T[-1]);+T}

Try it online!

Outputs one egyptian fractional representation of 1 using n fractions, constructed using ZaMoC's & dingledooper's approach.


R, 102 bytes

function(n,m=n){while(all(F<-apply(l<-combn(1:m,n),2,function(k)sum(prod(k)/k)-prod(k))))m=m+1;l[,!F]}

Try it online!

A brute-force approach that outputs the egyptian fractional representation(s) with the lowest-valued top denominator, by trying all combinations of fractions up to successively increasing denominators.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ The 55, 29, and 24-byte solutions do not work for \$n = 6\$. The denominators must be distinct. \$\endgroup\$ Jan 18 at 20:29
  • \$\begingroup\$ @AndersKaseorg - Thanks for spotting! I think it's fixed now! \$\endgroup\$ Jan 18 at 23:07
5
\$\begingroup\$

Charcoal, 16 bytes

FN⊞υ⊕∨Πυ¹⊞υ⊖⊟υIυ

Try it online! Link is to verbose version of code. Explanation: Uses a formula for Sylvester's sequence taken from A000058.

FN

Loop n times...

⊞υ⊕∨Πυ¹

... push the incremented product of the list to the list. (Note that Charcoal can't take the product of an empty list, so I have to manually replace the result with 1.)

⊞υ⊖⊟υ

Decrement the last element of the list.

Iυ

Output the list.

\$\endgroup\$
5
\$\begingroup\$

Excel, 47 bytes

=LET(x,SEQUENCE(A1),0.75^(x>A1-2)*2^x-(A1=1)/2)

Link to Spreadsheet

Uses the fact that for \$ n>2\$: $$\sum_{k=1} ^{n-2} \left(\frac 1 {2}\right) ^ k + \frac 4 {3}\left(\left(\frac 1 {2}\right)^{n-1} + \left(\frac 1 {2}\right)^n\right) = 1$$.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Drop the leading 0 for -1 byte \$\endgroup\$ Jan 19 at 3:57
  • 1
    \$\begingroup\$ Thanks @TaylorRaine. Excel puts the 0 back in. Does that could toward the byte count? \$\endgroup\$
    – Axuary
    Jan 19 at 14:03
  • \$\begingroup\$ For Access, Excel and all VBA variants - yes, AutoFormatting is considered valid - note, however, that AutoCompetion is not considered valid. To give an Excel example, you could consider omitting leading the 0 in 0.75 as AutoFormatting, but omitting trailing )s and having to clear the We found a typo in your formula ... dialog box would be AutoCompletion, and thus invalid. \$\endgroup\$ Jan 19 at 14:42
  • \$\begingroup\$ So to sum it all up - you can post your formula without the 0 in it, and without it contributing to your byte count. You may want to note that that's happening in your Live Excel sheet tho \$\endgroup\$ Jan 19 at 14:46
5
+50
\$\begingroup\$

tinylisp, 106 105 98 bytes

(load library
(d g(q((n x)(i(e n 1)x(g(s n 1)(c(*(a(h x)1)(h x))(c(a(h x)1)(t x
(d f(q((n)(g n(q(1

Try it online!

Not sure there's a better way to get (1) than (c 1() (use (q(1) add two elements to a list than (c X(c Y Z).

Ports e.g., Dominic van Essen's R answer.

Thanks to DLosc for -5 bytes.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Uses library just for *... \$\endgroup\$
    – Giuseppe
    Feb 2 at 15:20
  • \$\begingroup\$ You can save some bytes on parentheses by inverting the condition: Try it online! \$\endgroup\$
    – DLosc
    Feb 2 at 17:48
  • 1
    \$\begingroup\$ @DLosc thanks! Found another couple as well. I'm enjoying this LoTM so far, but tinylisp will either help me get over this or make it worse \$\endgroup\$
    – Giuseppe
    Feb 2 at 18:08
4
\$\begingroup\$

Jelly, 10 9 bytes

⁸P‘ṭƊ¡’0¦

Try it online!

Based on the Sylvester sequence.

\$\endgroup\$
4
\$\begingroup\$

tinylisp, 156 97 91 bytes

-59 bytes remove extra spaces and use pow function

-6 bytes thanks to @DLosc

(load library
(d g(q((n m)(i m(c(/(*(s 4(l(s n 2)m))(pow 2 m))4)(g n(s m 1)))(
q((n)(g n n

Try it online!

First Attempt

(load library
(d p(q((x n)(i n(* x(p x(s n 1)))1
(d g(q((n m)(i m(c(/(*(i(l m (s n 1))4 3)(p 2 m))4)(g n(s m 1)))(
(d f(q((n)(g n n

Try it online!

Porting into tinylisp.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Nice! (i(l m(s n 1))4 3) -> (s 4(l(s n 2)m)) for -2 bytes: Try it online! Also, you don't need to count the (d f in your score as long as f isn't recursive. \$\endgroup\$
    – DLosc
    Feb 2 at 17:09
3
\$\begingroup\$

Pari/GP, 34 bytes

n->[q-(i==n)|i<-[a=1..n],a*=q=1+a]

Try it online!

A port of @ZaMoC's Mathematica answer and @G B's Ruby answer.

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 13 9 bytes

$GD>DŠ*})

-4 bytes porting @GB's Ruby answer.

Try it online or verify the first \$n=10\$ test cases, excluding \$2\$.

Alternative 9-byter inspired by @Neil's comment below, which is pretty similar as the current approach above:

$EPNIÊ+ˆ¯

Try it online or verify the first \$n=10\$ test cases, excluding \$2\$.

Explanation:

$         # Push 1 and the input-integer
 G        # Loop input-1 amount of times:
  D       #  Duplicate the current integer
   >      #  Increase this copy by 1
    D     #  Duplicate that as well
     Š    #  Tripleswap the stack from a,b,c to c,a,b
      *   #  Multiply the top two values
 })       # After the loop, wrap all values on the stack into a list
          # (after which the result is output implicitly)


$         # Push 1 and the input-integer
 E        # Loop `N` in the range [1,input]:
  P       #  Push the product of the stack / top
          #  (which will be 1 in the first iteration)
   NIÊ    #  Check that `N` is NOT equal to the input
          #  (0 if it's the final iteration, 1 otherwise)
      +   #  Add that to the product
       ˆ  #  Pop and add it to the global array
        ¯ #  Push the global array for the next iteration
          # (after which the last pushed global array is output implicitly after
          # the loop)
\$\endgroup\$
7
  • \$\begingroup\$ There are at least two bytes to be saved by calculating the sum of reciprocals "by hand" with integer arithmetic \$\endgroup\$
    – ovs
    Jan 18 at 10:51
  • \$\begingroup\$ @ovs Yeah, I had the feeling there was. Porting GB's Ruby answer saves 4 bytes, though. :) \$\endgroup\$ Jan 18 at 11:58
  • 1
    \$\begingroup\$ Yeah that is shorter. For reference I had ...ʒPDy÷OQ \$\endgroup\$
    – ovs
    Jan 18 at 12:19
  • 1
    \$\begingroup\$ @ovs For reference I had )sFDP>š}ć<š. \$\endgroup\$
    – Neil
    Jan 19 at 0:18
  • 1
    \$\begingroup\$ @KevinCruijssen Ah, of course, the global array; I was racking my brains trying to work out where I was supposed to get an empty array from. \$\endgroup\$
    – Neil
    Jan 19 at 9:56
3
\$\begingroup\$

JavaScript (Node.js), 53 52 bytes

f=(n,x=1)=>[,[x],[x*3,x*1.5]][n]||[x*=2,...f(n-1,x)]

Try it online!

Making special \$1=\frac 13+\frac 1{1.5}\$ make it bit shorter

\$\endgroup\$
2
  • \$\begingroup\$ @Giuseppe Because 2 is not a valid input \$\endgroup\$
    – l4m2
    Feb 2 at 1:25
  • \$\begingroup\$ Oh I get it now. Have my upvote! \$\endgroup\$
    – Giuseppe
    Feb 2 at 3:14
2
\$\begingroup\$

Python 2, 43 bytes

-10 bytes thanks to dingledooper

lambda n:[4-(x>n-3)<<x>>1for x in range(n)]

Try it online!

First Attempt, 53 bytes

f=lambda n:map(lambda x:2**x*(4-(x>n-3))/2, range(n))

Try it online!

Porting to Python.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Very interesting formula. I can get yours down to 43 bytes: lambda n:[4-(x>n-3)<<x>>1for x in range(n)] (f= is not necessary for non-recursive lambdas). This makes me hopeful that a 41 in Python exists! \$\endgroup\$ Jan 30 at 21:07
  • \$\begingroup\$ Thanks for the info. I especially like the use of the bit shifts. \$\endgroup\$
    – Axuary
    Jan 31 at 5:43
2
\$\begingroup\$

JavaScript, 48 bytes

Try it online

f=n=>--n>1?[1,...f(n)].map(x=>x*2):n?[1.5,3]:[1]

Original answer (49 bytes):

f=n=>[[1],,[2,3,6]][--n]||[2,...f(n).map(x=>x*2)]
\$\endgroup\$
3
  • \$\begingroup\$ 47 bytes: f=n=>['1',,'236'][--n]||[1,...f(n)].map(x=>x*2) \$\endgroup\$
    – pxeger
    Feb 5 at 7:17
  • \$\begingroup\$ @pxeger It returns string instead of array for n=1,n=3 You inspired me to a shorter solution. I updated the answer. \$\endgroup\$ Feb 5 at 12:51
  • \$\begingroup\$ I thought output as a string was fine, but up to you I guess \$\endgroup\$
    – pxeger
    Feb 5 at 13:51
1
\$\begingroup\$

APL(Dyalog Unicode), 26 bytes SBCS

{1≡⍵:1⋄3≡⍵:2 3 6⋄2,2×∇⍵-1}

Try it on APLgolf!

A dfn submission which encodes the inductive proof posted in the comments: to get a solution for n+1, double each of the denominators and add 2 to the denominators.

E.g. 2 3 6 solves 32 4 6 12 solves 42 4 8 12 24 solves 5 → ...

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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