Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

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<=i<=l?

share|improve this question
1  
Search " Jacobsthal function" on Google or the OEIS. – Charles Oct 11 '12 at 18:32

1 Answer

up vote 2 down vote

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.

share|improve this answer
2  
To expand: if $n=(2)(3)(5)(7)=210$, then you get length 9 by choosing $b$ so $b$ is a multiple of 2, $b+1$ is a multiple of 3, $b+3$ is a multiple of 7, and $b+5$ is amultiple of 5; the algorithm in the link finds such a number $b$. – Gerry Myerson Oct 12 '12 at 5:54
Thanks for the clarity Gerry. I have a related question (to the OP) which I really wanted answered, and I think Charles' hint has given me an answer. The question is "Does (l(n)) / n tend to 0 as n tends to infinity?" The motive is that it would give me some interesting "nested dense" sets in R. Well, it is interesting to me because I am exploring the Baire Category theorem. Anyway, after searching the Jacobsthal function on google I found that l(n) < (log(n))^2 and since (log(n))^2 / n tends to 0 as n tends to infinity, my question is answered. Now to create interesting nested dense sets... – Adam Rubinson Oct 12 '12 at 10:46
Thanks for your answers btw – Adam Rubinson Oct 12 '12 at 10:48
@Adam: You might be interested in this question and the paper linked to in my answer. – joriki Oct 12 '12 at 10:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.