ON INTEGER SEQUENCES GENERATED BY LINEAR MAPS

摘要

Let x0 < x1 < x2 < ··· be an increasing sequence of positive integersngiven by the formula xn =u0003βxn−1 + γ u0004 for n = 1, 2, 3,..., where β> 1and γ are realnnumbers and x0 is a positive integer.We describe the conditions on integers bd ,..., b0,nnot all zero, and on a real number β> 1 under which the sequence of integers wn =nbdxn+d +···+ b0xn, n = 0, 1, 2,..., is bounded by a constant independent of n. Thenconditions under which this sequence can be ultimately periodic are also described.nFinally, we prove a lower bound on the complexity function of the sequence qxn+1 −npxn ∈{0, 1,..., q − 1}, n = 0, 1, 2,..., where x0 is a positive integer, p > q > 1arencoprime integers and xn =u0006pxn−1/qu0007 for n = 1, 2, 3,.... A similar speculative resultnconcerning the complexity of the sequence of alternatives (F : x→x/2or S : x→(3x +n1)/2) in the 3x + 1 problem is also given.