Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Consecutive integers divisible by a set of Primes

  1. Oct 1, 2012 #1
    I am having more than a little fun with this sequence of numbers and am looking for a better algorithm to find the next numbers in the sequence.

    Let Z be the set of the first n odd primes. Find two integers j and k that are relatively prime to all members of Z where every integer between j and k is not relatively prime to all members of Z. The absolute value of j-k must be the maximum value possible. This maximum value I call frg(n).

    So, for the set with only {3} |4-2| = 2 4 and 2 are relatively prime to 3, but 3 is not.
    For the set {3,5} |7-4| = 3 7 and 4 are relatively prime to 3 and 5, but 5 and 6 are not.

    frg(1) = 2, frg(2) = 3, frg(3) = 5, frg(4) = 11, ..... frg(8) = 20

    I initially thought this would just be the sequence of primes but it is not. Now I wonder how weird it gets as we go out the sequence.

    I can get to frg(15) with my desktop. I know someone can do better!
  2. jcsd
  3. Oct 1, 2012 #2
    I calculated the first 8 and put them in to OEIS, and got: oeis.org/A072752.

    What you're after is not the gaps, but the difference, so it's one more than the terms in the sequence I linked to.

    I'm not sure about an efficient algorithm, my jumbled together program could only do 8 before taking > 20 seconds.
  4. Oct 1, 2012 #3
    Thanks for the link. Same sequence +1 because I'm using the difference. I will see if I can add one more number to the sequence. One thing for sure, since I have been playing with prime numbers, nothing I have ever done hasn't already been done by someone and usually 100 to 300 years ago. Thanks again. However, I would like the seen the program that got those numbers.
  5. Oct 1, 2012 #4
    I'll try to come up with a better one, mine's terrible. How on Earth did you work out frg(15)?
  6. Oct 3, 2012 #5
    I ask a very similar question here:


    What was your motivation for excluding 2?

    I would be interested in what language and algorithm you used. I'm useing purebasic. I generated permutations of the prime list and constructed a gap by fitting them in the first empty slot and seiving in the order they occured in the permutation.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook