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

Lucas super-pseudoprime puzzle

Expand Messages
  • djbroadhurst
    ... Definition: The integer pair (q,n) is a Lucas super-pseudoprime (LSPS) pair if and only if n is composite, n q 0, and V(p,q,n) = p mod n, for every
    Message 1 of 46 , Oct 31, 2010
    View Source
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      "djbroadhurst" <d.broadhurst@...> wrote:

      > Proposition: For *every* pair of integers (p,k), we have
      > V(p, (11*k + 3)*29*43, 11*29*37*43) = p mod 11*29*37*43

      Definition: The integer pair (q,n) is a "Lucas super-pseudoprime"
      (LSPS) pair if and only if n is composite, n > q > 0, and
      V(p,q,n) = p mod n, for every integer p.

      With n = 11*29*37*43 = 507529, there are precisely 37 LSPS pairs
      (q,n), namely those with q = (11*k + 3)*29*43, for k = 0 to 36.
      Mike Oakes remarked that 507529 is not a Carmichael number.

      Puzzle: Find an odd square-free non-Carmichael number
      such that there exist more than 70,000 LSPS pairs (q,n).

      Comment: There is a solution with n < 10^7.

      David Broadhurst, All-Hallows-Even, 2010
    • 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
      View Source
      • 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.