Take the 2-minute tour ×
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.

In my mind the following conjecture is true:

Prime Maker Conjecture

I call a number $n$ factor-resistant to $q$ if $q\not\mid n$. Considering $n$ as a composite number, the idea is to make $n$ factor-resistant to all of its (prime) factors. When we multiply a number minus or plus $1$ with one of its (prime) factor and then add or subtract 1, the number would become factor-resistant to that (prime) factor.

The Algorithm:

  1. Let $n=m\mp 1$ ($m$ is even).

  2. Perform a primility test on $n$, if $n$ is prime output Prime and exit.

  3. Find the smallest prime factor $d_0$ of $n$

  4. Set $m = d_0 \times m$.

  5. Set $n= m \pm 1$

  6. Go to Step 2

Example

We choose $m=541\#$ ($\#$ is primorial sign) and positive side.

  1. $n=541\#+1$

  2. $IsPrime(n)$ ? $n$ is composite

  3. $d_0=2879$

  4. $m = 2879 \times 541\#$

  5. $n= m +1$

  6. $IsPrime(n) ? n$ is composite

  7. $d_0=342085039$

  8. $m=342085039\times 2879 \times 541\#$

  9. $n = m + 1$

  10. $IsPrime(n) ? n$ is prime.

Of course the most time consuming step in the algorithm is finding the (smallest) factor, sometimes it makes the algorithm impractical but for a math proof we can think of it as a fast operation.

My conjecture is that, the number of required iterations of this algorithm to convert a composite number to prime one, is finite, but I have no idea how to prove it or even approach it ...

Update

I've just made the algorithm more clear.

More Samples

  • $n = 1549 \times 57179\times 102932777 \times 67118797 \times 718049 \times 8466769 \times 4261711 \times 1444603 \times 100! + 1$
  • $n = 18593 \times 3119\# + 1$ is a 1327 digits prime
  • $n = 1732043 \times 142981 \times 97787 \times 376001 \times 7933\# + 1$ is a 3423 digits prime
share|improve this question
    
In step 4 of the algorithm, do you mean to multiply $m$ by $d_0$? Or did you mean $n$? –  Johan Mar 2 '13 at 11:29
    
And what do you mean by $p_{100}$ in your example? –  Johan Mar 2 '13 at 11:49
    
To multiply $m$ by $d_0$ and put the result $+1$ into $n$. It is primorial of 100th prime. –  Mohsen Afshin Mar 2 '13 at 14:50
    
But $d_0$ is not a prime factor of $m$. So you can't apply the statement about "When we multiply a number with its smallest prime factor and then add or subtract 1..." –  Tara B Mar 2 '13 at 15:13
    
$d_0$ is a prime factor of $n$ or $m+1$, so $d_0 \mid m+1$, and so then we have $d_0 \not\mid d_0\times m + 1$. Got it? –  Mohsen Afshin Mar 2 '13 at 15:47
show 1 more comment

2 Answers 2

Your algorithm does not converge as it is described.

Example: $m = 24$. Choose "+1" throughout. Then initially $n = 25$.

  1. $n$ is composite
  2. $d_0 = 5$
  3. $n$ becomes $121$
  4. $n$ is composite
  5. $d_0 = 11$
  6. $n$ becomes $265$
  7. $n$ is composite
  8. $d_0 = 5$
  9. $n$ becomes $121$

and so on.

Your example on the other hand updates the number $m$ in each step. Is that what you have in mind?

share|improve this answer
    
No, he just explained it poorly. See his example - third $n$ should be $11 \times 5 \times 24 + 1$. I did a little testing and found that this way at least first 96 integers work. –  Karolis Juodelė Mar 3 '13 at 6:03
    
@Hans Engler, I've updated the algorithm with correct explaination –  Mohsen Afshin Mar 3 '13 at 6:59
add comment

For a better counter-example, see Broadhurst's answer on http://tech.groups.yahoo.com/group/primenumbers/message/25024

share|improve this answer
add comment

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.