Prime Algorithim Conjecture

267 Views Asked by At

Let $g$ be the greatest factor of a positive integer($a$) where $g \neq a$ and $l$ be the smallest factor such that $gl = a$. Let $t_i$ be the $i$th term of the sequence where the starting term is $\frac{g_1!}{(a_1)^n}$ and $n$ is the greatest positive integer such that $(a_i)^n|g_i!$.

More specifically the sequence/recursive algorithim

$t_i = \frac{g_{i}! }{(t_{i - 1})^n}$

For example, when $a_1$ is $10$:

$t_1 = \frac{5!}{10^n}$

Here $n = 1$, so

$t_1 = \frac{5!}{10} \implies t_1 = 12$

Then

$t_2 = \frac{6!}{12^n}$

In which we find $n = 2$, giving

$t_2 = \frac{6!}{144} \implies t_2 = 5$

So here the sequence stops, as $t_2$ is prime and $g \neq a$ . Its interesting to note that $n$ is the number of pairs of the form $a = mn$ where m and n are factors of $a$.

Now take a look at the number where $a_1$ is $14$,

$t_1=7!/141 \implies t_1 = 360 \implies t_2=180!/360^n$

You'll notice the explosive growth that it exhibits when put into the algorithm. This makes it seem skeptical this algorithm will always end at a prime number but consider the following:

Lets say we have a number $t_{i -1}$ with over $10$ factors after the fraction cancels out and each one has a very large prime factorization with many distinct primes in each. Now note that the prime factorization of each factor allows us to spread the primes across the other factors and combine them in many different ways. Lets say we had a function called $F(x)$ that determines the number of factors that can be possibly made from $t_{i-1}$. Then if we could prove that $F(x)$ at no point contains more than $y$ of $g_i!$ factors($G(x)$) such that $t_{i} > t_{i - 1}$ than there will be numbers of $a_{1}$ in which the algorithm will fail. But on the other hand if it does, and it can be proven that for some $a_{i}$ for any $a_1$ $F(x) > \frac{G(x)}{y}$ (In this case $t_{i} < t_{i - 1}$ is true) than the algorithm can still end with a prime.

Note that every consecutive term is co-prime and that we consider that a sequence terminates when $t_i$ is prime.

Given any value of $g$ and $l$, where $a_i$ is not a perfect square, this algorithm always terminates.

Prove or disprove this.

1

There are 1 best solutions below

6
On BEST ANSWER

We could use symbol like g(x) to represent the largest factor of x other than itself. l(x) to represent the smallest factor of x other than 1. n(x,a) to represent largest integer y so that $x^y|a$. So SpoonedBread defined $a_{h+1}=\frac{g(a_h)!}{a_h^{n(a_h,g(a_h)!)}}$

The Bertrand's postulate said that there's at least one prime between integers x and 2x. It has been enhanced according to the link that when x is large enough, there's at least one prime between x and $(1+\frac1{16597}) x$ so that there're at least four primes between x and 2x.

So when $a_1=px_1$ and $x_1$ is large enough and p is the smallest prime factor of $a_1$, we have $g(a_1)=x_1$, and there're at least four prime factor $p_1\lt p_2\lt p_3\lt p_4$ between $\frac {x_1}2$ and $x_1$. so that $p_1p_2p_3p_4|g(a_1)!$, but all of them coprime with $x_1$ since there're larger than $\frac {x_1}2$ and at most one of them is equal to p.

Assume $p_2,p_3,p_4$ is not equal to p, So we have $a_2$ is multiple of $p_2p_3p_4$ and we could write $a_2=qx_2$ where $x_2\ge p_3p_4 \gt x_1$. Continue the step above we could find that $a_h$ is monotone increasing.