MAX(p_A093407)

[Martin Fuller]

It is certainly possible to calculate A075226 faster than calculating
all 2^n subset sums.  See the attached PARI program, which calculates
up to n=100 in under 2 minutes.

I believe sequence a(n) = max({ k : A093407(pi(k)) == n }) coincides
with A075226 whenever A075226(n)*2 > A025529(n) = H_n * A3418(n).  This
condition is met for n=2..100, so the attached b-file works for both
sequences.

%I A075226
%S A075226 3, 11, 19, 137, 137, 1019, 2143, 7129, 7129, 78167, 81401,
1085933, 1111673, 1165727, 2364487, 41325407, 41325407, 796326437,
809074601, 812400209, 822981689, 19174119571, 19652175721, 99554817251,
100483070801, 308885641403, 312058195853, 9110592033247, 9188228352007
%C A075226 Equal to max({ k : A093407(pi(k)) == n }) whenever a(n)*2 >
A025529(n).  This includes all n<=100.
%H A075226 Neil: attached b-file for n=2..100
%p A075226 Neil: attached PARI program
%O A075226 2
%K A075226 ,nice,nonn,
%A A075226 Martin Fuller (martin_n_fuller at btinternet.com), Jan 19 2008

Martin Fuller

--- hv at crypt.org wrote:

> Earlier I wrote:
> :I was prompted to look at A093407:
> :  For p = prime(n), the least k such that p divides the numerator of
> :  a sum 1/k + 1/x1 +...+ 1/xm, where x1,...,xm (for any m) are
> distinct
> :  positive integers < k.
> :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.
> 
> Ah, we have a tight upper bound of a(n) <= H_n * A3418(n); this
> becomes
> equality whenever the RHS is prime. (And so by results on H_n we also
> know the inequality is strict when n+1 is prime.) I don't know about
> lower bounds though: it is possible an appeal to Bertrand's postulate
> (er, Chebyshev's theorem) would get somewhere.
> 
> Calculating by hand, I find the sequence starts:
>   3, 11, 19, 137, 131, 1019, 2143, 7129, 6961, [a(11) < 79091]
> with offset 2, and that helps me find the related sequence A075226:
>   Largest prime in the numerator of the 2^n sums generated from the
> set
>   1, 1/2, 1/3,..., 1/n.
> 
> It follows from the definitions that a(n) >= A075226(n) whenever
> A075226(n) != A075226(n-1), and it is likely to be equal in most
> if not all of those cases.
> 
> (Interestingly, a(8) is also my current upper bound and conjectured
> actual value for A101877(7). I don't know whether that is more than
> coincidence, but I do know no similar coincidence occurs for
> A101877(8)
> or A101877(9) by virtue of the bounds I've established for those.)
> 
> Hugo
> 
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: a075226.gp.txt
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20080119/5b2087e4/attachment-0002.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: b075226.txt
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20080119/5b2087e4/attachment-0003.txt>