5
$\begingroup$

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
$\endgroup$
6
  • $\begingroup$ In step 4 of the algorithm, do you mean to multiply $m$ by $d_0$? Or did you mean $n$? $\endgroup$
    – Johan
    Mar 2, 2013 at 11:29
  • $\begingroup$ And what do you mean by $p_{100}$ in your example? $\endgroup$
    – Johan
    Mar 2, 2013 at 11:49
  • $\begingroup$ To multiply $m$ by $d_0$ and put the result $+1$ into $n$. It is primorial of 100th prime. $\endgroup$ Mar 2, 2013 at 14:50
  • $\begingroup$ 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..." $\endgroup$
    – Tara B
    Mar 2, 2013 at 15:13
  • $\begingroup$ $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? $\endgroup$ Mar 2, 2013 at 15:47

2 Answers 2

2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Mar 3, 2013 at 6:03
  • $\begingroup$ @Hans Engler, I've updated the algorithm with correct explaination $\endgroup$ Mar 3, 2013 at 6:59
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .