# Generalization on older SE question: not just covering $1$, but all rational numbers.

Older SE question lies here.

So I will change the question such that you can understand the question better:

$$\sum_{c\space\subset \Bbb{Co}}\frac{1}{c}\le k$$

-where your goal is to get to $k$ with the desired specific composites

-You must add up the specific composites (group $\Bbb{Co}$) such you come as close to the number, but not above the number. (The number being $k$)

-c are the specific subset of composites that are designed to fit $k$

If that doesn't make sense, allow me to give the example from this problem

You are trying to fit $k=1$ to the composite sum. This example is just arbitrary.

The question and the answer give the sum to $$\frac{1}{4}+\frac{1}{6}+\frac{1}{8}+\frac{1}{9}+\frac{1}{10}+\frac{1}{12}+\frac{1}{14}+\frac{1}{15}+\frac{1}{39}+\frac{1}{6552}=1$$

The reason for this the individual terms are as they are because

-You must add up specific composite reciprocals such that the nest composite reciprocal that you pick for the sum must make the sum as close to the $k$ value as possible.
(You can't do $\frac{1}{4}+\frac{1}{8}+\frac{1}{8}=1$ because $6\lt 8, \frac{1}{4}+\frac{1}{6}\lt 1$ also.) If after some terms you receive a completely equal summation to the $k$ value you are trying to reach, you terminate the sum.

My question is a proof that $\forall k\in\Bbb{Q}, k\gt 0,$ it can be represented as a finite sum under the previously given conditions. I don't know where to start because I don't know number theory well enough yet.

• What kind of number is $k$? – Gerry Myerson Dec 5 '15 at 7:54
• k is real @GerryMyerson – user285523 Dec 5 '15 at 7:55
• So, we're talking about infinite sums? – Gerry Myerson Dec 5 '15 at 7:58
• @GerryMyerson No, finite sums. But under the above conditions, you should (picking the terms of the finite sums from the $k$ given) eventually get exactly $k$ from the summation. After you get there, you terminate the sum. – user285523 Dec 5 '15 at 17:13
• Note that this is a greedy Egyptian fraction expansion with constrained denominators. Such problems can be exceedingly difficult. See en.wikipedia.org/wiki/… and the following section, and en.wikipedia.org/wiki/Odd_greedy_expansion . – Eric Towers Dec 5 '15 at 19:58

Edit 20151206:

This is still not an answer. However, I have polished my code and have extended partial results significantly. There seems to be an unexpected interaction between transaction protection and aborts generated to limit computation time. I'm not willing to post the new code here until this is resolved.

However: As described here, we should expect the leading contiguous sequence of the sets of composites to go exponentially in $k$. I observe that (for denominators below a few hundred) over the range $(0,6]$ the finished sequence is typically only a few more composites than this initial sequence. In fact in this range, the length of finished sequence is roughly $16 \mathrm{e}^k$. For example, for $k$ near $6$, many of the $C_k$ have length around 6200.

The last composite in the various lists is very irregular. For instance, the last member of $C_3$ has 665,692 digits and for $k$ around $3$, the last member of $C_k$ seems to be between $10^5$ and $10^7$ digits. The number of digits in the last member seems to be increasing triply exponentially ($\mathrm{e}^{\mathrm{e}^{\mathrm{e}^{\text{stuff involving$k$}}}}$) but I have a far less confident grip on this information.

This is not an answer. This is a restatement of the problem and a couple of partial results.

Let $C$ be the set of positive composite integers (where we take the OP's example with $1$ to inform us that $1 \not \in C$). For each non-negative $k \in \Bbb{Q}$, we construct a sequence,

• $C_k = (c_1(k), c_2(k), \dots)$, of elements of $C$, where if $\sum_{i=1}^{j-1}\frac{1}{c_i(k)} = k$, we terminate the sequence. Otherwise,
• $c_j(k) = \min \{c \in C \mid \sum_{i=1}^{j-1}\frac{1}{c_i(k)} + \frac{1}{c} \leq k \}$ (taking the usual convention than an empty sum is zero).

Question: Are all the $C_k$ finite?

OP states $C_1 = (4,6,8,9,10,12,14,15,39,6552)$ and I have verified this by computer search. Using the same code, I have found \begin{align} C_{3/2} = (&4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, \\ &28, 30, 32, 140, 17012, 564151318, 1525808048406006071, \\ &5653933344267037771836579905409789600), \\ C_2 = (&4,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30,32,33,34,35,36,38,39, \\ &40,42,44,45,46,48,49,50,51,52,54,55,56,57,58,60,62,684,462842, \\ &124024842563,30315950771563439024473, \\ &1292910513699325483619309497975469150613738265, \\ &2817869662560599109540560785109867630063576905426518917026230074786087943930323001317330400), \\ \text{and}\quad&{} \\ C_{5/2} = (&4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, \\ &28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, \\ &54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, \\ &78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100, \\ &102, 104, 105, 106, 108, 110, 111, 112, 114, 115, 116, 117, 164, 23802, \\ &455151859, 295912174724563683, 98351380501177755768677358787508948, \\ & \dots \text{(and 10 more integers, the largest of more than 36000 digits)}).\end{align} I have no reason to believe (runtimes constrained to a few minutes) that $C_3$, $C_{7/2}$, $C_4$, $C_5$, $C_6$, $\dots$, $C_{20}$, are finite. (Surprisingly, none of these exhausted memory.) As a wild guess, this greedy construction may fail to produce a finite list for most rationals starting near $3$. [This is false, see edit above.]

Mathematica code used:

cList[k_] := TimeConstrained[
Module[{
c,   (* running partial solution *)
finger,  (* run a finger through the composites *)
remainder  (* difference between k and sum of reciprocals in c *)
},
c = {};
remainder = k;
finger = 4;  (* Might as well skip to first composite. *)

While[remainder > 0,
If [1/finger <= remainder,
(* Print[{finger, remainder}]; *)  (* Diagnostic *)
AppendTo[c, finger];
remainder -= 1/finger
];
If[remainder > 0,
(* If the remainder is tiny, jump to large enough composites. *)
finger = Max[{finger + 1, Ceiling[1/remainder]}];
(* Skip primes. *)
While[PrimeQ[finger], finger++];
];
];
c
],
(* Limit run time to 300 seconds *)
300]


That code could easily be better organized; it's the first thing that worked.

• I suppose your study of this question can show why I was so interested by it, no? – user285523 Dec 13 '15 at 6:20