Az Eszterházy Károly Tanárképző Főiskola Tudományos Közleményei. 1998. Sectio Mathematicae. (Acta Academiae Paedagogicae Agriensis : Nova series ; Tom. 25)
JONES, J. P. and Kiss, P., Representation of integers as terms of a linear recurrence with maximal index
Representation of integers as terms of a. . . 27 case the algorithm terminates arid R(N) = r. If (2.2) does not hold, then we decrease r by 1 and return to Step 1. We iterate steps 1 and 2, decreasing r until (2.2) holds. Since initially R(N) < [1 + 2.128 • hi{N)\ < r, the algorithm must terminate after at most [1 + 2.128 -ln(yV)] iterations. We claim that this computation is polynomial time. Certainly the number of operations needed at each step is less than or equal to a polynomial in ln(jV). Calculation of F r requires time exponential in ln(r), i.e. proportional to a polynomial in r. However r is less than or equal to a polynomial in ln(7V), since F r < N . So this is polynomial time. In addition to finding r, the algorithm also finds (a, 6) such that H r(a 1 b ) = N . The pair (a, b ) is not uniquely dependent upon N . There is sometimes a second pair (c, d) such that H r(c,d ) = N. As sketched above the algorithm finds the pair (a, 6) with least b. It can easily be extended also to find the second pair (c, (i), when that exists. After (a,b ) has been found, let d — b + F r_ 1 and c = a — F r. Then N = // r(c, ci) by Lemma 1.2. d is positive. If dF r < iV, then c will also be positive and (c, d) will be a second pair. If not, then there is no second pair, i.e. N is a single. The algorithm can be simplified to yield a more explicit formula for r — R(N) and explicit formulas for a, ö, c and d. For this we shall use an old identity of LUCAS [4]: Multiplying both sides of (2.3) by (-1 ) rN and rearranging terms we get Equation (2.4) provides a solution to the linear diophantine equation aF r1 -f bF r = N . It shows that AF r-\ + BF r = N will hold if we put A = J4 r(jV) and B = B r(N), where (2.5) A r(N) = {-lyFr^N and B r{N) = ~{-l) r F r_ 2N . Thus a = A r(N ) and b = B r(N) is a particular solution of the equation aF r_! + bF r = N . Since (F r, F r +i ) = 1, from a particular solution we may obtain all solutions (a, b) by (2.6) a = A r{N) - tF r, b = B r(N ) + *F r_i, (t = 0, ±1, ±2, ±3,...). Then by Lemma 1.1 H r(a,b ) = N for all integers t. Now define g r(N) and h r(N) by (2.3) F 2 r_ x - F r_2 • F r = (-1 y. (2.4) (-1 ) rF r-iN • F r_! - (-l) rF r_2A T • F r = N. (2.7) 9T(N) = (l) rF r2N + 1 FT- 1 and
