8

This question arose through a response to this post.

For which integers $N>1$ does the fraction $\frac 1N$ appear in the Egyptian Fraction expansion of $\frac {N-1}{N}$?

To specify: As such expansions are not unique, I should say which one I refer to. Here we consider the expansion obtained through the greedy algorithm.

Thus $$\frac 12=\frac 12\;\;\&\;\;\frac 34=\frac 12+\frac 14\;\;\&\;\;\frac {11}{12}=\frac 12+\frac 13+\frac 1{12}$$ are easy examples.

A quick search for $N<100$ yields $N=\{2,4,12,84\}$ as examples. Taking that (short) list to OEIS leads to $[A053631][1]$, the sequence $a_i$ starting with $a_1=2$ and having the property that, for $i>1$, $\{a_{i-1}+1,a_i,a_i+1\}$ are a Pythagorean triple. That sequence continues from $84$ as $3612,\, 6526884,\, 21300113901612,\dots$ and it is easy to verify that those three, at least, are examples for the present question as well.

Are these all examples? Are there others?

Edit: as remarked in the comments, in each of the cases cited above, $\frac 1N$ appears as the final term in the expansion.

PinkyWay
  • 4,565
lulu
  • 70,402
  • Well, Egyptian fraction decompositions aren't unique, but I'm guessing that each $N$ has at least one such decomposition. – Akiva Weinberger Feb 07 '16 at 16:08
  • @AkivaWeinberger Thank you. I meant the expansion obtained via the greedy algorithm, and will edit my question accordingly. – lulu Feb 07 '16 at 16:09
  • Right, 'cause the greedy algorithm gives $\frac45=\frac12+\frac14+\frac1{20}$, but we also have $\frac45=\frac12+\frac15+\frac1{10}$. – Akiva Weinberger Feb 07 '16 at 16:13
  • @AkivaWeinberger Sure. Indeed, for most $N$ I'd expect that applying the greedy algorithm to $\frac {N-2}N=\frac {N-1}{N}-\frac 1N$ would give an example. – lulu Feb 07 '16 at 16:18
  • I'm curious why you didn't include $N=2$ in your list. (By the way, it seems that, for the ones less than $100$, the fraction $\frac1N$ is always last in the expansion. Is this true for the others as well?) – Akiva Weinberger Feb 07 '16 at 16:26
  • @AkivaWeinberger I should have included $2$, I'll add it. Yes. That property holds for every example I am aware of. I'll add that as well. – lulu Feb 07 '16 at 16:30
  • And they all begin the same, except for the last fraction in the expansion:$$\frac12+\frac13+\frac17+\frac1{43}+\frac1{1807}+\dotsb+\frac1N$$The denominators of each of those (except for the last) are of the form $\frac{N_i}2+1$ for $N_i$ in your list. – Akiva Weinberger Feb 07 '16 at 16:40
  • @AkivaWeinberger True...I had spotted that but feared it was an artifact of the Pythagorean subsequence and not a property of my numbers. – lulu Feb 07 '16 at 17:01

1 Answers1

5

Note that $2 \cdot 2=4, 4 \cdot 3=12, 12 \cdot 7=84, 84 \cdot 43=3612, 3612 \cdot 1807=6526884$. If $k$ is a solution, then it is $\frac {k-2}k + \frac 1k$, where we don't care how $\frac {k-2}k$ is expressed. Then let $m=k(\frac k2+1)$, which is a multiple of $4$ because $k$ is. We have $\frac {m-1}m=\frac {k(\frac k2+1)-1}{k(\frac k2+1)}=\frac {k-2}k+\frac 1k+\frac 1{k+2}=\frac {k-2}k+\frac 1{k/2+1}+\frac 1{k(\frac k2+1)}=\frac {k-2}k+\frac 1{k/2+1}+\frac 1m$, so $m$ is a solution. This shows there are an infinite number of solutions, but does not show there are no others

Ross Millikan
  • 374,822
  • Thanks for this. Not clear to me that the "pythogorean" sub list is generated this way...I'll take a look. – lulu Feb 07 '16 at 17:00
  • Yes, this is exactly the recurrence for A053631. I have $m=k+\frac {k^2}2$ as shown under PROG in the listing. – Ross Millikan Feb 07 '16 at 19:15
  • Right you are. Thanks again. I have yet to find any examples of the type I want that don't arise this way.. – lulu Feb 07 '16 at 19:40