sum of unit fractions

[hv at crypt.org]

"David Wilson" <davidwwilson at comcast.net> wrote:
:I have been thinking about this problem of expressing an integer as a
:sum of reciprocals of distinct positive integers with least possible
:maximum denominator.  I'm sure the ideas here have all been explored
:before, but here goes:
[...]
:These observations beg the questions:
:
:(1) Which integers are good?  This has the potential for an OEIS
:sequence.
:
:(2) Is the Above Theorem sufficient to show an integer is bad?

It is important to allow for non-singular prime powers as well.

For a given prime p, consider the sequence of reciprocals
  R = [ i^-1 (mod p) for i = 1 .. n ]
Then np is guaranteed good if there exists a non-empty subsequence
S of R such that sum(S) == 0 (mod p) that includes r_n. np is
guaranteed bad if there is no such subsequence _and_ n < p; if n >= p
we must also consider the potential contribution of p^2 (and maybe
higher powers), but since for n = p - 1, R must be a permutation of
[ 1 .. p-1 ], I think it is clear that:
  Defining gpp(n) as the greatest prime power of n;
  Given a = np such that gpp(a) = p, a is 'good' iff:
    1) p = 2 and n > 1
    2) p > 2 and n >= p-1
    3) or there exists a non-empty subsequence of [ i^-1 (mod p), i=1..n ]
       that sums to 0 (mod p) (**)
  Given a = np^k such that gpp(a) = p^k, a is good iff np is good.

Since 1^-1 == 1 (mod p) for all p, it is clear that p^k (k > 0) is never
good.

(**) I'm not sure if it is possible for a to be bad when a = pq, p > q,
such that there exists a good subsequence of [ i^-1 (mod p), i=1..q ],
but there does not exist a good subsequence of [ i^-1 (mod q), i=1..p ].

The approach I used to test optimality of a(N) for N = 1 .. 5 was:
- set Limit successively to 1, 2, ...
- calculate Q_{p^k} as the subsequence of 1..Limit for which gpp(n) = p^k
- set H(Limit) = sum_{i=1..Limit}{ 1/i }
- set Kept = 0/1, Discarded = 0/1
- recursively for each p^k such that Q_{p^k} is non-empty, in decreasing order
  - calculate Req = the required sum modulo p :
    - if denominator(Kept) is not divisible by p^k then Req = 0
      else Req = numerator(Kept) ^ -1 (mod p)
  - for Q_{p^k}, calculate R, the sequence (q_i/p^k) ^ -1 (mod p)
  - save the values of Kept and Discarded
  - for each subsequence S of R such that sum(S) == Req (mod p)
    - for each q_i in Q, add 1/q_i to Kept or Discarded depending
      on whether the corresponding r_i was used ('kept') in S
    - if H(Limit) - Discarded = N then terminate successfully
    - if H(Limit) - Discarded > N then recurse to the next lower prime power
    - restore Kept and Discarded to the saved values
  - derecurse
- and try the next value for Limit

(All calculations are done using high precision rationals; various
optimisations are elided.)

Note that this approach guarantees that denominator(H(Limit) - Discarded)
is free of any prime power >= p^k before we recurse to the next lower
prime power.

For example when calculating a(3) we get to Limit = 24 and assign the
numbers so:
23^1 : Q = [ 23 ]; R = [ 1 ]
19^1 : Q = [ 19 ]; R = [ 1 ]
17^1 : Q = [ 17 ]; R = [ 1 ]
 2^4 : Q = [ 16 ]; R = [ 1 ]
13^1 : Q = [ 13 ]; R = [ 1 ]
11^1 : Q = [ 11, 22 ]; R = [ 1, 6 ]

 3^2 : Q = [ 9, 18 ]; R = [ 1, 2 ]
 2^3 : Q = [ 8, 24 ]; R = [ 1, 1 ]
 7^1 : Q = [ 7, 14, 21 ]; R = [ 1, 4, 5 ]
 5^1 : Q = [ 5, 10, 15, 20 ]; R = [ 1, 3, 2, 4 ]
 2^2 : Q = [ 4, 12 ]; R = [ 1, 1 ]
 3^1 : Q = [ 3, 6 ]; R = [ 1, 2 ]
 2^1 : Q = [ 2 ]; R = [ 1 ]
 x^0 : Q = [ 1 ]; R = [ 1 ] (nominally)

We can quickly discard all p^k down to and including 11^1, but when
considering 3^2 we find that r_1 + r_2 == 0 (mod 3), so keeping 9 and 18
is an option; similarly we can keep 8 and 24, must discard 7, 14, 21,
and can keep 5, 10, 15, 20 (or optionally [ 5, 20 ] or [ 10, 15 ]).

At this point H(24) - Discarded = 37/12, so for 2^2 we must find
a subsequence that sums to 37^-1 == 1 (mod 2). We can satisfy that by
keeping either the 4 or the 12, but discarding the latter gives us the
required sum, and so we have a solution.

Hugo