- The computational complexity is (nlogn)^3 for the

problem 38 formulas, I have not studied the complexity

for the problem 39.

And the formulas in the article primes in an aritmetic

progression is also polinomial.

--- Phil Carmody <thefatphil@...> escribió: >

--- Sebastian Martin <sebi_sebi@...> wrote:> > Hello all:

http://www.gallup.unm.edu/~Smarandache/SMRuiz-nextprime.pdf

> > you can see my article about prime numbers at:

> >

> >

>

> >

And what's the

> > and other formulas at:

> >

> > http://www.primepuzzles.net/problems/prob_038.htm

> > http://www.primepuzzles.net/problems/prob_039.htm

> >

> > Any comment or improvements will be welcome.

>

>

> What computatioal complexity do algorithms based on

> your formulae have?

>

> For example, what's the point in replacing the

> sigma0 function with a sum

> that has exponential complexity?

> point in performing that sum

_______________________________________________________________

> repeatedly inside another expression whose number of

> terms is exponential in

> the side of the problem size?

>

> Phil

>

Yahoo! Messenger

Nueva versión: Webcam, voz, y mucho más ¡Gratis!

Descárgalo ya desde http://messenger.yahoo.es - --- Sebastian Martin <sebi_sebi@...> wrote:
> The computational complexity is (nlogn)^3 for the

It depends on how you judge the size of the problem, I should have been more

> problem 38 formulas, I have not studied the complexity

> for the problem 39.

> And the formulas in the article primes in an aritmetic

> progression is also polinomial.

explicit. It's fairly common to view the size of a problem parametrised by

the number N as log(N). O(poly(N)) is exponential in log(N).

For example, consider the discussions surrounding the recent AKS algorithm.

Trial division to sqrt(N) is sub-linear in N, but is expoential in log(N).

Trial division would never be described as a sub-linear algorithm in any

context I've encountered.

Sieving, however, adopts a 'N is linear' nomenclature, as does prime

counting, so I did probably chose the wrong default (oh the joys of having

two defaults).

With that in mind - can you explain why a contrived O(n^(3+eps)) algorithm

has any practical merit when there exist O(n^(1+eps)) algorithms or better

that do the same job?

I am reminded of the classic 'grand revolutionising factoring algorithm':

http://groups.google.com/groups?th=621fa55443f7d8b3&rnum=1

which was subsequently 'pessimised' in the follow-ups.

Phil

=====

"The hottest places in Hell are reserved for those who, in

times of moral crisis, preserved their neutrality."

-- John F. Kennedy, 24 June 1963, claiming to quote Dante,

to whom this has been incorrectly attributed ever since.

__________________________________________________

Do You Yahoo!?

Yahoo! Finance - Get real-time stock quotes

http://finance.yahoo.com - I already know that the topic doesn't have a lot of

practical interest.

But I hope this can have certain theoretical interest.

This perhaps could help somebody to find an algorithm

but efficient.

--- Phil Carmody <thefatphil@...> escribió: >

--- Sebastian Martin <sebi_sebi@...> wrote:> > The computational complexity is (nlogn)^3 for the

http://groups.google.com/groups?th=621fa55443f7d8b3&rnum=1

> > problem 38 formulas, I have not studied the

> complexity

> > for the problem 39.

> > And the formulas in the article primes in an

> aritmetic

> > progression is also polinomial.

>

> It depends on how you judge the size of the problem,

> I should have been more

> explicit. It's fairly common to view the size of a

> problem parametrised by

> the number N as log(N). O(poly(N)) is exponential in

> log(N).

>

> For example, consider the discussions surrounding

> the recent AKS algorithm.

> Trial division to sqrt(N) is sub-linear in N, but is

> expoential in log(N).

> Trial division would never be described as a

> sub-linear algorithm in any

> context I've encountered.

>

> Sieving, however, adopts a 'N is linear'

> nomenclature, as does prime

> counting, so I did probably chose the wrong default

> (oh the joys of having

> two defaults).

>

> With that in mind - can you explain why a contrived

> O(n^(3+eps)) algorithm

> has any practical merit when there exist

> O(n^(1+eps)) algorithms or better

> that do the same job?

>

> I am reminded of the classic 'grand revolutionising

> factoring algorithm':

>

>

> which was subsequently 'pessimised' in the

_______________________________________________________________

> follow-ups.

>

>

> Phil

>

>

>

> =====

> "The hottest places in Hell are reserved for those

> who, in

> times of moral crisis, preserved their neutrality."

> -- John F. Kennedy, 24 June 1963, claiming to quote

> Dante,

> to whom this has been incorrectly attributed ever

> since.

>

> __________________________________________________

> Do You Yahoo!?

> Yahoo! Finance - Get real-time stock quotes

> http://finance.yahoo.com

>

Yahoo! Messenger

Nueva versión: Webcam, voz, y mucho más ¡Gratis!

Descárgalo ya desde http://messenger.yahoo.es