[seqfan] Jacobsthal function

[Charles Greathouse]

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