David Moran wrote:

Tim Peters wrote:

[

...
Here is a recap of the technique written more rigorously:

probPrime(x) = ((p_k - 1)*...*2)*floor(x/(p_k*...*2))/x

such that x>(p_k*...*2), where k is the largest prime less than or
equal to j that will fit, where j is the count of primes up to and
including sqrt(x).

[Tim Peters]

You mean p_k is the largest prime (etc), not k.

So at x=100 k is 3, because the product of the first 3 primes is 30
(<= 100) but the product of the first 4 primes is 210 (> 100). Then

you estimate the number of primes <= 100 as 100 * probPrime(100) =

(p_3 - 1)*(p_2 - 1)*(p_1 - 1) * floor(100/(p_3 * p_2 * p_1)) =
4 * 2 * 1 * floor(100/( 5 * 3 * 2) =
8 * 3 =
24

? Fine so far as it goes.

What happens at, say, x=10^6? The product of the first 7 primes is
510510, so k=7. You expect to compute a sensible approximation by
using /only/ the first 7 primes, when there are 168 primes <= sqrt(10^6)?

If that doesn't strike you as exceedingly unlikely to work at first
glance, complete the computation for 10^6 and explain why 92160 should be
accepted as a good approximation to pi(10^6) = 78498 (and note that the
dirt-cheap x/(ln(x)-1) estimates 78030 in this case).

Looks like you don't know how very fast the product of the first k primes
grows. For example, at x=10^12, k=11, and then you're using only 11
primes despite that pi(sqrt(10^12)) = 78498.
...

[

Link removed. So you still didn't take the next obvious step? I
wonder why.

Same general deal as with your factoring attempts: I actually know
something non-trivial about the topic, so often know how one of your
attempts is going to turn out shortly after first seeing it. The use of the
primorial above (see the link you deleted -- the product of the first k
primes) made it obvious at first glance (note the use of that phrase above)
it wasn't going to work well at all.

Now a question for you: if the next step is obvious, why didn't you use it
the first time instead of posting the above?

I said that the probability that x is not divisible by p for a
particular prime p less than or equal to the sqrt(x) is given by

((p-1)*floor(x/p))/x

A mistake on my part.

You didn't say that in the post I was replying to, and it's clear as mud why
you think it. The probability that x is divisible by p is 1 or 0, but we
can't say which without knowing x and p first. The probability that an
integer chosen uniformly at random from 1 to x is divisible by p is exactly:

floor(x/p) / x

Therefore the probability that an integer chosen uniformly at random from 1
to x is not divisible by p is exactly 1 minus that, or:

1 - floor(x/p)/x [1]

For example, floor(30/7) = 4 integers in 1..30 are divisible by 7, so the
probability that an integer in 1..30 is not divisible by 7 is

1 - 4/30 = 26/30 = 13/15

What's the reasoning for your:

((p-1)*floor(x/p))/x [2]

above? Do you /really/ want to say that "the probability" of not being
divisible by 7 is the smaller 6*floor(30/7)/30 = 24/30 = 12/15 instead?
This smells like an error to me.

Yup. It was a mistake which I realized a little later. The correct
answer is

1 - floor(x/p)/x.

In the end it won't matter much (both ways are still asymptotically wrong).

There is the possibility of clipping from combinations that are not
possible, which still just follows from using Legendre's Formula.

Like up to 100, the primes are 2, 3, 5 and 7, so you loop through
possibilities using 2, 3, 5 and 7, and then 2(3), 2(5), 2(6), and 3(5),
3(7) and so on until you get to 2(3)(5)(7), which drops off with the
use of floor() because it is greater than 100.

So it's still all about the floor() function.

As you get bigger and bigger x, more combinations of primes fall off
the edge you might say, and are cleared with the exact approach using
Legendre's.

However, note that because the /underlying/ model is inherently biased
toward overestimating the prime count, an error that makes your
"probabilities" smaller than you intend may actually help you. (Exercise:
prove that your expression [2] is always <= my expression [1], for all
positive x and p.)

So, of course, the easy correction is to use:

probPrime(x) = ((p_j-1)*floor(x/p_j))...*floor(x/2))/x^j

where p_j is the jth prime, where j is the number of primes up to and
including x.

Fixing my error that should be

ProbPrime(x) = ((1 - floor(x/p_j)/x)*...*(1 - floor(x/2)/x).

So, why didn't you make the obvious leap? I wonder.

You haven't been paying attention: it's not the rounding artifacts that
were the /primary/ problem in your original model. That's only the problem
you saw. The primary problem remains that the individual probabilities here
are not independent in the vicinity of x, so multiplying them together to
compute the joint probability is /inherently/ incorrect.

Nope. I proved that it is mostly remainder error by stepping through
what follows from Legendre's Formula, as the argument is trivial.

Possibly mathematicians looking for an explanation in this area thought
that the individual progabilities were entangled, but that can't be
true for many reasons where a simple explanation is that given primes
p_1 and p_2, p_1 mod p_2 can't show a preference, as if it did, the
naturals would show a preference, but for each prime they go in
lock-step, for example:

1, 2, 3 followed by 4, 5, 6 and so on

where you have 1, 2, 0 modulo 3, followed by 1, 2, 0 modulo 3, out to
infinity.

So no, there no entanglement of probabilities. That idea is just
wrong.

The correct answer can easily be found using Legendre's and noticing
that some combinations are excluded for size reasons.

Because I know that (you still don't in part because you didn't follow the
references previously given), I /know/ this approach is also doomed. I
don't have to try it to know that, same way I didn't have to try your
previous attempts to know how they'd turn out. Write a program yourself
this time, and you'll see that even the simple x/(ln(x)-1) is a much better
approximation to pi(x) as x increases, and that the ratio of pi(x) to yours
still drifts away from 1. It's probably a better approximation than you
started with (especially if you make errors that underestimate the
"probabilities" you intended to compute), and enormously better than the one
you posted at the top, but it still misses the mark.

But unlike you I want to know the correct answer--while you want what
you've been told to be true.

You are following some books.

I am figuring out what is actually happening.

If you had, you might have become world-famous, put your name in the
history books as more than just my foil, and stepped forward as a
positive contributor in this entire thing, despite what you did before,
so there was a tremendous amount of positive pressure to get the right
answer, and a world of pain to miss it.

But you missed it.

The puzzle remains and I wonder what else I can do that is that easy.
I have not found a bottom, and that is the puzzle. There should have
been a bottom.

Sorry, but in truth you don't yet have anything in this area worth having.
How about going to a library tomorrow and looking up one of the books I
referenced?

Waste of time.

Why? We had to read books to learn. Why can't you? An attempt to learn
might show that you're actually trying to understand what people with
more experience are telling you.

Dave

I've read lots of books. I prize books and learning. I've also read
books in this area.

The problem here though is that for reasons that escape me, as it
boggles my mind, mathematicians have smudged the line with primes when
it comes to question about how many primes there are in an
interval--the prime distribution--versus questions like how many twin
primes there are in an interval.

So the books are lying. Since it is so easy to explain, any objective
reader can know that the books are lying, and wonder, like me, why.

Now then, how is it obvious?

Well, the count of primes up to a given x is exactly determined by a
simple calculation using the primes up to and including the square root
of x.

For instance, to count the primes up to 24, you need only use

24 - floor(24/2) - floor(24/3) + floor(24/6) + 2 - 1

which is, you subtract the evens, from 24 and then the count of those
divisible by 3, and then you add in those divisible by 6--as they've
been subtracted twice--and then add in 2 for the primes as 2 got
subtracted with the evens and 3 got subtracted with those divisible by
3, and then you subtract one for 1, as one is not prime.

That gives you the EXACT count, and the method is perfect, for any
natural x.

In contrast, how many twin primes are there up to 24?

To be a twin prime, given an odd prime x, it must be true in that
interval that

x+2

is coprime to 3, as, of course, it will be coprime to 2, but notice,
you cannot calculate the count in the same way you could calculate the
count of primes!!!

There are TWO SYSTEMS, where one is exact and determined, not at all
random, with simple equations for counting primes, and the other is
random, so you can't calculate the number of twin primes, you have to
go check each prime, add 2 to it, and see if the result is divisible by
3.

As I've pointed out repeatedly, given primes p_1 mod p_2 it is
IMPOSSIBLE for that to show a preference for a particuar non-zero
residue!!!

If it could, then the composites--the products of the primes--would
show the SAME PREFERENCE, but in fact, the natural follow the simple
pattern:

1, 2, 3, 4, 5, and so on out to infinity.

I just explained in a couple of paragraphs how and why questions about
the prime distribution differ from areas that have to do with prime
residues modulo other primes, like with the twin primes conjecture, or
Goldbach's Conjecture.

But I doubt you'd find that explanation in ANY of the references you
mention.

My conclusion is that since this is simple, mathematicians lied. By
smearing the line, they can do research indefinitely, supporting any
number of people who are doing nothing at all positive.

They are doing nothing. They are just doing nothing at all.


James Harris

For instance, to count the primes up to 24, you need only use

24 - floor(24/2) - floor(24/3) + floor(24/6) + 2 - 1

which is, you subtract the evens, from 24 and then the count of those
divisible by 3, and then you add in those divisible by 6--as they've
been subtracted twice--and then add in 2 for the primes as 2 got
subtracted with the evens and 3 got subtracted with those divisible by
3, and then you subtract one for 1, as one is not prime.

That gives you the EXACT count, and the method is perfect, for any
natural x.

I've read lots of books. I prize books and learning. I've also read
books in this area.

The problem here though is that for reasons that escape me, as it
boggles my mind, mathematicians have smudged the line with primes when
it comes to question about how many primes there are in an
interval--the prime distribution--versus questions like how many twin
primes there are in an interval.

So the books are lying.

... [repetition] ...
I just explained in a couple of paragraphs how and why questions about
the prime distribution differ from areas that have to do with prime
residues modulo other primes, like with the twin primes conjecture, or
Goldbach's Conjecture.

But I doubt you'd find that explanation in ANY of the references you
mention.

... [repetition] ...