Re: Prime Numbers and Carmichael Statements

In article <1194462694.719480.319770@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
amzoti <amzoti@xxxxxxxxx> wrote:

On Nov 7, 11:02 am, Pubkeybreaker <pubkeybrea...@xxxxxxx> wrote:
amzoti wrote:
Hi All,

I was looking at the book "The Theory of Numbers" by R. D. Carmichael
from 1914 on the wonderful resource - Project Guttenberg.

See:http://www.gutenberg.org/etext/13693

In the book, Carmichael makes the following claims.

***
The subject of prime numbers is in general one of exceeding
difficulty.
In fact it is an easy matter to propose problems about prime numbers
which no one has been able to solve.
Some of the simplest of these are the following:

1. Is there an infinite number of pairs of primes differing by 2?
2. Is every even number (other than 2) the sum of two primes or the
sum of a prime and the unit?
3. Is every even number the difference of two primes or the difference
of 1 and a prime number?

These are still open.

4. To find a prime number greater than a given prime.
5. To find the prime number which follows a given prime.
6. To find the number of primes not greater than a given number.
7. To compute directly the nth prime number, when n is given.

Modern algorithms solve 4,5, & 7 very quickly (polynomial time).
(although the meaning of the word "directly" is vague)

For 6., if N is the given number, the computation can be done in time
O(sqrt(N))
via a method of Odlyzko et.al. that has not been implemented to my
knowledge.- Hide quoted text -

- Show quoted text -

I interpreted 'directly' to mean a closed form solution with proof.

In other words, for any of the statements you reference, provide a
method in the form of a closed solutin where you can pick 'n' and out
pops the next item.

I am aware of many of the algorithmic approaches.

There is certainly a formula f(n) which gives the n-th prime,
the problem is that using that formula to compute the n-th prime
is computationally equivalent to running an algorithm to test
1, 2, 3, ..., until you've accumulated n primes. To put it another
way, it's hard to draw a line and say everything on one side is
a closed form solution and everything on the other side is
an algorithm.

It's safe to say that we can do a lot better at problems 4 to 7
than Carmichael could, and not just because we have computers
and he didn't - we have better algorithms. But it's also safe to
say that all of those problems are much harder than, say, the
same problems with "prime" replaced by "square."

--
Gerry Myerson (gerry@xxxxxxxxxxxxxxx) (i -> u for email)
.

Relevant Pages

  • Re: Is there a polynomial algorithm for that problem?
    ... The sum over all n numbers is negative. ... Unfortunately that algorithm does not scale. ... An instance of 3-Partition consists of a list of 3m positive integers ... list can be partitioned into m lists of size 3, ...
    (sci.math)
  • Re: Choose k random lines from file
    ... > What, for the algorithm shown above, or for any algorithm? ... Yes, that is an unbiased generator, but I had thought ... >>give less of a bias using an extra float or double ... >>distribution for the sum. ...
    (comp.programming)
  • Re: standard deviation, but without the mean
    ... Suppose Xsum is the sum of the the first n numbes and that X2 is ... Just keep track if X2 and Xsum as you go. ... Actually this is not a correct algorithm, ... the error in the least 9 digits.. ...
    (sci.stat.math)
  • Re: C# generic containers from a "C++ perspective"
    ... If you implement the floating-point and integer algorithms ... Maintain the sum of all the items in an accumulator. ... That is the fundamentally-broken algorithm that I was expecting you to ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Disjoint circle merge NP complete for L^n error?
    ... The key point is that we need to be sure there is no optimal algorithm ... We only need to erase MAX and replace with SUM in the proof ... minimum error partition) algorithm in P. ... MAX. I'm pretty sure that if both these are in NP then all L^n metrics ...
    (comp.theory)