Consider the strings $(b,b+1,b+2,...,b+l)$ of consecutive natural numbers, all less than some fixed natural number $n > b+l$. Is there a way to find the longest string (length of a string $= l+1$) with $\gcd(b+i,n) > 1$ for all $0\le i \le l$?
"Strings" of consecutive natural numbers
2
$\begingroup$
number-theory
-
1Search " Jacobsthal function" on Google or the OEIS. – 2012-10-11
1 Answers
2
Arrange arithmetic sequences with distances given by the prime factors of $n$ so as to cover as many consecutive numbers as possible; for instance, if the prime factors are $2$, $3$, $5$ and $7$, this could be
2 3 2 7 2 5 2 3 2 3
I don't know whether there's a systematic way of doing this, but it seems that just using them from the smallest to largest whenever a new one is required to fill a gap might be optimal. Then by the Chinese remainder theorem, using the associated algorithm you can find the residue mod $n$ where this sequence is realized.
-
0@Adam: You might be interested in [this question](http://math.stackexchange.com/questions/58832/primegaps-w-r-t-the-m-first-primes-jacobsthals-function) and the paper linked to in my answer. – 2012-10-12