11
\$\begingroup\$

Background

As noted in this question, for all positive integers \$n>2\$ there exists at least one Egyptian fraction representation (EFR) of \$n\$ distinct positive integers \$a_{1} < a_{2} < \dots < a_{n}\$ such that $$ \sum_{k=1}^{n} \frac{1}{a_{k}} = 1. \tag{1} \label{1} $$

When \$n=3\$, for instance, we have $$ \frac{1}{2} + \frac{1}{3} + \frac{1}{6} = 1 \tag{2}\label{2}. $$

Note that the above EFR in \eqref{2} consists of two terms with prime denominators, and one term with a composite denominator.

Recently, I've come across an EFR of \$1\$ that solely consists of composite1 denominators. This is the following identity:

$$ \sum_{k=1}^{\infty} \frac{1}{k(k+1)} = 1. \tag{3}\label{3} $$

However, this is not a finite EFR of \$1\$. I am interested EFRs of \$1\$ that are finite and solely consist of composite denominators.

Task

Find an algorithm that, given \$n\$, does the following two things:

  1. Determines whether an EFR of length \$n\$ exists without any prime denominators. If such a representation does not exist, the algorithm should print the output

No EFR of \$1\$ with composite denominators exists for this \$n\$

or something else along along these lines - as long as it's clearly conveyed no such representation exists.

  1. If such a representation does exist, the algorithm ought to output the denominators of at least one valid solution of length \$n\$. Alternatively, you may 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 -- see the paragraph on precision in this question).

Test Cases

Below, I list one possible output for \$n=9,\dots,13\$, and the only possible output2 for \$n=4\$ and \$n=8\$. They were found by Neil and Mukundan314:

n     outputs
4     No EFR of 1 with composite denominators exists for this n
8     No EFR of 1 with composite denominators exists for this n
9     {4, 6, 8, 9, 10, 12, 15, 18, 24} 
10    {4, 6, 8, 9, 10, 15, 18, 21, 24, 28}
11    {4, 6, 8, 10, 12, 15, 18, 20, 24, 30, 36}
12    {4, 8, 9, 10, 12, 15, 18, 20, 21, 24, 28, 30}
13    {4, 8, 9, 12, 14, 15, 18, 20, 21, 24, 28, 30, 35}

Rules

We largely follow the rules described here:

  • You may output the EFRs in any order, of you choose to output multiple. But all denominators within each EFR ought to be displayed in ascending 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
  • The shortest code in bytes wins

Notes

[1] This infinite EFR actually does include a prime denominator, the number \$2\$, as pointed by Jonathan Allan. We can only say it includes no odd primes.

[2] For \$n=2,\dots,8\$, the output should indicate that no such EFR is possible, as the sum of the reciprocals of the composites up to that value of \$n\$ is less than \$1\$ -- this was (also) noted by Jonathan Allan.

\$\endgroup\$
16
  • 2
    \$\begingroup\$ I've found 11 composite numbers whose reciprocals sum to 1, they are 4, 6, 8, 10, 12, 15, 18, 20, 24, 30, 36. \$\endgroup\$
    – Neil
    Feb 25 at 16:19
  • 2
    \$\begingroup\$ Few more: 9 length: 4, 6, 8, 9, 10, 12, 15, 18, 24, 10 length: 4, 6, 8, 9, 10, 15, 18, 21, 24, 28, 12 length: 4, 8, 9, 10, 12, 15, 18, 20, 21, 24, 28, 30, 13 length: 4, 8, 9, 12, 14, 15, 18, 20, 21, 24, 28, 30, 35 \$\endgroup\$ Feb 25 at 16:34
  • 1
    \$\begingroup\$ Let us say we have a solution \$a\$ of length \$n\$ then we can replace \$a_n\$ with \$a_n + 2\$, \$a_n * (a_n + 1)\$ and \$(a_n + 1) * (a_n + 2)\$ (you should be able to convince yourself this by writing these as reciprocals and doing some simplification). This means that given a solution of length \$n\$ we can create a solution of length \$n + 2\$ since we have already found solutions for \$9\$ and \$10\$, we have solution for \$9 + 2x\$ and \$10 + 2x\$ which covers everything. \$\endgroup\$ Feb 25 at 18:50
  • 4
    \$\begingroup\$ @Mukundan314 Since \$a_n\$ is composite, you can do better still: \$\frac1{a_n}=\frac1{bc}=\frac1{c(b+c)}+\frac1{b(b+c)}=\frac1{c(b+2c)}+\frac1{(b+c)(b+2c)}+\frac1{b(b+c)}\$ (where \$b\$ and \$c\$ are coprime) etc. \$\endgroup\$
    – Neil
    Feb 25 at 19:51
  • 2
    \$\begingroup\$ @Mukundan314 I was just expanding it to show that it would generalise easily, although given \$b\$ and \$c\$ are coprime then \$b+c\$ is coprime to both of them so yes I guess that's a trivial observation. \$\endgroup\$
    – Neil
    Feb 25 at 19:59

10 Answers 10

6
\$\begingroup\$

Jelly, 25 bytes

ḊẒÐḟœc³P-ƤS⁼PƲƇ
0Ç1#<?9ḢÇ

A full program that accepts an integer, \$n\$, and prints the Jelly representation of a list of at least one valid decomposition, each as a list of \$n\$ composite denominators in ascending order, or nothing if not possible (when \$n \lt 9\$).

Try it online! (Too slow for even \$n=12\$)

How?

Brute force:

ḊẒÐḟœc³P-ƤS⁼PƲƇ - Link 1: integer, UpperBound
Ḋ               - dequeue {UpperBound} -> [2..UpperBound]
 ẒÐḟ            - discard primes
    œc³         - combinations of program input (n) items (without repeats)
              Ƈ - keep those for which:
             Ʋ  -   last four links as a monad - f(Selection):
        -Ƥ      -     for outfixes of length one less than Selection:
       P        -       product
          S     -     sum -> SumProducts
            P   -   product {Selection} -> TotalProduct
           ⁼    -   {SumProducts} equals {TotalProduct}?

0Ç1#<?9ḢÇ - Main Link: integer, N:
     ?    - if...
    < 9   - ...condition: {N} is less than 9?
0         - ...then: zero
  1#      - ...else: start with k=1 and increment collecting the first 1 for which:
 Ç        -            call Link 1 (empty list is falsey)
       Ḣ  - head -> k
        Ç - call Link 1
          - implicit print

Original  35  29 bytes

ḢH;2×S$;
_9µ‘Ṡ“ðØЀ½µ®©¥‘xÇ⁸¡

A monadic Link that accepts an integer, \$n\$, and yields a valid decomposition as a list of \$n\$ composite denominators in descending order, or an empty list if not possible (when \$n \lt 9\$).

Try it online! (The numbers get huge pretty quickly!)

How?

We know \$n \lt 9\$ is not possible since the sum of the reciprocals of the eight smallest composites is less than one: \$\frac{1}{4} + \frac{1}{6} + \frac{1}{8} + \frac{1}{9} + \frac{1}{10} + \frac{1}{12} + \frac{1}{14} + \frac{1}{15} \lt 1\$.

We can find a solution for \$n=9\$: [4, 6, 8, 9, 10, 12, 15, 18, 24].

We can create a solution of length \$n+1\$ by removing the largest denominator, \$D\$, from a solution of length \$n\$ and replacing it by two larger numbers, \$A\$ and \$B\$, such that \$\frac{1}{D} = \frac{1}{A} + \frac{1}{B}\$.

\$D\$ is composite so we can factorise it as \$D=F.M\$ and now \$A=F(F+M) \gt D\$ and \$B=M(F+M) \gt D\$ will do:

\begin{align} \frac{1}{D} & = \frac{1}{FM} \\ & = \frac{F+M}{FM(F+M)} \\ & = \frac{M}{FM(F+M)} + \frac{F}{FM(F+M)} \\ & = \frac{1}{F(F+M)} + \frac{1}{M(F+M)} \\ \end{align}

Since the first \$D\$, \$24\$, is divisible by \$4\$ we can fix \$F\$ at \$2\$ safe in the knowledge that both \$A\$ and \$B\$ will be divisible by \$4\$ forever, allowing us to continue using \$F=2\$.

ḢH;2×S$; - Link 1: list of integers, Denominators (descending)
Ḣ        - remove the head and yield it
 H       - halve that -> M
  ;2     - concatenate a two -> [M,F]
      $  - last two links as a monad:
     S   -   sum them -> M+F
    ×    -   multiply -> [M(M+F), F(M+F)] = [max(A,B), min(A,B)]
       ; - concatenate {the beheaded Denominators}

_9µ‘Ṡ“ðØЀ½µ®©¥‘xÇ⁸¡ - Link: integer, N
_9                   - subtract 9 -> N-9
  µ                  - start a new monadic Link ~ X=N-9
   ‘                 - increment {X}
    Ṡ                - sign -> S
     “ðØЀ½µ®©¥‘     - [24, 18, 15, 12, 10, 9, 8, 6, 4]
                x    - repeat elements max(S,0) times
                         -> [] if N < 9 else [24, 18, 15, 12, 10, 9, 8, 6, 4]
                  Ç⁸¡ - call Link 1 min(0,X) times
\$\endgroup\$
4
  • \$\begingroup\$ 15 is composite. \$\endgroup\$
    – Neil
    Feb 25 at 21:50
  • \$\begingroup\$ @Neil 1/4 + 1/6 + 1/8 + .. + 1/15 is still less than 1: ato.pxeger.com/… \$\endgroup\$
    – noodle man
    Feb 25 at 21:54
  • \$\begingroup\$ Thanks, altered! \$\endgroup\$ Feb 25 at 21:56
  • 1
    \$\begingroup\$ @noodleman Fair enough, but I didn't want his answer to be sullied by a silly typo. \$\endgroup\$
    – Neil
    Feb 25 at 22:02
5
\$\begingroup\$

Charcoal, 56 bytes

Nθ¿›θ⁸«”)‴7⊘J‹ê%υZX”≔E⁻θ⁹×⁺⁸׳ι⁺¹¹×³ιζ⊞ζ⁻×⁹θ⁵⁷W⁻ζυ⊞υ⌊ιIυ

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

Nθ¿›θ⁸«

Input n and check that it is greater than 8.

”)‴7⊘J‹ê%υZX”

Output the first 8 terms of @Mukandan314's 9-term sequence using a compressed string.

≔E⁻θ⁹×⁺⁸׳ι⁺¹¹×³ιζ⊞ζ⁻×⁹θ⁵⁷

Generate some more terms using the relation in my comment on the question (b=8 and c=3 in my case).

W⁻ζυ⊞υ⌊ιIυ

Sort and output the remaining terms.

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

JCram, 27 bytes (SBCS), 91 bytes JS

-5 thanks to Arnauld.

JavaScript solution:

n=>n<9?0:[4,6,8,9,10,12,15,18,...[...Array(n-9)].map(_=>x*(x+=3),x=8),x*3].sort((a,b)=>a-b)

Uses an idea pointed out by Neil and Mukundan314 in the comments.

JCrammed:

⌽⌊≥⍸χⒷ⁸d⊤¤β⁷D⏧¤⍆ξτ⍯⍇¯⌷3⊑¹⍤L

JCram is a research project on compressing JavaScript code for the purposes of code golf. Read more.

\$\endgroup\$
8
  • \$\begingroup\$ I think Array(n-9).fill() can be [...Array(n-9)]. (Sadly the JCrammed page doesn't respond to code pasted into the text box.) \$\endgroup\$
    – Neil
    Feb 26 at 7:16
  • \$\begingroup\$ @Neil As the page says, you have to wait for the model (30MB) to load. This can be a bit prohibitive on slow networks. And more importantly the site will not work until the model is loaded. Maybe I should add a progress bar. \$\endgroup\$ Feb 26 at 9:11
  • 1
    \$\begingroup\$ @Mukundan314 Done, the fix costed a single byte. \$\endgroup\$ Feb 26 at 9:15
  • 1
    \$\begingroup\$ The "language" showcases remarkable efficiency, particularly notable given its straightforward usability. To contextualize the efficiency of 31 bytes, I experimented with implementing the same algorithm using Japt, the best I could achieve was 47 bytes (though my Japt skills are quite rusty). \$\endgroup\$ Feb 26 at 10:30
  • 2
    \$\begingroup\$ This is JCrammed to 27 bytes. \$\endgroup\$
    – Arnauld
    Feb 27 at 1:07
3
\$\begingroup\$

Husk, 17 bytes

?øḟo=1ṁ\Ṗ¹fohpN<9

Try it online! (applied to all numbers up to 12, too slow for 13)

Not happy about how long the filter conditions ended up being, but working with infinite lists is always fun

Explanation

?øḟo=1ṁ\Ṗ¹fohpN<9
?              <9    If the input is less than 9:
 ø                     Return an empty list
                     Else:
          fohpN        Get the infinite list of composite numbers
        Ṗ¹             Get all possible subsets of length `input` from this list
  ḟo                   Find the first one for which:
      ṁ\                 The sum of reciprocals
    =1                   Is equal to 1
\$\endgroup\$
1
\$\begingroup\$

Python, 82 bytes

f=lambda x:x<9or(x<10)*b"	\n"or[*(a:=f(x-1))[:-1],b:=a[-1]+4,b//2*(b//2-2)]

Attempt This Online!

Works by splitting the largest denominator in the solution for n - 1 using the relation provided by @Neil in the question's comments; with the solution for n = 9 hardcoded in the bytestring.

Python, 83 bytes

lambda x:x<9or sorted([*b"	\n",9*x-57]+[(i*3+8)*(i*3+11)for i in range(x-9)])

Attempt This Online!

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 30 bytes

•š~ üõ•25вI9-DdiFD¨sθ;2sªDO*«ï

Try it online!

Returns a negative number for inputs < 9

This is basically just a port of Jonathan Allan's original Jelly answer. He has a great description of the algorithm and why it works on his post.

•š~ üõ•25вI9-DdiFD¨sθ;2sªDO*«ï
•š~ üõ•25в                         push [4, 6, 8, 9, 10, 12, 15, 18, 24]
          I9-                      subtract 9 from the input
             Ddi                   if the value is positive:
                F                      Repeat (input - 9) times:
                 D¨sθ                      detach the tail
                     ;2sª                  prepend 2
                         DO*               calculate the two new denominators
                            «ï             re-attach to the head as ints
                                   implicit output
\$\endgroup\$
1
\$\begingroup\$

PARI/GP, 83 bytes

A port of @Mukundan314's Python answer in PARI/GP .


83 bytes, It can be golfed more.

Attempt This Online!

f(x)={if(x<9,1,concat([4,6,8,9,10,12,15,18,9*x-57],vector(x-9,i,(3*i+5)*(3*i+8))))}
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 92 bytes

Do[x=Select[Subsets[Range@i~Select~CompositeQ,{#}],Tr[1/#]==1&];If[x!={},Return[x]],{i,#!}]&

Try it online!

Note: Tio times out for inputs 4 < n < 9 and n > 13

Returns a list of solutions found, or returns nothing if no solution exists.

A brute force method for finding a solution. Mathematica doesn't have lazy evaluation lists so I have to use a loop to iterate over the bounds.

Breakdown of the function, which takes 1 input n

Do[                                            For i in [1...n!]
    x=Select[                                  Get all
        Subsets[                                 subsets of length n of
            Range@i~Select~CompositeQ,             the set of composite numbers < i
            {#}],
        Tr[1/#]==1&];                          For which the sum of their inverses is 1.
    If[x!={}, Return[x]],                      If one or more are found, return them
{i,#!}]&
\$\endgroup\$
1
\$\begingroup\$

Scala 3, 96 bytes

x=>if(x<9)Seq(1)else Seq(4,6,8,9,10,12,15,18,9*x-57)++((1 to x-9).map(i=>(3*i+5)*(3*i+8)).toSeq)

Attempt This Online!

\$\endgroup\$
1
\$\begingroup\$

APL(NARS), 97 chars

r←f w;k;t
r←⍬⋄→0×⍳8≥w⋄r←4 6 8 9 10 12 15 18 24
→3×⍳w=k←≢r⋄t←r[k]÷8⋄r[k]←t×t+8⋄r,←8×t+8⋄→2
r←r[⍋r]

10+37+43+7=97, It use the fact that 1/rs=(1/r(r+s))+(1/s(r+s)) test:

  f 8
┌0─┐
│ 0│
└~─┘
  f 9
┌9──────────────────────┐
│ 4 6 8 9 10 12 15 18 24│
└~──────────────────────┘
  f 10
┌10────────────────────────┐
│ 4 6 8 9 10 12 15 18 33 88│
└~─────────────────────────┘
  f 20
┌20────────────────────────────────────────────────────────────────────────┐
│ 4 6 8 9 10 12 15 18 33 209 513 728 945 1505 2193 3009 3953 5025 6225 7553│
└~─────────────────────────────────────────────────────────────────────────┘
  +/÷f 10 
1
~
  +/÷f 20 
1
~
  +/÷f 500 
1
~

It is possible find one decomposition of one fraction in sum of elements of 1/d and d is not prime > 2. Example 13r10

  +/ 1r4 1r6 1r8 1r9 1r10 1r12 1r14 1r15 1r16 1r18 1r20 1r21 1r22 1r36 1r70 1r80 1r99
13r10

The more big number I found was 14r10. 15r10 and 2 it seems are too much big for algo

  +/1r4 1r6 1r8 1r9 1r10 1r12 1r14 1r15 1r16 1r18 1r20 1r21 1r22 1r24 1r28 1r35 1r36 1r48 1r99 
7r5 

It is possible find one decomposition of one fraction in sum of elements of 1/d with d natural number (so d could be prime too) example 13r129

  +/1r11 1r129 1r473 
13r129
\$\endgroup\$
1
  • \$\begingroup\$ possibly →3×⍳w=k←≢r⋄t←r[k]÷6⋄r[k]←t×t+6⋄r,←6×t+6⋄→2 can generate more little numbers \$\endgroup\$
    – Rosario
    Mar 14 at 11:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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