Problems & Puzzles: Puzzles

Puzzle 897. Integers as sum of special Egyptian fractions. In 1978 A. W. Johnson discovered the following special Egyptian fraction equal to unit. The special feature is that every denominator is a semiprime integer. It has been conjectured by Butler, Erdos & Graham, that a sum of such kind of fractions can produce any integer, other than 1. Q1. Can your repeat the A. W. Johnson task but allowing square denominators (as 4, 9, 25, ...)? Q2. Can you send your best solutions for any integer>1 using only semiprime denominators? I will keep your answers in this table: Integer Author Date Semiprime denominators 1 A. W. Johnson 1978 {6 21 34 46 58 77 87 115 155 215 287 391 10 22 35 51 62 82 91 119 187 221 299 689 14 26 38 55 65 85 93 123 203 247 319 731 15 33 39 57 69 86 95 133 209 265 323 901} (Qty=48, Minimal=6, Maximal=901, square-free denominatos) 2       3       4       5       Q3. Can you produce an example of sum of Egyptian fractions equal to 1, using only denominators composed by 3 prime factors?

---

Emmanuel wrote on October 20, 2017.
 

Q1 It is not possible to obtain 1 (or any other natural number) as a sum of reciprocals of semiprimes when one of the fractions is  1/4. This is because the other fractions will always sum to a fraction with denominator  odd  or  2 times an odd number : plus 1/4  then always returns a fraction with 4  in the denominator. The same argument applies to sums of reciprocals that would use the fraction  1/9, 1/25, ...

 

Q3 If found a set of  73082  natural numbers that have exactly three (different) prime divisors whose reciprocals sum to 1. But, this is a little bit too much to print out in full.  Therefore, I send it in annex. (See it here A or B)

***

Jan van Delden wrote:

My Contribution to Q1 and Q3. Very long, but I think it is theoretically interesting. I couldn’t find a source for the method employed by A.W. Johnson. So this might be new.. On the other hand an exhaustive search would have been to time consuming (now and in 1978).

 

Q1/(Q2):

 

The solution consisting of a set S of 48 semiprimes by A.W. Johnson can be visualized in a Graph:

See Graph A

The numbers at the vertices are the primefactors of the semiprimes, the edges connecting the vertices represent the semiprimes.

This solution is generated by 14 primes, the largest one being 53.

 

In this tekst we assume that the semiprimes are distinct and that the multiplicity of a prime divisor is 1.

Let’s call P the set of primefactors p.

 

For each primefactor p we can split S into:

S(p):                   The set of semiprimes having p as divisor

S(not p):              S\S(p), the remaining semiprimes

 

For each primefactor p we define:

T(p):                      The set of primes q such that p*q is an elment of S(p)

 

A Graph visualizing this:

See Graph B

The red edges represent S(29). The vertices connected to 29 comprise the set T(29): {2,3,7,11}.

The blue edges represent S(not 29). See attachment for small video which shows all T(p).

 

If we add the number of edges for all S(p), each edge is counted twice.

 

There is a relation between p and q in T(p):  sum(1/q, q in T(p)) mod p=0.

Proof:

 

Given: sum(1/s, s in S)=n, with n a natural number.

Split this sum for s in S(p) and s in S(not p):

sum(1/s, s in S(p))+sum(1/s, s in S(not p))=n         rewrite:

1/p*sum(1/q, q in T(p))+sum(1/s, s in S(not p))=n

 

This expression can be written as:

 

1/p*(A/B)+C/D=1  with  p not a divisor of B or D.

 

B = prod(q, q in T(p))
A = sum(B/q, q in T(p))

Multiply numerator and denominators with pBD:

 

AD+pBC=pnBD

Compute the residue mod p:

 

AD mod p=0 

 

It is known that p is not a divisor of D, so we must have A mod p=0 (or  p is a divisor of the numerator of sum(1/q, q in T(p)).

 

Since gcd(q,p)=1 we know that the inverse of q mod p exists, therefore the inverse of B mod p exists.

(or the denominator B is unequal to 0 mod p). The numerator A = 0 mod p.
So finally sum(1/q, q in T(p)) mod p = A/B mod p = 0.

 

So a necessary condition for the sum of reciprocals of distinct semiprimes s in S to be an integer>0 is:

For all p with p|s we must have p is a divisor of the numerator of sum(1/q, q in T(p)).

 

This condition is also sufficient.

 

The least common multiple of both denominators in the sum is equal to the primes in P (*), each p has multiplicity 1,

for each representation of the sum as a split over S(p) and S(not p).

With this denominator for each fixed prime p, p will also divide the numerator:

 

With gcd(B,D)=E and B=B’E, D=D’E, A=A’p

1/p*(A’p/(B’E))+C/(D’E) =  (A’pD’+pB’C) / (pB’DÉ)= (A’D’+B’C) /(B’D’E)

 

So each factor p in the denominator will divide the numerator, so the denominator is a factor of the numerator, thus the sum is an integer>0.

(*) Essential part of the proof. One should show explicitly the construction of B’,E and D’ in terms of T(p), P\p.

 

Some considerations for a program to search for solutions:

 

The point of all this that this gives us an opportunity to split a search for a full solution of semiprimes into parts (for each p). Moreover the sets T(p1) and T(p2) might intersect, so often there one can append the set of primes making the modular equation equal to 0. On the downside there is no knowledge of the size of the T(p) we search for.

 

If one looks for solutions with as few semiprimes as possible, than it is a good idea to assume that there exists a p0 such that for p>=p0  the primes q in T(p) are smaller than p0. In the example by A.W. Johnson p0=19. Furthermore the number of elements of T(p) can’t be equal to 1 and will probably be unequal to 2;  For large primes p we have that #T(p)=2 means that T(p)={2,p-2}, giving a large semiprime (p-2)*p which we probably don’t want. For small primes p we want T(p) to have lots of factors.

I couldn’t find a solution with less than 48 semiprimes. However:

 

I found 4 other solutions with 48 semiprimes, the best one:

 

{6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 77, 82, 85, 86, 91, 93, 95, 115,

119, 123, 133, 141, 143, 145, 155, 203, 209, 215, 235, 247, 287, 299, 323, 391, 493, 517, 611, 731}

 

With the following Graph C:

 

 

The primeset P has 14 elements, the largest prime factor is 47. The largest semiprime is 731 (17*43).

 

The other 3 solutions are generated for a primeset with the largest prime factor equal to 59 (p0=19, 23 or 29).

 

I tried Q2, but this requires some more finetuning to my program, maybe search for a solution with strictly increasing sizes of T(p) with decreasing p. Or more patience.

 

Q3:

 

Three distinct factors:

 

s=p*q*r  with p<q<r and all s in S are distinct, for each prime divisor p a modular relation holds between p and T(p).

 

One factor with muliplicity 3:

 

The set S can not contain a factor s=p*p*p, if all s in S are distinct.
The sum splits into 1/p^3+A/B=n with p^3 not a divisor of B which gives   B+p^3*A=p^3nAB  which leads to a contradiction.

 

One factor with multiplicity 2:

 

s=p^2*q and all s in S:

1/p^2*(A/B)+1/p*(C/D)+E/F=1, p not a divisor of B or D or F. Multiply with p^2BDF:

 

ADF+pBCF = p^2BD (F- E)

 

Modulo p     this reads A mod p=0.

Modulo p^2 this reads AD+pBC mod p^2=0  (or  A’D+BC mod p=0 with A=A’p)

 

We need several factors of the form p^2*q, but that is possible.

For instance if p=2, the first condition states that the size of T(2^2) should be even.
For instance if p=2, the second condition states A’+ C mod 2=0 (since D and B are odd), so A’=C mod 2.

 

We could search for p<p0, q<q0, r<=r0, q<r, s=p*q*r and either p=q or p<q. 
If we include this type of  s the total size of S decreases dramatically compared with p<q<r.

The size of S is equal to 357 if p0=q0=19 and r0=59. The sum of the smallest 309 elements of S will be larger than 1.
The size of S is equal to 400 if p0=q0=23 and r0=53. The sum of the smallest 336 elements of S will be larger than 1.
However I didn’t find the time to implement this. (It will be tricky).

 

See Video D

 

 

***

 

---