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
26 James P. Jones and Péter Kiss N = 100, R = 7, a = 6, 6 = 4, N = 1,000, £ = 12, a = 8, 6=2, N = 10,000, R = 12, a = 80, 6 = 20, N = 100,000, £ = 14, a = 269, 6 = 99, N = 1,000,000, £ = 19, a = 154, 6 = 144, N = 10,000,000, £ = 19, a = 1540, 6 = 1440, N = 100,000,000, £ = 23, a = 5143, 6 = 311, N = 1,000,000,000, £ = 23, a = 51430, 6 = 3110. N = 1,000,000,000 happens to be an example of a double number. we have N = II r(c, d) also for c = 22773 and d = 20821, besides a = 51430 and b = 3110. Other examples of double numbers are 15 = £4(6,1) = //4(3,3) and 32 = // 5(9,1) = £ 5(4,4). In the next section we shall prove that the equation N = £ r(a, 6) never has three solutions (a, b) in positive integers with r = R(N). (Of course it may have other solutions when r < R(N). E.g. for A r = 6 and r — 3 we have 6 = £2(1,5) = £2(2,4) = £2(3,3) where 2 < r.) Thus there is no concept of a triple number. 2. An algorithm for R(N ) In this section we shall show that there exists an algorithm for computing R(N). In fact we shall prove that there is a polynomial-time algorithm for computing R(N). We give a procedure which finds, given iV, the value of R(N) and also a and 6. Since the number of steps in the procedure will be less then a polynomial in ln(7V), the number of bit operations needed to compute R(N) will be less than a polynomial in ln(JV). Suppose N is given. To compute R(N), begin with any sufficiently large value of r, satisfying r > R(N). For example by Corollary 1.19 we can take r = [1 -f 2.128 • ln(7V)J . Then proceed as follows. Step 1: Find a positive solution b to the congruence (2.1) N = bF r (mod/;_!), (1 < b). This congruence is solvable in natural numbers since (F r , /V-i ) = 1. Hence there is a solution b in the range 1 < b < F r- \ . Take the least such b in this range. Step 2: Check whether (2.2) bF r < N. If this is the case, put a = (N - bF r)/F r_ 1. Then a is an integer by (2.1). Also we have N = aF r-\ + bF r and condition (2.2) implies 1 < a. In this
