primes in an arithmetic prog.

Expand Messages
• 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
Message 1 of 3 , Aug 31, 2002
• 0 Attachment
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:
> > you can see my article about prime numbers at:
> >
> >
>
http://www.gallup.unm.edu/~Smarandache/SMRuiz-nextprime.pdf
> >
> > 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
>
> For example, what's the point in replacing the
> sigma0 function with a sum
> that has exponential complexity?
And what's the
> 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
• ... 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
Message 2 of 3 , Aug 31, 2002
• 0 Attachment
--- Sebastian Martin <sebi_sebi@...> wrote:
> 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.

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
• 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
Message 3 of 3 , Aug 31, 2002
• 0 Attachment
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
> > 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
Your message has been successfully submitted and would be delivered to recipients shortly.