Conjecture:fundamental mathematical group

[Focus]

You're not talking about a sieve, are you? To me, a sieve is a dumb algorithm which tests all odd numbers not ending in 5. That's not what I meant. I meant a smart algorithm which can produce all the primes and only the primes. Such an algorithm would also tell us the number of primes over any specified interval of natural numbers.

What is a "smart" algorithm? Do you mean an algorithm that has a polynomial complexity? I can write you an algorithm that can generate all primes (and only primes) and one for telling you how many primes are in a given finite subset of the naturals. You can tell the algorithm to output infinity whenever you enter a infinite subset.

 

[Jimmy Snyder]

What is a "smart" algorithm? Do you mean an algorithm that has a polynomial complexity? I can write you an algorithm that can generate all primes (and only primes) and one for telling you how many primes are in a given finite subset of the naturals. You can tell the algorithm to output infinity whenever you enter a infinite subset.

So if I enter the infinite subset { 2, 4, 6, ... }, it will return infinity?

 

[SW VandeCarr]

What is a "smart" algorithm? Do you mean an algorithm that has a polynomial complexity? I can write you an algorithm that can generate all primes (and only primes) and one for telling you how many primes are in a given finite subset of the naturals. You can tell the algorithm to output infinity whenever you enter a infinite subset.

Then why do we need to estimate the number of primes less than x asymptotically with x/ln(x)?

 

[Jimmy Snyder]

Then why do we need to estimate the number of primes less than x asymptotically with x/ln(x)?

Because the algorithm is time consuming. An algorithm must complete in a finite number of steps. You would be suprised to learn how large some numbers can be and still be considered finite.

 

[SW VandeCarr]

Because the algorithm is time consuming. An algorithm must complete in a finite number of steps. You would be suprised to learn how large some numbers can be and still be considered finite.

Of course. That's why de facto, we have no provable formula that will generate all the primes and only the primes.

 

[Jimmy Snyder]

Of course. That's why de facto, we have no provable formula that will generate all the primes and only the primes.

Algorithm. You have not proved that there is no algorithm, you have only proved that you think there isn't one.

 

[humanino]

Of course. That's why de facto, we have no provable formula that will generate all the primes and only the primes.

No, that's obviously not a proof that such a formula does not exist. We do have an algorithm which generates all primes (sieve of Eratosthenes). It is an algorithm, admittedly not very efficient, but perfectly valid still.

Can you prove to me that there is no polynomial (possibly of very large degree) such that P(n) is the n-th prime ? That would be another algorithm. It would suffice to evaluate the polynomial at every integer to get all the primes. It would still take an infinite time, but it would be more efficient than the sieve of Eratosthenes.

 

[SW VandeCarr]

No, that's obviously not a proof that such a formula does not exist. We do have an algorithm which generates all primes (sieve of Eratosthenes). It is an algorithm, admittedly not very efficient, but perfectly valid still.

Can you prove to me that there is no polynomial (possibly of very large degree) such that P(n) is the n-th prime ? That would be another algorithm. It would suffice to evaluate the polynomial at every integer to get all the primes. It would still take an infinite time, but it would be more efficient than the sieve of Eratosthenes.

No. I'm saying we don't have an efficient formula to generate the nth prime. I'm not saying one can't possibly exist.

 

[SW VandeCarr]

Algorithm. You have not proved that there is no algorithm, you have only proved that you think there isn't one.

See my response to humanino. Also, mathematical formulas with numerical outputs and algorithms are implemented the same way, as computational steps.

 

[Jimmy Snyder]

Can you prove to me that there is no polynomial (possibly of very large degree) such that P(n) is the n-th prime?

Yes. Let P be a polynomial of degree m such that P(n) is prime for all n.
$$P(x) = a_mx^m + ... + a_0$$
Then P(1) = p where p is a prime, so P(1) = 0 (mod p). So for any k,
$$P(1 + kp) = a_m(1+pk)^m + ... + a_0$$
$$= a_m + a_mb_m + ... + a_1 + a_1b_1 + a_0$$
(where $$b_i$$ is divisible by p for all i)
= P(1) mod p
= 0 mod p
so P(1 + kp) = 0 (mod p) and either P(1 + kp) is divisable by p and is not prime, or is 0. But P only has m zeros or is itself the zero polynomial.

 

[humanino]

...

I never had any doubt that you would know. I suspect you may even be able to come up with another proof
Thanks for the answer.

 

[Evo]

Locked pending moderation.