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

Re: Lucas super-pseudoprimes for Q <> 1

Expand Messages
  • mikeoakes2
    ... Thanks for that, David. For c), I benefited from your Chinese hint: hereby gratefully acknowledged. I think the best thing about a) was that it was truly
    Message 1 of 46 , Nov 4, 2010
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
      >
      > Excellent: post-hoc speed-ups are always welcome.
      >
      > Yet first credit should always go to the first
      > discovery. Happily this also goes to you:
      >
      > http://tech.groups.yahoo.com/group/primenumbers/message/21947
      > > I have just finished a 1 GHz-yr investigation of this Conjecture
      > > In every case but one, n was indeed a Carmichael number,
      > > but for n = 507529 = 11*29*37*43, the conditions are satisfied
      >
      > a) To discover 1 non-Carmichael: 1 GHz-year (MO)
      > b) To discover 6 more: less than 1 GHz-hour (DB)
      > c) To recover all 7: less than 1 GHz-minute (MO)
      >
      > Which is the more meritorious?
      >
      > I incline to think : (a), by MO, at beginning of this process.

      Thanks for that, David.
      For c), I benefited from your Chinese hint: hereby gratefully acknowledged.

      I think the best thing about a) was that it was truly exhaustive, in that it assumed no restriction on the number of factors of n; and as we have seen, the bulk of the time needed is for checking out semiprimes (even with your CRT improvement).
      We can be certain that 507529 is a[1] for Neil's OEIS entry, when we get round to creating it.
      But a[2] is currently not certain, as b) assumed no semiprime solution exists.

      The algorithm in c) is almost linear in n_max, which is remarkable, isn't it.
      I have run it up to n_max=10^10 so far, and found 89 non-Carmichaels.
      The core of the lemma is one line of pari-GP code, but it's unproven. It was found "by inspection", after wrestling for some time with the following deep paper by Richard Pinch:
      http://www.chalcedon.demon.co.uk/rgep/p20.pdf
      [I can't remember, did you flag it in an earlier posting?]

      The algorithm seems to work, and certainly gives those solutions, and only those, which your code gives, where they overlap.
      I wonder if you can co-discover it?
      (My turn to set a Puzzle:-)

      Mike
    • djbroadhurst
      ... http://physics.open.ac.uk/~dbroadhu/cert/dbmo116.out gives my 116, in the format [n, factors, number of solutions] With n
      Message 46 of 46 , Nov 9, 2010
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "mikeoakes2" <mikeoakes2@...> wrote:

        > > My revised count up to 2*10^10 is 116.
        > My (original) count up to 2*10^10 was 105.
        > So it must have missed 11, i.e. a bigger proportion.

        http://physics.open.ac.uk/~dbroadhu/cert/dbmo116.out
        gives my 116, in the format [n, factors, number of solutions]

        With n < 2*10^10, the record-holder for the number of solutions is
        [2214495361, [13, 17, 23, 29, 83, 181], 147407]
        which googles quite nicely, linking to
        http://www.cs.rit.edu/usr/local/pub/pga/fibonacci_pp

        David
      Your message has been successfully submitted and would be delivered to recipients shortly.