Egyptian Fractions with Denominators from Sequences Closed Under Doubling

David Eppstein Department of Computer Science University of California, Irvine Irvine, CA 92697 USA

                       eppstein@uci.edu

Abstract Resolving a conjecture of Zhi-Wei Sun, we prove that every rational number can be represented as a sum of distinct unit fractions whose denominators are practical numbers. The same method applies to allowed denominators that are closed under multiplication by two and include a multiple of every positive integer, including the odious numbers, evil numbers, Hardy-Ramanujan numbers, Jordan-Pólya numbers, and fibbinary numbers.

1 Introduction

An Egyptian fraction represents a rational number as a sum of distinct unit fractions; we allow 1/1 as a unit fraction, but no larger integers. Several past works have studied Egyptian fractions with restricted denominators. In the mid-1950s, in connection with the still-open question of the termination of a greedy algorithm for finding representations with odd denominators, Breusch and Stewart showed that all rational numbers with odd denominators have Egyptian fractions with odd denominators [2, 13]. One of Graham’s first publications [5] Egyptian showed that Egyptian fractions with square denominators exist for all rationals in the intervals [0, π^{2}/6−1) and [1, π^{2}/6), and characterized Egyptian fractions with kth-power denominators for k > 2. The last posthumous publication of Erdős [3] showed that all natural numbers have Egyptian fraction representations whose denominators are the products of three prime numbers.

We find two properties of integer sequences that allow all rational numbers to be represented as Egyptian fractions with denominators from the sequence, or all rational numbers up to the natural limit of such representations, the sum of reciprocals of sequence elements.

• Sequence S is closed under doubling (or doubling-closed) when, for all x ∈ S, the quantity 2x is also a member of S. That is, doubling a sequence element produces another sequence element.

• Sequence S is productive when, for all x ∈ ℤ^{+}, there exists y ∈ ℤ^{+} such that xy is a member of S. That is, every integer has a multiple that is in the sequence.

Well-known sequences with both properties include the practical numbers, odious and evil numbers, Hardy-Ramanujan numbers, Jordan-Pólya numbers, and fibbinary numbers (see Section 2 for details on these sequences), allowing us to find Egyptian fractions using their elements as denominators. Our results positively resolve a conjecture of Sun according to which all rational numbers have Egyptian fractions with practical denominators [14]. Two other conjectures of Sun on Egyptian fractions whose denominators are the primes minus one or the primes plus one remain open; the sequences in those conjectures are not closed under doubling.

Our construction method multiplies the numerator of a fraction by a power of two, divides by the denominator, and separately finds the binary representations of the quotient and remainder. This method was used by Stewart to find Egyptian fractions with all denominators even [13] and called the “binary remainder method” in our earlier survey on Egyptian fraction construction algorithms [4].

2 Doubling-closed and productive sequences

We briefly survey some notable integer sequences that are closed under doubling and productive. For these sequences, we also consider the convergence or divergence of the sum

∑_{x∈S} \frac{1}{x}

of reciprocals of elements of a sequence S, as this sum (when finite) forms a natural upper bound on Egyptian fractions with denominators in S. Some of these sequences are subsequences of others, but for representation by Egyptian fractions this is not redundant, because they will represent different ranges of rational numbers.

• The practical numbers (\underline{A005153}) are the numbers n such that all integers m ≤ n may be represented as sums of distinct divisors of n. For n in this sequence, all rationals m/n ∈ (0, 1) have Egyptian fraction representations with denominators that are divisors of n. Several tables of Egyptian fraction expansions based on this principle were given by Fibonacci [11], but the first explicit definition of the practical numbers was by Srinivasan in 1948 [12]. A positive integer n is practical if and only if, for each prime p that divides n, the sum of divisors of the (< p)-smooth part of n is at least p−1 [13, 10]. This property is clearly preserved on multiplication by two, and can be obtained from any positive integer n by multiplying it by a power of two bigger than all of its prime divisors. Therefore, the practical numbers are doubling-closed and productive. They have logarithmic asymptotic density [15], like the prime numbers, so their sum of reciprocals diverges.

• The odious numbers (\underline{A000069}) have binary representations with an odd number of nonzero bits, and the evil numbers (\underline{A001969}) have binary representations with an even number of nonzeros. Although named by Berlekamp, Conway, and Guy [1, p. 431], their study goes back at least to Prouhet in 1851 [16]. Doubling an odious or evil number shifts its binary representation without changing its parity. For any n and sufficiently large k, the number n(2^{k} + 1) is evil, with a binary representation formed by two copies of the binary representation of n, separated by zeros, so the evil numbers are productive. The smallest multiplier whose product with n is odious (\underline{A178757}) was proven to exist by Morgenbesser, Shallit, and Stoll [8]. Because the odious and evil numbers have density \frac{1}{2} in the integers, the sums of their reciprocals diverge.

• The Hardy-Ramanujan numbers (\underline{A025487}) have prime factorizations 2^{e_{2}}3^{e_{3}}5^{e_{5}} ⋯ with e_{2} ≥ e_{3} ≥ e_{5} ≥ · · ·. This ordering of exponents is preserved by doubling. A Hardy-Ramanujan multiple of any n can be obtained from the prime factorization of n by replacing each exponent with its maximum with all later exponents. Hardy and Ramanujan [6] proved that the set of these numbers below any given threshold N has cardinality exponential in \sqrt{log N/ log log N}, sufficiently sparse that their sum of reciprocals converges to a finite bound.

• The Jordan-Pólya numbers (\underline{A001013}) are the orders of automorphism groups of trees, studied by Jordan and Pólya [7, 9], and are equivalently the products of factorials. Because 2 is a factorial, they are preserved by doubling. Each n has a multiple in this sequence, for instance n!. Their sum of reciprocals converges.

• The fibbinary numbers (\underline{A003714}) have binary representations with no two consecutive nonzero bits. Doubling a fibbinary number shifts its binary representation without introducing new consecutive nonzeros. Multipliers for each n showing that \underline{A003714} is productive, and an argument that these multipliers exist for all n, are given in \underline{A300867}. \underline{A003714} is so-named because the number of them with a given number of bits is a Fibonacci number. This implies that, up to any threshold N, there are O(N^{log_{2} φ}) ≈ N^{0.694242} fibbinary numbers, where φ is the golden ratio, few enough that their sum of reciprocals converges.

• The Moser-de Bruijn sequence (\underline{A000695}) consists of sums of distinct powers of four, and is not closed under doubling. Modifying it by including both the numbers of this form, and the doubles of numbers of this form, produces \underline{A126684}, which is closed under doubling. The existence in \underline{A126684} of a multiple of any n follows from the same argument as the fibbinary numbers: the numbers of the form (4^{i} − 1)/3, having binary representations that alternate between 0’s and 1’s, have by the pigeonhole principle two elements that are congruent modulo n, and the difference of these two elements is a multiple of n in \underline{A126684}. \underline{A126684} grows quadratically, and is the fastest-growing sequence whose sums of pairs of elements include all positive integers. Its quadratic growth implies that its sum of reciprocals converges.

• \underline{A116882} consists of the positive products 2^{k} · ℓ for which 2^{k} ≥ ℓ, and is clearly closed under doubling. For every n, it contains the multiples 2^{k}n of n, for all k large enough that 2^{k} ≥ n. When the numbers in \underline{A116882} up to some threshold N are factored into a power of two and an odd part, there are O(log N) choices for the power of two and O(\sqrt{N}) choices for the odd part, giving O(\sqrt{N} log N) total choices, few enough that the sum of reciprocals converges.

3 Existence of representations

Theorem 1. Let S be a doubling-closed and productive set of positive integers, and let q be a rational number with 0 < q < ∑_{s∈S} 1/s. Then q has a representation as an Egyptian fraction with denominators in S.

Proof. Let m = min S. Let P be a prefix (that is, an initial subsequence) of the ascending sorted order of S, the longest prefix for which q ≥ ∑_{p∈P} 1/p. Let q′ = q − ∑_{p∈P} 1/p be the remaining fraction to represent after choosing unit fractions with denominators in P. We find a representation q′ = x/y of q as a fraction (not necessarily in lowest terms), where y has a nontrivial odd factor and where my ∈ S. To do so, let x′/y′ be the lowest-terms representation of q′, multiply both x′ and y′ by three if y′ is a power of two, find a multiple rmy′ of my′ that belongs to S, and let x = rx′ and y = ry′.

Let k = ⌊log_{2} y⌋, and divide 2^{k}mx by y giving 2^{k}mx = ay + b. Then x/y < 1/m (else we would have included more elements in P), and 2^{k} < y, so 2^{k}mx < y^{2} and a < y. As with any remainder of division we have also b < y. Let A = {a_{1}, a_{2}, … } and B = {b_{1}, b_{2}, … } be sets of integers with a = ∑_{i} 2^{a_{i}} and b = ∑_{j} 2^{b_{j}}, the sets of exponents in the binary representations of a and b. By our choice of k, and because both a and b are less than y, each of the exponents in A and B is at most k.

Represent q as a sum of unit fractions, by expanding

q = (∑_{p∈P} \frac{1}{p}) + \frac{x}{y}

= (∑_{p∈P} \frac{1}{p}) + \frac{2^{k}mx}{2^{k}my}

= (∑_{p∈P} \frac{1}{p}) + \frac{ay + b}{2^{k}my}

= (∑_{p∈P} \frac{1}{p}) + (∑_{a_{i}∈A} \frac{1}{2^{k−a_{i}}m}) + (∑_{b_{j}∈B} \frac{1}{2^{k−b_{i}}my} ).

All denominators in this representation are members of P, or can be obtained by repeatedly doubling m or my, so all belong to S. Within each of the three summations of this representation, the unit fractions come from distinct elements of a set P, A, or B, and are therefore distinct from each other. The denominators of unit fractions coming from P cannot coincide with any other denominators, because if they did we would have been able to include more elements in P. No denominators in the second summation can equal a denominator in the third summation, because of the nontrivial odd factor of y. Therefore, we have represented q as a sum of distinct unit fractions all of whose denominators belong to S.

Corollary 2. Every positive rational number has an Egyptian fraction representation with practical denominators, an Egyptian fraction representation with odious denominators, and an Egyptian fraction representation with evil denominators.

Corollary 3. For each of the sequences \underline{A025487}, \underline{A001013}, \underline{A003714}, \underline{A126684}, and \underline{A116882}, every positive rational number that is less than the sum of reciprocals of the sequence has an Egyptian fraction representation in which all denominators belong to the sequence.

References

[1] E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for your Mathematical Plays, Volume 1: Games in General, Academic Press, 1982.

[2] R. Breusch, A special case of Egyptian fractions, solution to advanced problem 4512, Amer. Math. Monthly 61 (1954), 200–201.

[3] S. Butler, P. Erdős, and R. L. Graham, Egyptian fractions with each denominator having three distinct prime divisors, Integers 15 (2015), A51:1–A51:9.

[4] D. Eppstein, Ten algorithms for Egyptian fractions, Mathematica in Education and Research 4(2) (1995), 5–15.

[5] R. L. Graham, On finite sums of reciprocals of distinct nth powers, Pacific J. Math. 14 (1964), 85–92.

[6] G. H. Hardy and S. Ramanujan, Asymptotic formulae for the distribution of integers of various types, Proc. London Math. Soc. 16 (1916), 112–132.

[7] C. Jordan, Sur les assemblages de lignes, J. Reine Angew. Math. 1869(70) (1869), 185–190.

[8] J. F. Morgenbesser, J. Shallit, and T. Stoll, Thue-Morse at multiples of an integer, J. Number Theory 131 (2011), 1498–1512.

[9] G. Pólya, Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen, Acta Math. 68 (1937), 145–254.

[10] W. Sierpiński, Sur une propriété des nombres naturels, Ann. Mat. Pura Appl. 39(1) (1955), 69–74.

[11] L. E. Sigler, Fibonacci’s Liber Abaci, Springer-Verlag, 2002.

[12] A. K. Srinivasan, Practical numbers, Current Science 17 (1948), 179–180.

[13] B. M. Stewart, Sums of distinct divisors, Amer. J. Math. 76(4) (1954), 779–785.

[14] Z.-W. Sun, A conjecture on unit fractions involving primes. Unpublished manuscript, linked from OEIS sequence \underline{A005153}, November 6 2015.

[15] A. Weingartner, Practical numbers and the distribution of divisors, Q. J. Math. 66(2) (2015), 743–758.

[16] E. M. Wright, Prouhet’s 1851 solution of the Tarry-Escott problem of 1910, Amer. Math. Monthly 66 (1959), 199–201.

2010 Mathematics Subject Classification: Primary 11A67; Secondary 11A63, 11B83.

Keywords: Egyptian fraction, practical number, odious number, evil number, Hardy-Ramanujan number, Jordan-Pólya number, fibbinary number.

(Concerned with sequences \underline{A000069}, \underline{A000695}, \underline{A001013}, \underline{A001969}, \underline{A003714}, \underline{A005153}, \underline{A025487}, \underline{A116882}, \underline{A126684}, \underline{A178757}, and \underline{A300867}.)

Received July 19 2021; revised version received September 23 2021. Published in Journal of Integer Sequences, September 24 2021.

Return to Journal of Integer Sequences home page.