Re: Prime numbers

[amzoti, on www.primenumbersformula.com]
Hi Phil,

do you actually know how to interpret this function?

I was trying to read it and not sure what the floor like functions
mean.

I'm sure they mean the floor.

I must also be misinterpreting something because it looks like
most stuff cancels out.

I expect that's intentional ;-)

Any ideas as this would be easy to test?

Well, let's look at it top down. It has the structure:

H(m) = 2*((2m+1)/2)^e(m)

for a messy function e(m), which we'll get to later. _Assume_ for the
moment that:

e(m) = 1 if 2m+1 is prime
= 0 if 2m+1 is not prime

If that's true, then:

H(m) = 2*((2m+1)/2)^1 = 2m+1 if 2m+1 is prime
= 2*((2m+1)/2)^0 = 2 if 2m+1 is not prime

So, if that's true, H(m) _obviously_ generates all and only the primes as m
goes from 1 to infinity, and generates each prime exactly once except for 2.
2 is generated for each m s.t. 2m+1 is not prime. If you look at the
sequence he gives below it:

it generates all the prime numbers (3,5,7,2,11,13,2,17,19, ...)

that matches the above. At m=1, 2m+1=3 and is prime. Likewise for 5 and 7
at m=2 and m=3. At m=4, 2m+1=9 is not prime, and that's the first 2 in his
sequence. m=5 gives 11 and m=6 gives 13, then at m=7 2m+1=15 is not prime
and another 2 shows up in his sequence. Etc.

So it just boils down to finding a function e(m) s.t.

e(m) = 1 if 2m+1 is prime
= 0 if 2m+1 is not prime

His e(m) works, and is really a pretty standard kind of trick if you're
attracted to silly ;-) functions like this:

e(m) = floor(a * floor(b/a) / b)

where:

a = 2m+1
b = (2m)!+1

Remember that Wilson's theorem says p is prime if and only if p divides
(p-1)!+1. Substitute 2m+1 for p to get:

2m+1 is prime if and only if 2m+1 divides (2m!)+1

or, using the variable names just above,

2m+1 is prime if and only if a divides b

Suppose a does divide b (2m+1 is prime). Then b = q*a for some integer q,
and

floor(a * floor(b/a) / b) =
floor(a * floor(q*a/a) / (q*a)) =
floor(a * q / (q*a)) =
floor(1) =
1

So e(m) is 1 if 2m+1 is prime. OTOH, if a does not divide b (2m+1 is not
prime), then b = q*a + r for some integers q and r with 0 < r < a, and

floor(b/a) = floor((q*a + r)/a) = floor(q + r/a) =
since 0 < r/a < 1
q

so

floor(a * floor(b/a) / b) =
floor(a * q / (q*a + r)) =
since r > 0, q*a+r > q*a
0

So e(m) is 0 if 2m+1 is not prime, and we're done.

However, right now it looks like crank/troll work!

It does seem overly impressed with itself. As an exercise, now figure out
why this function (found on Wikipedia) works:

f(n) = 2 + mod(2*n!, n+1)

That also generates all and only the primes as n goes from 1 to infinity,
and also generates each prime exactly once except for 2 (which is generated
infinitely often). IMO, that's more elegant.


.

Relevant Pages

  • Re: PROOF THAT THERE ARE AN INFINITY OF PRIMES!!!!!!!!!!!!!!
    ... Rouben Rostamian wrote: ... PROOF THAT THERE ARE AN INFINITY OF PRIMES!!!!!!!!!!!!!! ... Your CAPS-LOCK key works real well but your math doesn't: ... the prime A that divides 11 and the prime B that ...
    (sci.math)
  • Re: P(prod_i p_i^{k_i}|n)=?
    ... Not stupid, but more complicated than it needs to be. ... P(x divides n) = 1/x. ... as N tends to infinity of P, when x is equal to one of ... 1,2,...,N with equal probability. ...
    (sci.math)