1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

LLT numbers

  1. Nov 19, 2006 #1
    Let's say: [tex]L(x)=x^2-2[/tex] , [tex]L^1 = L[/tex], [tex]L^m = L \circ L^{m-1} = L \circ L \circ L \ldots \circ L[/tex].
    Where [tex]L(x)[/tex] is the polynomial used in the Lucas-Lehmer Test (LLT) :
    [tex]S_0=4 \ , \ S_{i+1}=S_i^2-2=L(S_i) \ ; \ M_q \text{ is prime } \Longleftrightarrow \ S_{q-2} \equiv 0 [/tex] modulo [tex]M_q[/tex] .

    We have:
    [tex]L^2(x)=x^4-4x^2+2[/tex]
    [tex]L^3(x)=x^8-8x^6+20x^4-16x^2+2[/tex]
    [tex]L^4(x)=x^{16}-16x^{14}+104x^{12}-352x^{10}+660x^8-672x^6+336x^4-64x^2+2[/tex]

    Let's call [tex]C_m^+[/tex] the sum of the positive coefficients of the polynomial [tex]L^m(x)[/tex].
    We call [tex]C_m^+[/tex] a "LLT number": [tex]C_1^+ = 1 , C_2^+ = 3 , \ C_3^+ = 23 , \ C_4^+ = 1103 , \ C_5^+ = 2435423 [/tex] .

    It seems that we have the formula: [tex]C_m^+ = 2^m \prod_{i=1}^{m-1} C_{i}^+ - 1 \ \ \text{ for: } m>1 [/tex].

    How to prove it ? (I have no idea ...)

    T.
     
    Last edited: Nov 19, 2006
  2. jcsd
  3. Nov 21, 2006 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Induction?
     
  4. Nov 21, 2006 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    If that pattern of alternating signs keeps up, oberve that

    [tex]
    C_m^+ = \frac{L^m(i) + L^m(1)}{2}
    [/tex]
     
  5. Nov 21, 2006 #4
    Got it !

    OK. I've got a proof. Thanks for the hints! Not so difficult once you think using "i" !
    T.
     
  6. Nov 21, 2006 #5
    LLT numbers and Fermat primes

    Now, more difficult, I think.
    Can you prove:

    [tex] \prod_{i=1}^{2^n-1}C_i^{+} \equiv 1 \pmod{F_n}\ \ [/tex] iff [tex]\ \ F_n=2^{2^n}+1[/tex] is prime.

    T.
     
    Last edited: Nov 21, 2006
  7. Nov 21, 2006 #6
    Better, simpler

    Can you prove:

    [tex]C_{2^n}^{+} \equiv -2 \pmod{F_n} \ \Longleftrightarrow \ F_n=2^{2^n}+1 \text{ is prime.}[/tex].

    T.
     
  8. Nov 21, 2006 #7
    If it has already been proven then why ask us? If not, do you intend to include our names in the published paper as sources of help?
     
  9. Nov 21, 2006 #8
    Hello,
    I'm an amateur: I play with numbers and try to find nice/interesting properties about nice numbers. I have no proof of this one. I like the way Hurkyl did: he gave an hint and then some of the Maths I learnt 30 years ago plus the Number Theory I've learnt these last years come back and I try to find the proof.
    Sure. Last year I asked questions in this forum and got answers and proofs and I wrote a paper where I said who helped me. If I write a paper about the LLT numbers, I'll talk about people who helped me. About a "published" paper, my only candidate target is arXiv.org . So, do not dream about being published in a famous journal. My main goal is fun.
    As examples, look at:
    Generalized Pell Numbers: Zhi-Wei SUN helped me.
    New properties of Mersenne numbers: an anonymous reviewer provided a nice proof.
    Cycles under the LLT modulo a Mersenne prime: 2 guys helped me, including ZetaX from this forum.
    Regards,
    Tony
     
  10. Nov 23, 2006 #9
    Lucas numbers

    I think I have an idea.
    It appears that we have: [tex]L^m(i) = V_{2^m}(1,-1)[/tex], where i is the square root of -1, m is greater than 1, and [tex]V_n(1,-1)[/tex] is a Lucas number defined by: [tex]V_0=2 , V_1=1, V_{n+1}=V_n+V_{n-1}[/tex]. Look at "The Little Book of BIGGER primes" by Paulo Ribenboim, 2nd edition, page 59.
    So, what I called LLT numbers are: [tex]C_m^+ = \frac{V_{2^m}-1}{2}[/tex].
    I did not know this relationship.
    Now, in order to prove the theorem, I think I could use either the method used by Lehmer or the one used by Ribenboim. I'll see.
    Any more ideas ?
    Regards,
    Tony
     
    Last edited: Nov 23, 2006
  11. Nov 23, 2006 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    There's a U sequence too, I think. There's a nice formula not just for increasing the indices by 1, but also for doubling the indices.
     
  12. Nov 23, 2006 #11
    Yes: [tex]V_{2n}=V_n^2-2Q^n[/tex].
    When n is even and Q=-1 or 1, we have: [tex]V_{2^n}=V_{2^{n-1}}^2-2[/tex] which is the LLT basic formula.
    Have I found something useful or is it simply another way to look at an old result ? (Probably second one !)
    T.
     
    Last edited: Nov 23, 2006
  13. Nov 23, 2006 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    IIRC, there's a more general one. If you know [itex]U_m, U_{m+1}, V_m, V_{m+1}[/itex], you can leap directly to [itex]U_{2m}, U_{2m+1}, V_{2m}, V_{2m+1}[/itex]. I don't remember the details; I just wanted to throw it out there, in case the idea was useful. The U and V sequences have a ton of useful properties!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: LLT numbers
  1. Bell Numbers (Replies: 3)

  2. Number Sequence (Replies: 2)

  3. Number theory (Replies: 5)

Loading...