Consecutive integers divisible by a set of Primes

In summary, this person is playing with prime numbers and is looking for an algorithm that is faster than their current program. They also mention wanting to see the program that got the numbers.
  • #1
axelmorack
10
0
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!
 
Physics news on Phys.org
  • #2
I calculated the first 8 and put them into 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.
 
  • #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.
 
  • #4
axelmorack said:
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.

I'll try to come up with a better one, mine's terrible. How on Earth did you work out frg(15)?
 
  • #5
I ask a very similar question here:

https://www.physicsforums.com/showthread.php?t=632458

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 occurred in the permutation.
 

1. What are consecutive integers?

Consecutive integers are a sequence of numbers that follow each other in order without any gaps. For example, 1, 2, 3, 4, 5 are consecutive integers.

2. What does it mean for an integer to be divisible by a prime number?

An integer is divisible by a prime number if it can be evenly divided by that prime number without leaving a remainder. For example, 12 is divisible by 2 because 12 divided by 2 is equal to 6 with no remainder.

3. What is the significance of consecutive integers being divisible by a set of primes?

When consecutive integers are divisible by a set of primes, it means that each consecutive integer is divisible by at least one of the prime numbers in the set. This can be useful in solving certain mathematical problems or in finding patterns in number sequences.

4. How can consecutive integers be checked for divisibility by a set of primes?

To check if a consecutive integer is divisible by a set of primes, we can divide the integer by each prime number in the set and see if there is no remainder. If there is no remainder for any of the divisions, then the integer is divisible by the set of primes.

5. Can consecutive integers be divisible by multiple sets of primes?

Yes, consecutive integers can be divisible by multiple sets of primes. This means that each integer in the sequence is divisible by at least one prime number from each set of primes.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
799
  • Linear and Abstract Algebra
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
27
Views
2K
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
33
Views
3K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
705
  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Precalculus Mathematics Homework Help
Replies
17
Views
2K
Back
Top