MAX(p_A093407)
Martin Fuller
martin_n_fuller at btinternet.com
Sat Jan 19 14:23:53 CET 2008
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>
More information about the SeqFan
mailing list