Egyptian fraction representations of 1

Question

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 code-golf, so the shortest code in bytes wins

Answer 1

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.

Answer 2

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

Answer 3

Wolfram Language (Mathematica), 32 bytes

Using Sylvester's sequence A000058

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

Try it online!

-8 bytes from @att

Answer 4

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

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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

Answer 9

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.

Answer 10

Charcoal, 16 bytes

ＦＮ⊞υ⊕∨Πυ¹⊞υ⊖⊟υＩυ

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

ＦＮ

Loop n times...

⊞υ⊕∨Πυ¹

... push the incremented product of the list to the list. (Note that the version of Charcoal on TIO 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.

Ｉυ

Output the list.

14 bytes using the newer version of Charcoal on ATO that can take the product of an empty list:

ＦＮ⊞υ⊕Πυ⊞υ⊖⊟υＩυ

Attempt This Online! Link is to verbose version of code.

Answer 11

Jelly, 10 9 bytes

⁸P‘ṭƊ¡’0¦

Try it online!

Based on the Sylvester sequence.

Answer 12

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.

Answer 13

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.

Answer 14

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)

Answer 15

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

Answer 16

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.

Answer 17

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 3 → 2 4 6 12 solves 4 → 2 4 8 12 24 solves 5 → ...

Answer 18

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

Answer 19

Scala, 105 bytes

Golfed version. Try it online!

def f(n:Int)=(1 to n).map(i=>{var a,q=BigInt("1");for(_<-1 to i){a*=q;q=1+a};q-(if(i==n)1 else 0)}).toSeq

Ungolfed version. Try it online!

object PariGpInScala {
  def main(args: Array[String]): Unit = {
    val inputList = List(1, 3, 4, 5, 6, 7, 8, 9, 10)

    inputList.foreach { n =>
      println(s"$n summands:")
      println(s"1 = ${f(n).map(x=>"1/"++x.toString)mkString(" + ")} \n")
    }
  }

  def f(n: Int): List[BigInt] = {
    (1 to n).map { i =>
      var a,q = BigInt("1")
      for (_ <- 1 to i) {
        a *= q
        q = 1 + a
      }
      q - (if (i == n) 1 else 0)
    }.toList
  }
}

Answer 20

APL(NARS), 80 chars

r←z w;k;t
r←⍬⋄→0×⍳2≥w⋄r←2 3 6
→3×⍳w=k←≢r⋄t←r[k]÷6⋄r[k]←t×t+6⋄r,←6×t+6⋄→2
r←r[⍋r]

10+20+43+7=80. It return ⍬ if w≤2, 2 3 6 if w=3, otherwise it use the formula

1/r*s=(1/(r*(r+s)))+(1/s*(r+s)) 

for make more long the array of start 2 3 6. z has the peculiarity could calculate easly the result at last for argument <= 20000, because the numbers are not big numbers there will be a problem for the argument too much big, when r*(r+s) or s*(r+s) will be too much big.

  z 3
2 3 6 
  z 2

  z 4
2 3 7 42 
  z 20
2 3 7 91 247 475 618 775 1147 1591 2107 2695 3355 4087 4891 5767 6715 7735 8827 9991 
  +/÷z 20
1
  +/÷z 20000
1