Lehmer sequence

"Lehmer number" redirects here. It can also refer to a hypothetical solution to Lehmer's totient problem.

In mathematics, a Lehmer sequence is a generalization of a Lucas sequence.

Algebraic relations

If a and b are complex numbers with

[math]\displaystyle{ a + b = \sqrt{R} }[/math]

[math]\displaystyle{ ab = Q }[/math]

under the following conditions:

• Q and R are relatively prime nonzero integers
• [math]\displaystyle{ a/b }[/math] is not a root of unity.

Then, the corresponding Lehmer numbers are:

[math]\displaystyle{ U_n(\sqrt{R},Q) = \frac{a^n-b^n}{a-b} }[/math]

for n odd, and

[math]\displaystyle{ U_n(\sqrt{R},Q) = \frac{a^n-b^n}{a^2-b^2} }[/math]

for n even.

Their companion numbers are:

[math]\displaystyle{ V_n(\sqrt{R},Q) = \frac{a^n+b^n}{a+b} }[/math]

for n odd and

[math]\displaystyle{ V_n(\sqrt{R},Q) = a^n+b^n }[/math]

for n even.

Recurrence

Lehmer numbers form a linear recurrence relation with

[math]\displaystyle{ U_n = (R-2Q)U_{n-2}-Q^2U_{n-4} = (a^2+b^2)U_{n-2}-a^2b^2U_{n-4} }[/math]

with initial values [math]\displaystyle{ U_0=0,\, U_1=1,\, U_2=1,\, U_3=R-Q=a^2+ab+b^2 }[/math]. Similarly the companion sequence satisfies

[math]\displaystyle{ V_n = (R-2Q)V_{n-2}-Q^2V_{n-4} = (a^2+b^2)V_{n-2}-a^2b^2V_{n-4} }[/math]

with initial values [math]\displaystyle{ V_0=2,\, V_1=1,\, V_2=R-2Q=a^2+b^2,\, V_3=R-3Q=a^2-ab+b^2. }[/math]