Misplaced Pages

Lehmer sequence

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
"Lehmer number" redirects here. It can also refer to a hypothetical solution to Lehmer's totient problem.

In mathematics, a Lehmer sequence U n ( R , Q ) {\displaystyle U_{n}({\sqrt {R}},Q)} or V n ( R , Q ) {\displaystyle V_{n}({\sqrt {R}},Q)} is a generalization of a Lucas sequence U n ( P , Q ) {\displaystyle U_{n}(P,Q)} or V n ( P , Q ) {\displaystyle V_{n}(P,Q)} , allowing the square root of an integer R in place of the integer P.

To ensure that the value is always an integer, every other term of a Lehmer sequence is divided by √R compared to the corresponding Lucas sequence. That is, when R = P the Lehmer and Lucas sequences are related as:

P U 2 n ( P 2 , Q ) = U 2 n ( P , Q ) U 2 n + 1 ( P 2 , Q ) = U 2 n + 1 ( P , Q ) V 2 n ( P 2 , Q ) = V 2 n ( P , Q ) P V 2 n + 1 ( P 2 , Q ) = V 2 n + 1 ( P , Q ) {\displaystyle {\begin{aligned}P\,U_{2n}({\sqrt {P^{2}}},Q)&=U_{2n}(P,Q)&U_{2n+1}({\sqrt {P^{2}}},Q)&=U_{2n+1}(P,Q)\\V_{2n}({\sqrt {P^{2}}},Q)&=V_{2n}(P,Q)&P\,V_{2n+1}({\sqrt {P^{2}}},Q)&=V_{2n+1}(P,Q)\end{aligned}}}

Algebraic relations

If a and b are complex numbers with

a + b = R {\displaystyle a+b={\sqrt {R}}}
a b = Q {\displaystyle ab=Q}

under the following conditions:

Then, the corresponding Lehmer numbers are:

U n ( R , Q ) = a n − b n a − b {\displaystyle U_{n}({\sqrt {R}},Q)={\frac {a^{n}-b^{n}}{a-b}}}

for n odd, and

U n ( R , Q ) = a n − b n a 2 − b 2 {\displaystyle U_{n}({\sqrt {R}},Q)={\frac {a^{n}-b^{n}}{a^{2}-b^{2}}}}

for n even.

Their companion numbers are:

V n ( R , Q ) = a n + b n a + b {\displaystyle V_{n}({\sqrt {R}},Q)={\frac {a^{n}+b^{n}}{a+b}}}

for n odd and

V n ( R , Q ) = a n + b n {\displaystyle V_{n}({\sqrt {R}},Q)=a^{n}+b^{n}}

for n even.

Recurrence

Lehmer numbers form a linear recurrence relation with

U n = ( R − 2 Q ) U n − 2 − Q 2 U n − 4 = ( a 2 + b 2 ) U n − 2 − a 2 b 2 U n − 4 {\displaystyle U_{n}=(R-2Q)U_{n-2}-Q^{2}U_{n-4}=(a^{2}+b^{2})U_{n-2}-a^{2}b^{2}U_{n-4}}

with initial values U 0 = 0 , U 1 = 1 , U 2 = 1 , U 3 = R − Q = a 2 + a b + b 2 {\displaystyle U_{0}=0,\,U_{1}=1,\,U_{2}=1,\,U_{3}=R-Q=a^{2}+ab+b^{2}} . Similarly the companion sequence satisfies

V n = ( R − 2 Q ) V n − 2 − Q 2 V n − 4 = ( a 2 + b 2 ) V n − 2 − a 2 b 2 V n − 4 {\displaystyle V_{n}=(R-2Q)V_{n-2}-Q^{2}V_{n-4}=(a^{2}+b^{2})V_{n-2}-a^{2}b^{2}V_{n-4}}

with initial values V 0 = 2 , V 1 = 1 , V 2 = R − 2 Q = a 2 + b 2 , V 3 = R − 3 Q = a 2 − a b + b 2 . {\displaystyle V_{0}=2,\,V_{1}=1,\,V_{2}=R-2Q=a^{2}+b^{2},\,V_{3}=R-3Q=a^{2}-ab+b^{2}.}

All Lucas sequence recurrences apply to Lehmer sequences if they are divided into cases for even and odd n and appropriate factors of √R are incorporated. For example,

U 2 n ( R , Q ) = R U 2 n − 1 ( R , Q ) − Q U 2 n − 2 ( R , Q ) U 2 n + 1 ( R , Q ) = R U 2 n ( R , Q ) − Q U 2 n − 1 ( R , Q ) V 2 n ( R , Q ) = R V 2 n − 1 ( R , Q ) − Q V 2 n − 2 ( R , Q ) V 2 n + 1 ( R , Q ) = R V 2 n ( R , Q ) − Q V 2 n − 1 ( R , Q ) {\displaystyle {\begin{aligned}U_{2n}({\sqrt {R}},Q)&={\phantom {R\,}}U_{2n-1}({\sqrt {R}},Q)-Q\,U_{2n-2}({\sqrt {R}},Q)&U_{2n+1}({\sqrt {R}},Q)&=R\,U_{2n}({\sqrt {R}},Q)-Q\,U_{2n-1}({\sqrt {R}},Q)\\V_{2n}({\sqrt {R}},Q)&=R\,V_{2n-1}({\sqrt {R}},Q)-Q\,V_{2n-2}({\sqrt {R}},Q)&V_{2n+1}({\sqrt {R}},Q)&={\phantom {R\,}}V_{2n}({\sqrt {R}},Q)-Q\,V_{2n-1}({\sqrt {R}},Q)\end{aligned}}}

References

  1. Weisstein, Eric W. "Lehmer Number". mathworld.wolfram.com. Retrieved 2020-08-11.


Stub icon

This number theory-related article is a stub. You can help Misplaced Pages by expanding it.

Categories: