Value a(6) in doubt for a = A101877

[Rainer Rosenthal]

franktaw at netscape.net wrote:
> There is a shortcut available in the calculation of
> http://www.research.att.com/~njas/sequences/A101877
> 
> For each prime p, calculate a value t(p), ...

Thank you for the hints. I had just finished my little
question regarding the influence of primes in this
nice problem addressed by A101877. So i will post it
and read your remarks tomorrow (time for bed now).

Please have a look at numerator sets S_1 up to S_7 with
respect to the prime factors:

  n       primes in S_n      primes not in S_n
 --------------------------------------------
  2       2, 3               5, 7, ...
  3       2, 3, 5            7, 11, ...
  4       2 .. 13            17 and up
  5       2 .. 23            29 and up
  6       2 .. 53,61,67      59, 71 and up
  7       2 .. 137,173       139 .. 167, 179 and up

Up to n=5 all first primes are used. With n=6 there
is a first hole at 59. With n=7 there is even a gap.

Even if I my other conjecture today was no good, I
have some doubt about the optimality of a(6) when
I look at the use of primes. Shouldn't it be better
to include prime 59 and maybe get rid of the 67?
This is just a suggestion, stemming from my first
attempts to tackle a(5).

Cheers,
Rainer Rosenthal
r.rosenthal at web.de







Rainer Rosenthal <r.rosenthal at web.de> wrote:
:franktaw at netscape.net wrote:
:> There is a shortcut available in the calculation of
:> http://www.research.att.com/~njas/sequences/A101877
:> 
:> For each prime p, calculate a value t(p), ...
:
:Thank you for the hints. I had just finished my little
:question regarding the influence of primes in this
:nice problem addressed by A101877. So i will post it
:and read your remarks tomorrow (time for bed now).
:
:Please have a look at numerator sets S_1 up to S_7 with
:respect to the prime factors:
:
:  n       primes in S_n      primes not in S_n
: --------------------------------------------
:  2       2, 3               5, 7, ...
:  3       2, 3, 5            7, 11, ...
:  4       2 .. 13            17 and up
:  5       2 .. 23            29 and up
:  6       2 .. 53,61,67      59, 71 and up
:  7       2 .. 137,173       139 .. 167, 179 and up
:
:Up to n=5 all first primes are used. With n=6 there
:is a first hole at 59. With n=7 there is even a gap.
:
:Even if I my other conjecture today was no good, I
:have some doubt about the optimality of a(6) when
:I look at the use of primes. Shouldn't it be better
:to include prime 59 and maybe get rid of the 67?
:This is just a suggestion, stemming from my first
:attempts to tackle a(5).

Assuming a(6) <= 469, we need to consider multiples 1..7 of both 59 and
67, which gives:

1/n (mod 59)  1 30 20 15 12 10 17
1/n (mod 67)  1 34 45 17 27 56 48

The first set yields two subsets that sum to 0 (mod 59), being {2,5,7}
and {3,5,6,7}. In both cases the actual reciprocal sum is 1/70. The second
So I guess in this case a contribution of 1/70 just wasn't enough to reach
the required total. (If I calculate right, even taking multiples of 59
up to 9 only gives a best subset of 71/2520, slightly less than 1/35.)

Of course, you can remove the element 70 from the set and replace it
with {118,295,413} if you wish ... :)

For S_7 it gets worse: I haven't checked, but it seems likely that for
case no such option to substitute would exist. (And don't forget that
the current S_7 is just an upper bound on a(7), it isn't yet proven
minimal.)

Hugo



I was prompted to look at A093407:
by a reference in an email from Franklin T. Adams-Watters.

 From this sequence we see that a(2 = pi(3)) = 2, since 1 + 1/2 == 0 (mod 3),
and clearly no other entry in the sequence will take the value 2.

Similarly, a(pi(2)) = a(pi(5)) = a(pi(11) = 3. Since the non-empty subsets
of { 1, 1/2, 1/3 } sum to [2, 3, 5, 6, 8, 9, 11]/6, clearly we achieve
a sum == 0 (mod p) only when p is one of {2, 3, 5, 11}.

How hard is it to find a(n) = max({ k : A093407(pi(k)) == n })?
The above shows a(2) = 3, a(3) = 11. I think knowing a few more terms of
this sequence would enable some further optimisations in the calculation
of new terms of A101877.

I don't know, though, whether there is an easier way to determine a(n)
than constructing the 2^n-1 subset sums. How tight are the theoretical
limits we can impose on a(n)? It is easy to show a(n) <= n * A3418(n),
but that's a pretty loose upper bound.

Hugo