[seqfan] Re: Jacobsthal function

[hv at crypt.org]

Turning it into a computation might be trickier, but you can determine
the value by reasoning based on the distinct prime factors.

If n = p_1^a_1, we have a(n) = 2.

If n = p_1^a_1 . p_2^a_2, we have a(n) = 3 if p_1, p_2 are large enough;
in fact, "large enough" means > 2: if p_1 = 2, we have a(n) = 4.

More generally, if n has k distinct prime factors, we'll have a(n) = k+1
if the least of them is greater than k, else we'll have room to fit in
more multiples of some p_i within a span of k consecutive integers each
non-coprime to n. Determining just how many can be interleaved in the
latter case is where all the interesting stuff happens; I expect that
encoding that determination would be logically tricky, but computationally
fairly easy.

Hugo

Charles Greathouse <charles.greathouse at case.edu> wrote:
: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/
:
:_______________________________________________
:
:Seqfan Mailing list - http://list.seqfan.eu/