[seqfan] Re: Jacobsthal function

[Charles Greathouse]

I don't really think of that as easy! I can find phi(n) for a 20-digit
n in a second, but I can't count to a 20-digit number in my lifetime
(barring much faster computers). And phi(n) is, to my mind, only
borderline easy since large numbers are hard to factor.

Charles Greathouse
Analyst/Programmer
Case Western Reserve University

On Sat, Sep 8, 2012 at 11:11 PM, Neil Sloane <njasloane at gmail.com> wrote:
> Charles, My guess is that the "easy" keyword was based
> on the fact that you can compute jacobsthal(n) in about n/2 steps,
> and that that seems an easy calculation.
>
> If you find out more about the complexity of this function, please add a
> comment to the entry
>
> Neil
>
> On Sat, Sep 8, 2012 at 9:44 PM, Charles Greathouse <
> charles.greathouse at case.edu> wrote:
>
>> On the face of it that gives information only on the computation of
>> A048670.
>>
>> Charles Greathouse
>> Analyst/Programmer
>> Case Western Reserve University
>>
>> On Sat, Sep 8, 2012 at 9:06 PM,  <allouche at math.jussieu.fr> wrote:
>> > Hi
>> > Does the following help?
>> >
>> http://www.ams.org/journals/mcom/2009-78-266/S0025-5718-08-02166-2/S0025-5718-08-02166-2.pdf
>> >
>> > best
>> > jp
>> >
>> >
>> > Charles Greathouse <charles.greathouse at case.edu> a écrit :
>> >
>> >> The Jacobsthal function, A048669, is an important sequence which
>> >> appears in many contexts (e.g., bounding the size of prime gaps;
>> >> finding the least prime in an arithmetic progression; bounding the
>> >> state complexity of regular languages). It is defined as the maximal
>> >> distance between numbers relatively prime to n.
>> >>
>> >> How is it computed? The sequence is marked easy, and yet the only
>> >> program listed is very slow, doing calculations on all numbers up to
>> >> n.
>> >>
>> >> A search reveals a body of literature on computing A048670 =
>> >> a(prime(n)#) efficiently, but nothing on the sequence itself. Perhaps
>> >> it is obvious but I can't immediately see it.
>> >>
>> >> Charles Greathouse
>> >> Analyst/Programmer
>> >> Case Western Reserve University
>> >>
>> >> _______________________________________________
>> >>
>> >> Seqfan Mailing list - http://list.seqfan.eu/
>> >>
>> >
>> >
>> >
>> >
>> > _______________________________________________
>> >
>> > Seqfan Mailing list - http://list.seqfan.eu/
>>
>> _______________________________________________
>>
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>
>
>
> --
> Dear Friends, I have now retired from AT&T. New coordinates:
>
> Neil J. A. Sloane, President, OEIS Foundation
> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA
> Phone: 732 828 6098; home page: http://NeilSloane.com
> Email: njasloane at gmail.com
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/