“Lucas chain”的意思、由来-开放百科全书

词条

Lucas chain

释义

References

In mathematics, a Lucas chain is a restricted type of addition chain, named for the French mathematician Édouard Lucas. It is a sequence

a₀, a₁, a₂, a₃, ...

that satisfies

a₀=1,

and

for each k > 0: a_k = a_i + a_j, and either a_i = a_j or |a_i − a_j| = a_m, for some i, j, m < k.^[1]

The sequence of powers of 2 (1, 2, 4, 8, 16, ...) and the Fibonacci sequence (with a slight adjustment of the starting point 1, 2, 3, 5, 8, ...) are simple examples of Lucas chains.

Lucas chains were introduced by Peter Montgomery in 1983.^[2] If L(n) is the length of the shortest Lucas chain for n, then Kutz has shown that most n do not have L < (1-ε) log_φ n, where φ is the Golden ratio.^[1]

References

1. ^¹Guy (2004) p.169
2. ^Kutz (2002)

{{cite book |last=Guy | first=Richard K. | authorlink=Richard K. Guy | title=Unsolved problems in number theory | publisher=Springer-Verlag |edition=3rd | year=2004 |isbn=978-0-387-20860-2 | zbl=1058.11001 | pages=169–171 }}
{{cite journal|first=Martin | last=Kutz |title=Lower Bounds For Lucas Chains |journal=SIAM J. Comput. |year=2002 |volume=31 | number= 6 |pages= 1896–1908 |url=http://www.mpi-inf.mpg.de/~mkutz/pubs/Kutz_LucasChains.pdf |format=PDF | zbl=1055.11077 | doi=10.1137/s0097539700379255}}
{{Cite document|first=Peter L. | last=Montgomery | authorlink=Peter Montgomery (mathematician) | title=Evaluating Recurrences of Form X_m+n = f(X_m, X_n, X_m-n) Via Lucas Chains | year=1983 | journal=Unpublished|url=http://cr.yp.to/bib/1992/montgomery-lucas.ps |format=PS }}

1 : Integer sequences

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。