Pi(x) function in number theory solved

[eljose]

Here you are the best formula to calculate Pi(x) by means of a 4-dimensional integral:

$$\pi(t)=\frac{1}{4\pi^2}\int_0^t\int_{c-i\infty}^{c+i\infty}\int_{d-i\infty}^{d+i\infty}\int_0^{\infty}dxdsdqdn\frac{n^{-s+2}x^{q-1}LnR(qn}}{R(4-s)}$$

Where R(s is the Riemann Zeta function...

 

[matt grime]

please elaborate: in what sense that is the "best"? do you for instance mean that of all the 4 dimensional integrals it is the "best" or of all methods of evalutaing pi it is the "best", and in either case "best" means what?

since you state "calculate pi" i presume you mean the fastest method. please prove that it is the fastest known method.

it is undoubtedly an interesting relation, but how useful or original is it?

 

[eljose]

I think is better becasuse always require the same number of operations,let,s use a random number generator to generate random number on the interval

$$(0,t)x(-\infty,\infty)x(0,\infty)x(-\infty,\infty)$$

where we have made the change of variables s=c+iu and q=d+iv

then we generate N numbers (as t is differente each time the numbers will be different but always the same N) and compute the integral by Montecarlos,s Method the error wil be 1/N^(0,5) if we take N=100 poiints the error will be 0,1,but as we know Pi(x) is an integer we don,t need to have a lot of accuracy,the number of terms will be:

N+Sum(1,N)

 

[keebs]

I think is better becasuse always require the same number of operations,let,s use a random number generator to generate random number on the interval

It doesn't always require the same number of operations because you are integrating up to variable t, which can vary (hence the term "variable"). In fact, because you will need to integrate numerically it may take even more operations to get a good approximation than a summation would.

 

[Zurtex]

What sort of accuracy and run time would this require to calculate something like Pi(10^100)?

 

[eljose]

To Zurtex: i have no computer program to calculate montecarlo method so if they published my work (in fact if i were famous perhpas would win the field medal with this work) we would know the time required..

To Keebs: i have taken the 4-dimensional volume to be $$(0,t)x(-\infty,\infty)x(0,\infty)x(-\infty,\infty)$$ and in this 4 dfimensional volume we choose N points,yes the volume varies as t varies,so the random points will be different each time we want to calculate PI(t) but the number of points N is always the same.

 

[Hurkyl]

I think is better becasuse always require the same number of operations

That is necessarily false. For example, the time it takes to simply write the answer is unbounded.

Let me restate:

Suppose you say that you can compute pi(n) in N operations. I can demonstrate the existence of some number, m, such that it takes more than N operations to simply write pi(m), let alone compute it.

 

[keebs]

To Keebs: i have taken the 4-dimensional volume to be javascript:; and in this 4 dfimensional volume we choose N points,yes the volume varies as t varies,so the random points will be different each time we want to calculate PI(t) but the number of points N is always the same.

But as t increases the volume increases, thus a computer will require more time to compute the integral.

 

[eljose]

I don,t think there is a big problem with my integral,just use Montecarlo method to calculate it or simply use another method...

Hurtkyl can you prove your statement?..(mathematically) and according to your post any method used to compute Pi(x) will require "unbounded" time.

my method is also better as gives you the Pi(x) in an integral form,so you can apply the numerical method of calculating integrals to it..whereas the others require to calculate a series that if n is big to compute Pi(n) you will need to make at least a sum sum(1,n)

 

[matt grime]

oh dear, and i was hopi9ng to give you the ebnefit of the doubt this time since i don't like to discourage people from investigating mathematics but for pity's sake egt a grip.

hurkyl can prove his claim since there are an infinite number of primes, surely a fields' medal winner can see that? he is simply stating that there is no constant T such that pi(x) can be evaluated in time less then T for all x. which is what you are claiming can be done. proof. suppose that printinig a single digit takes t seconds then there are at most T/t printiable digits that may appear in pi(x) implying pi(x) is bounded, however pi(x) grows without bound.

right, you have applied an inverse transform to a function. no biggee. numerical integration is exactly the same as summing a series so claiming your representation is better is a tad off the mark to say the least. until you can get this in perspective you will remain shunned by those mathematicians who have declined to give your thoughts time in the past. how can yuo honestly claim to have a better way of calculating pi(x) without actually knowng the first thing about complexity of algorithms? this is maths, you have to prove your claims especially ones that are apparenty nonsensical.

you do not need a computer to estimate the order of the algorithm

 

[eljose]

Thanks for your replies,according to you and Hurkyl then all methods involving calculating pI(x) require bigger time as x increase...

My method is new (is the first method to calculate pi(x) involving an integral and not a sum) so i think is worth publishing,the problem perhaps is that i am not famous and can not compete with these snobish teachers of important universities publishing nonsenses and useless things , sorry i won,t comply anymore...

another question let,s suppose that the integral equation for Pi(x) could be approximate by numerical methods by:

$$\pi(a)K(a,s)+\sum_jK(s,x_j)\pi(x_j)=g(s)$$

then we could set a system of equation to calculate Pi(a) am i wrong?...

 

[shmoe]

..(is the first method to calculate pi(x) involving an integral and not a sum)

No it isn't-expressions of pi(x) in the form of an integral are not new at all. For computationally useful algorithms of this type, there's a paper by Lagarias and Odlyzko called Computing pi(x): an Analytic Method from the 80's (there are probably a few others out there as well, but afaik this is the first to provide a potentially useful method). An electronic roughish copy is on Odlyzko's website if you don't have access to the journal http://www.dtc.umn.edu/~odlyzko/ . Read it. Their integral is not only simpler, but you can see what a full on run-time analysis of something like this looks like as well as proofs of correctness. You can also find on his website some papers on approximating values of $$\zeta(s)$$ (for cripes sake, why do you still refuse to use the standard notation and wonder why people can't be bothered to take you seriously?), something that can not be done to an arbitrary accuracy in a constant amount of time (another roadblock in your claimed constant runtime).

Get your head out of the clouds- Odlyzko has not only trumped what you claim to have done, but has a large body of work involving numeric techniques and other nifty results. Guess what? He doesn't have a fields medal either and he extremely well respected.

 

[Zurtex]

Thanks for your replies,according to you and Hurkyl then all methods involving calculating pI(x) require bigger time as x increase...

My method is new (is the first method to calculate pi(x) involving an integral and not a sum) so i think is worth publishing,the problem perhaps is that i am not famous and can not compete with these snobish teachers of important universities publishing nonsenses and useless things , sorry i won,t comply anymore...

another question let,s suppose that the integral equation for Pi(x) could be approximate by numerical methods by:

$$\pi(a)K(a,s)+\sum_jK(s,x_j)\pi(x_j)=g(s)$$

then we could set a system of equation to calculate Pi(a) am i wrong?...

I know nothing about number theory this advanced, but I've seen many people on this forum alone post Pi(x) represented by an integral.

But at the end of the day an integral is just numerically calculated by a sum and the amount of run time and error on a computer needs to be calculated otherwise it's pointless just saying you have this fantastic integral that you've not even shown an example of how it works.

 

[eljose]

Yes Shmoe i know i should change it to $$\zeta(s)$$ i will edit my equation...

i checked teh webpage you gave me but i can not find the integral for PI(x) would you mind putting it on your reply?..thanks, i would be interesete d in watching the form of this integral representation of Pi(x)

 

[shmoe]

Look under his "computational number theory" category of papers.

 

[eljose]

Now my methdo would also be valid to calculate a(n) being this function n iff n is prime and 0 otherwise,now we have only 2 values and the expresion would be:

$$a(t)=\frac{1}{4\pi^2}\int_{t-1}^t\int_{c-i\infty}^{c+i\infty}\int_{d-i\infty}^{d+i\infty}\int_0^{\infty}dxdsdqdn\frac{n ^{-s+2}x^{q-1}LnR(qn}}{\zeta(4-s)}$$

now the volume is alwsays the same and not depending on x so the number of operations required to calculate a(n) would be always the same..

 

[keebs]

my method is also better as gives you the Pi(x) in an integral form,so you can apply the numerical method of calculating integrals to it..whereas the others require to calculate a series that if n is big to compute Pi(n) you will need to make at least a sum sum(1,n)

And to calculate an integral of Pi(n) you will need many more terms than sum(1,n) if you're going to use integrals, because calculating integrals numerically requires splitting up the curve into little tiny rectangles, finding the area of all of the rectangles, and then summing up all of the little areas.

My method is new (is the first method to calculate pi(x) involving an integral and not a sum) so i think is worth publishing,the problem perhaps is that i am not famous and can not compete with these snobish teachers of important universities publishing nonsenses and useless things , sorry i won,t comply anymore...

Haha, you know all of those summation formulas for pi(x), right? All of them can easily be transformed into an integral form.

now the volume is alwsays the same and not depending on x so the number of operations required to calculate a(n) would be always the same..

Nope, as t gets bigger you're going to require more operations to perform the multiplication and addition of the bigger values.

 

[shmoe]

now the volume is alwsays the same and not depending on x so the number of operations required to calculate a(n) would be always the same..

The higher the t, the larger the magnitude of the x term in the integrand, so you have to calculate zeta more accurately to get the integrand to a necessary precision, and this is not free. This is not going to let you calculate a(t) in constant time (wrt to t). (this is assuming that your expression is even correct)

 

[eljose]

To shmoe,i have checked all the articles but found no integral representation fro Pi(x) they only speak about calculating Riemann,s Zeta function could you write the integral representation or tell me what,s the name of the paper where the integral appears?..thanks in advance shmoe...

another question is the precision...we now that a(n) will be 0 or 1 so why we need such a high precision?... the same problem would happen with x/ln(x) so why this formula is accepted

So the total time will be= time required to calculate Riemmann,s function with accuracy + tiem to calculate an integral with fixed volume (and as th evolume is fixed using montecarlo,s method with always the same points will be enough...

 

[Zurtex]

To shmoe,i have checked all the articles but found no integral representation fro Pi(x) they only speak about calculating Riemann,s Zeta function could you write the integral representation or tell me what,s the name of the paper where the integral appears?..thanks in advance shmoe...

another question is the precision...we now that a(n) will be 0 or 1 so why we need such a high precision?... the same problem would happen with x/ln(x) so why this formula is accepted

Have you ever tried to approximate an integral by a numerical method? Have you ever tried to work out the error generated by a method of approximating an integral my numerical methods?

Because I have and I can tell you that when you put it on to a computer you have to do a lot of working to reduce error and keep runtime to a minimum. Even integrating a fairly simple rational function required looking at areas where the error would be quite high and ways of reducing it.

But your representation of Pi(x) is even worse, not only do you have the error of approximating the integral but you also have the error of approximating the functions and at least the Zeta function is a pain in the ass to approximate.

Perhaps if you gave us an example of how easy you think this representation of Pi(x) is then that would help us understand what you think is so great about your method. Perhaps start on a low number like Pi(20) and show how it is the same run time of another relatively small number like Pi(10000000).

 

[wisredz]

My method is new (is the first method to calculate pi(x) involving an integral and not a sum) so i think is worth publishing,the problem perhaps is that i am not famous and can not compete with these snobish teachers of important universities publishing nonsenses and useless things , sorry i won,t comply anymore...

Come on man what do you talk about? Those snobish you talk about do a lot more than you for math. You cannot talk about them like that. how can you say that waht they publish is useless and unimportant? The most brilliant minds of the world is working on this problem and you call what they do unimportant and useless! I'm not saying that you cannot be among those great minds but come on they have more experience, they have a better grasp of the subject no matter how good you know it etc.

 

[shmoe]

To shmoe,i have checked all the articles but found no integral representation fro Pi(x) they only speak about calculating Riemann,s Zeta function could you write the integral representation or tell me what,s the name of the paper where the integral appears?..thanks in advance shmoe...

You have not checked all the articles there. I gave you the name of the relevant paper "Computing pi(x): an Analytic Method" by Lagarias and Odlyzko. I gave you the webpage where you can find it and the section it's in. There's not much left for you to do to find it.

another question is the precision...we now that a(n) will be 0 or 1 so why we need such a high precision?

Say you needed the integrand to within +/- D to calculate the integral to +/- 0.5. If one of the terms in the integrand grows, you have to find the other terms to a higher precision to get the integrand +/- D.

... the same problem would happen with x/ln(x) so why this formula is accepted

Huh? You know x/log(x) is not calculating anything exactly right? It's an approximation to pi(x) and the relative error goes to zero as x goes to infinity (remember the error term?), it never claims to get pi(x) exactly. It's "accepted" because it's been proven correct (it's also an extremely powerful statement about the distribution of primes).

So the total time will be= time required to calculate Riemmann,s function with accuracy + tiem to calculate an integral with fixed volume (and as th evolume is fixed using montecarlo,s method with always the same points will be enough...

Here's a plan. Quit making claims about how little time it's going to take you to calculate your integral to a given accuracy and accually do a runtime analysis. Don't bother complaining that you don't know how to do such an analysis- learn. Or do a practical implementation like Zurtex has suggested. You don't have to do anything massive, just use your integral to find Pi(x) for a few x<10^9 say and see how long it took you. A supercomputer shouldn't be needed for such a small range.

 

[matt grime]

another question is the precision...we now that a(n) will be 0 or 1 so why we need such a high precision?... the same problem would happen with x/ln(x) so why this formula is accepted
..

do you actually understand any number theory or maths? that is an asymptotic estimate of pi(x), it isn't an expression for pi(x), it differs from pi(x) by a huge amount in absolute terms.

 

[eljose]

i got another expression for Pi(exp(1/t) by solving its integra equation this is:

$$[\pi(2^{1/t})=\frac{1}{2i\pi}\int_{c-i\infty}^{c+i\infty}t^{-s}F(s+1)/G(s+1)ds$$

where F(s) and G(s) are the Mellin transforms of the functions LnR(x)/xln(2) and 1/exp(x)-1

how can i calculate the time needed for this algorithm?...

 

[Zurtex]

i got another expression for Pi(exp(1/t) by solving its integra equation this is:

$$[\pi(2^{1/t})=\frac{1}{2i\pi}\int_{c-i\infty}^{c+i\infty}t^{-s}F(s+1)/G(s+1)$$

where F(s) and G(s) are the Mellin transforms of the functions LnR(x)/xln(2) and 1/exp(x)-1

You do realize that doesn't make any sense as you've not given what variable the integral is respect to?

Could you try and actually show us how you would compute this then and what the error and runtime is?

 

[Muzza]

Could you try and actually show us how you would compute this then and what the error and runtime is?

Don't be such a snob!

 

[Zurtex]

Don't be such a snob!

What on Earth are you on about?

Error and Runtime are an important thing in numerical approximation, without those it's near pointless presenting a new way to calculate such a function to mathematicians in general. Why should they do your work?

I am of course assuming this is new and not already been thought up over a dozen times my students who already realized it wasn't that much use or were told as much by mathematicians they approached.

 

[Hurkyl]

Don't be such a snob!

He's not. Eljose's main problem is that he doesn't seem to know much about numerical computation, yet he's insisting that his formulae give practical methods for computing pi(x).

and as th evolume is fixed using montecarlo,s method with always the same points will be enough...

No, it will not.

Let me give you something simple to allow you to convince yourself otherwise:

Try computing

$$f(a) = \int_0^{\infty} \frac{1}{1 + a^2 x^2} \, dx$$

(where a > 0) via Monte Carlo integration.

You claim that Monte-Carlo integration over a fixed region requires only a fixed number of points to evaluate this integral to the desired accuracy. That would imply that there is an upper bound for f(x). (Why? Because you say we only need to look at finitely many points, and the integrand is always less than 1)

However, you can also do this integral analytically, to convince yourself that f(x) is not bounded.


Still not convinved? Try actually coding up a program to carry do this integral via Monte Carlo integration, and empirically observe the amount of work that must be done to get anything close to the right answer!

 

[Muzza]

What on Earth are you on about?

Sorry, I was trying to make fun of eljose's habit of dismissing valid criticism as snobbery. Apparently it didn't quite pan out as I had expected it to ;)

 

[eljose]

How can i calculate the tme needed for an algorithm?... in the INverse Mellin transform appears the variable t so the tme will depend on t being of a form
O(t^a) being a a real number ..how could i calculate this a?..thanks.

 

[matt grime]

but you'd already said that your metohd was the best so you must have calcualted this> or are you admitting to making intellectually fradulent claims?

 

[eljose]

sorry matt perhpas i exagerated a bit..i thought it was the best because (at least i thought) it provided Pi(x) without calculating a sum or without knowing all the primes but i don,t know how to calculate the time involved running it.

i have given an integral for Pi(e^1/t) so if we want to know the value of Pi for high values we need to calculate the integral for small t

you needn,t make me fun of my poor engilsih or my scarce knowledge of numerical methods, in fact i am a physicist (surprised?) by i like math and someday i would like to contribute to math and physics...

 

[keebs]

i have given an integral for Pi(e^1/t) so if we want to know the value of Pi for high values we need to calculate the integral for small t

t may be small, but e^1/t is large.

you needn,t make me fun of my poor engilsih or my scarce knowledge of numerical methods, in fact i am a physicist (surprised?) by i like math and someday i would like to contribute to math and physics...

What do you do in physics then? Where do you work?

 

[matt grime]

I know you're a physics student, you have said so before. No one is making fun of your poor English, though I have in the past explained to you that the "papers" you have written are poorly presented and thus that will count against you attempting to submit them to anyone. Nor is anyone making fun of the fact that you know no numerical methods. we are pointing out that your claims of speed simplicity uniqueness and originality are unfounded and that making grand claims such as "this probably deserves a field's medal but you're too snobbish to accept that someone not famous could have come up with it" are not winning you any supporters. attacking those who point out the mathematical flaws with such non-mathematical attacks also only serves to underline that you are not prepared to listen and that you probably cannot defend oyur idea on mathematical grounds. you have been given a lot of attention on this forum for your ideas.

 

[Hurkyl]

A run-time analysis is probably best demonstrated by a (simple) example:

Your algorithm is to check if the number n is prime by trial dividing n by every number up through &radic;n.

In pseudocode, it looks like:

for m in the range 2, 3, 4, ..., [√n]
   r := the remainder of n / m
   if r == 0
      print "n is composite"
      quit
end for
print "n is prime"

In the worst-case, we have to go through this loop [&radic;n] - 1 times. Each time through the loop, we must compute one remainder. So, we say that, in the worst-case, this algorithm tests for primality using O(&radic;n) remainder operations. (We can say exactly how many, but that level of detail is generally not of theoretical importance)

(We must also increment m, test if we're done looping, test if the remainder is zero, and other minor things, but these are considered insignificant compared to the rest of the work being done)

Now, if we assume a remainder operation consumes one "unit" of time, we would say that this algorithm runs in O(&radic;n) time, or in "square-root time". For example, that would mean if we quadruple the size of the input, the running time is only doubled.


However, that assumption is not really valid.

I don't recall precisely how much time it takes to compute the remainder of a / b, so I'll make an underestimate, and say it takes O(log a) time to compute the remainder of a / b. (Because it takes at least log a time to simply read all the digits of a)

So, this primality testing algorithm really runs in O(&radic;n log n) time.

Compare this to, say, the AKS primality test, which is said to run in $O((log n)^{4 + \epsilon})$ time. (&epsilon;, here, is your favorite small positive number. Basically, it's saying that using the exponent 4 is an underestimate, but using anything bigger than 4 is an overestimate)

By calculus, we know that &radic;n log n grows much faster than (log n)^(4 + &epsilon;), so we say that the latter algorithm is asymptotically faster than the former.

In practice, that means when n is sufficiently large, the AKS primality test will generally take (much) less time than trial division.