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