Consecutive integers divisible by a set of Primes

  • Context: Graduate 
  • Thread starter Thread starter axelmorack
  • Start date Start date
  • Tags Tags
    Integers Primes Set
Click For Summary

Discussion Overview

The discussion revolves around finding a better algorithm to determine a sequence of integers that are relatively prime to a set of odd primes, specifically focusing on the maximum gap between two integers that meet certain criteria. The conversation includes exploration of the sequence's properties and computational challenges.

Discussion Character

  • Exploratory
  • Mathematical reasoning
  • Technical explanation

Main Points Raised

  • One participant defines a function frg(n) based on the maximum gap between two integers that are relatively prime to a set of odd primes, providing examples for specific values of n.
  • Another participant references the Online Encyclopedia of Integer Sequences (OEIS) and notes that the sequence discussed is related to a known sequence but differs by one due to the focus on differences.
  • A participant expresses interest in improving their algorithm, indicating that their current implementation is inefficient and slow for larger values.
  • There is a question about the exclusion of the prime number 2 from the set, prompting a discussion about the rationale behind this decision.
  • One participant shares their programming approach using PureBasic, mentioning the generation of permutations of the prime list to construct gaps.

Areas of Agreement / Disagreement

Participants express curiosity and share methods, but there is no consensus on the best algorithm or approach to efficiently calculate the sequence. The exclusion of the prime number 2 also raises questions without a clear agreement on its implications.

Contextual Notes

Some participants mention computational limitations and the historical context of similar mathematical explorations, indicating that the problem may have been addressed in various forms previously.

Who May Find This Useful

Individuals interested in number theory, algorithms related to prime numbers, and those exploring mathematical sequences may find this discussion relevant.

axelmorack
Messages
10
Reaction score
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
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.
 
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.
 
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)?
 
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.
 

Similar threads

Undergrad Localizing single variable quotient polynomial ring at a prime ideal
  • · Replies 6 ·
Replies
6
Views
2K
Undergrad Trouble understanding an online solution to an exercise in Dummit & Foote
  • · Replies 21 ·
Replies
21
Views
2K
Undergrad Localising a non integral domain at a prime
  • · Replies 17 ·
Replies
17
Views
3K
MHB 412.00.1.12 are relatively prime for all n.
  • · Replies 1 ·
Replies
1
Views
1K
Graduate All complex integers of the same norm = associates?
  • · Replies 1 ·
Replies
1
Views
2K
Determine whether the integer 701 is prime by testing?
  • · Replies 1 ·
Replies
1
Views
3K
High School Probability that 2 distinct integers are divisible by the same number
  • · Replies 9 ·
Replies
9
Views
2K
Undergrad Confused about Gauss's Lemma of Irreducibility
  • · Replies 4 ·
Replies
4
Views
3K
Graduate Differences between Gaussian integers with norm 25
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Base Pi Integers: Isomorphism with Rationals?
  • · Replies 33 ·
2
Replies
33
Views
4K