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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook