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

Re: Lucas super-pseudoprime puzzle

Expand Messages
  • mikeoakes2
    ... David, I have at last started to digest that paper. In particular, I believe that the relation between Chebyshev and Lucas polynomials is: T_n(x) =
    Message 1 of 33 , May 26 3:31 PM
      --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
      >
      > This was the puzzle:
      >
      > > Puzzle: Find a composite positive odd integer n that passes
      > > the Lucas test V(a,1,n) = a mod n, for every integer a.
      >
      >[snip]
      >
      > Then by googling
      > > pseudoprime 7056721
      > I arrived at
      > http://adm.lnpu.edu.ua/downloads/issues/2008/N2/adm-n2-4.pdf
      > which proves that n is a solution if and only if it is an odd
      > square-free composite integer such that for each prime p|n
      > n = +/- 1 mod p-1 ... [1]
      > n = +/- 1 mod p+1 ... [2]
      > This paper claims that 7056721 is the unique solution with n < 10^10.

      David,
      I have at last started to digest that paper.
      In particular, I believe that the relation between Chebyshev and Lucas polynomials is:
      T_n(x) = (1/2)*V(2*x,1,n)
      Yes?

      Their definition of a "Chebyshev number" is a composite number n such that
      T_n(a) = a mod n
      for all integers a.

      This translates into:
      V(2*a,1,n) = 2*a mod n
      for all integers a.

      That's a weaker requirement than yours (above), which needs the modular equality to hold for _odd_ first argument of V() as well.

      I wonder whether or not it is really a weaker condition.
      Any views on this?

      Mike
    • mikeoakes2
      ... You did very much what I did. I nearly fell off the chair when I averaged everything out and saw 0.57... :-) ... Not very. Would you buy an appeal to
      Message 33 of 33 , May 27 12:34 PM
        --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
        >
        > I tried 1/n^c:
        >
        > v=[1237.1, 328.7, 105.4, 28.01, 6.22 , 1.510, 0.439, 0.0939];
        > print(vector(8,k,-log(v[k]/10^6)/(k+4)/log(10)));
        >
        > [0.5815, 0.5805, 0.5682, 0.5691, 0.5785, 0.5821, 0.5780, 0.5856]
        >
        > and then A/n^c, using the first datum to remove A:
        >
        > print(vector(7,k,-log(v[k+1]/v[1])/k/log(10)));
        >
        > [0.5756, 0.5348, 0.5484, 0.5747, 0.5827, 0.5750, 0.5885]
        >
        > In both cases c =~ Euler looks rather convincing,
        > given the statistics. Well spotted, Sir!

        You did very much what I did.
        I nearly fell off the chair when I averaged everything out and saw 0.57... :-)

        > How strongly are you committed to A = 1, for the average,
        > given the variability of the overall factor with a?

        Not very.
        Would you buy an appeal to Occam's razor, mon vieux?

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