Loading ...
Sorry, an error occurred while loading the content.

primes in an arithmetic prog.

Expand Messages
  • Sebastian Martin
    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
      > your formulae have?
      >
      > 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
    • Phil Carmody
      ... 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':
        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
      • Sebastian Martin
        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':
          >
          >
          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
          >

          _______________________________________________________________
          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.