Jacobsthal function related to squares The ordinary Jacobsthal function $j$ is defined by setting $j(n)$ as the smallest number $m$ such that, for each consecutive $m$ integers, at least one of the numbers is coprime to $n$. There are estimates for $j$; for example, $$j(n) \ll \log ^2 (n)$$ and it is conjectured by Jacobsthal that we could improve this to $$j(n) \ll ( \log (n) / \log ( \log (n)) )^2.$$
See for example http://www.tcnj.edu/~hagedorn/papers/JacobPaper.pdf .
We define now $h(n)$ as the smallest number $m$ such that, for each square $a \in \mathbb{N}$, the sequence $$a+1, a+1, \ldots, a+m$$ contains at least one number comprime to $n$. My question is now, are there any good upper estimates for $h(n)$ ? Clearly, $h(n) \leq j(n)$ holds, so we could take the above estimate for $j(n)$, but I am searching for something stronger, perhaps like $$h(n) \leq C \log(n),$$
where $C=2$ or so.
 A: I take back what I said in the comments about the bound not shrinking.  I am convinced that one can get much tighter bounds, and that the tighter bounds will depend massively on the quadratic residues for each of the primes involved.
To set the stage, I change notation slightly.  I use $m$ for the argument to $j()$, and I use $n$ for the number of distinct prime factors of $m$.  I also insist $m > 1$.
One of the more accessible results is that $j(m) = j(k)$ if $m$ and $k$ have the same prime factors.  Further if the prime factors are all larger than $n$, then $j(m)= n+1$, so there is a certain uniformity in the analysis and results for a large and simply stated class of numbers.
(Advertisement; I am working on similar statements where $n$ is replaced by something like $\sqrt(n)$.  Email me for more detail.)
Many of the standard bounds for $j(m)$ can be expressed in terms of $n$.  When I posted my comments above, I thought something similar would be true for this version.  However, checking a few examples leads me somewhere completely different.
For $m$ a prime power, $j(m)=2$.  The same holds for the new variation if and only if $-1$ is a qr of the prime dividing $m$.  However, things change when $n>1$.  $h(6)=j(6)=4$, but this does not hold for all numbers of the form $2p$.  $h(m)$ can vary from 2 to 4 depending on $m$ even if $n$ is restricted to 2.
To make things interesting, I computed $h(385)$, which is bounded above by 4.  There are 6 values of a mod 385 to show $j(385)=4$. To get $h(385)=4$, I had to find a square which was 4 mod 7, 9 mod 11, and 4 mod 5.  The square of 47 fit the bill, but I could imagine different primes with qrs that would not nicely fit in the set {-3,-2,-1}, so $h(m)$ will not always reach 4 or higher when $n=3$; it will depend on getting qrs which are small negative numbers.  For higher $n$, you may not achieve $h(m)>n$ without choosing the $n$ prime factors carefully.   And this analysis is using only squarefree $m$; I do not know what happens in the general case.
EDIT 2011.07.29 I let the presence of quadratic residues rattle me into thinking that $h(m)$ would depend on the multiplicity of prime factors of $m$.  It does not.  As is the case for $j(m)$, the value of $h(m)$ depends only on the set of prime factors of $m$, and so there is no "general case":  it suffices to assume $m$ is squarefree. END EDIT 2011.07.29
I am having a few challenges showing upper bounds without having to worry about quadratic residues.  This problem is a can of worms I am not ready to tackle.  Certainly nothing like the uniform results involving sufficiently large prime factors will hold.  One approach involves "tiling" a candidate interval with appropriate primes, and then solving $n$ many quadratic congurences simultaneously.  I don't know enough about quadratic residues to see any clean looking results here.  It is an interesting variation on which I welcome other viewpoints.
Gerhard "Jacobsthal's Function Is Tough Already" Paseman, 2011.07.15 
