# LLT numbers

1. Nov 19, 2006

### T.Rex

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

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

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

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

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

T.

Last edited: Nov 19, 2006
2. Nov 21, 2006

### CRGreathouse

Induction?

3. Nov 21, 2006

### Hurkyl

Staff Emeritus
If that pattern of alternating signs keeps up, oberve that

$$C_m^+ = \frac{L^m(i) + L^m(1)}{2}$$

4. Nov 21, 2006

### T.Rex

Got it !

OK. I've got a proof. Thanks for the hints! Not so difficult once you think using "i" !
T.

5. Nov 21, 2006

### T.Rex

LLT numbers and Fermat primes

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

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

T.

Last edited: Nov 21, 2006
6. Nov 21, 2006

### T.Rex

Better, simpler

Can you prove:

$$C_{2^n}^{+} \equiv -2 \pmod{F_n} \ \Longleftrightarrow \ F_n=2^{2^n}+1 \text{ is prime.}$$.

T.

7. Nov 21, 2006

### Playdo

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?

8. Nov 21, 2006

### T.Rex

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

9. Nov 23, 2006

### T.Rex

Lucas numbers

I think I have an idea.
It appears that we have: $$L^m(i) = V_{2^m}(1,-1)$$, where i is the square root of -1, m is greater than 1, and $$V_n(1,-1)$$ is a Lucas number defined by: $$V_0=2 , V_1=1, V_{n+1}=V_n+V_{n-1}$$. Look at "The Little Book of BIGGER primes" by Paulo Ribenboim, 2nd edition, page 59.
So, what I called LLT numbers are: $$C_m^+ = \frac{V_{2^m}-1}{2}$$.
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
10. Nov 23, 2006

### Hurkyl

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

11. Nov 23, 2006

### T.Rex

Yes: $$V_{2n}=V_n^2-2Q^n$$.
When n is even and Q=-1 or 1, we have: $$V_{2^n}=V_{2^{n-1}}^2-2$$ 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
12. Nov 23, 2006

### Hurkyl

Staff Emeritus
IIRC, there's a more general one. If you know $U_m, U_{m+1}, V_m, V_{m+1}$, you can leap directly to $U_{2m}, U_{2m+1}, V_{2m}, V_{2m+1}$. 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!