[seqfan] Re: Jacobsthal function

[Neil Sloane]

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