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:
Let $n=m\mp 1$ ($m$ is even).
Perform a primility test on $n$, if $n$ is prime output Prime and exit.
Find the smallest prime factor $d_0$ of $n$
Set $m = d_0 \times m$.
Set $n= m \pm 1$
Go to Step 2
Example
We choose $m=541\#$ ($\#$ is primorial sign) and positive side.
$n=541\#+1$
$IsPrime(n)$ ? $n$ is composite
$d_0=2879$
$m = 2879 \times 541\#$
$n= m +1$
$IsPrime(n) ? n$ is composite
$d_0=342085039$
$m=342085039\times 2879 \times 541\#$
$n = m + 1$
$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
