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 linear recurrence with maximal index JAMES P. JONES

1 and PÉTER KISS

2 Abstract. For sequences H

n(a,b) of positive integers, defined by H

0 = a, Hi-b and //„-//„_! + //„_2, we investigate the problem: for a given positive integer N find positive integers a and b such that N=H

n(a,b) and n is as large as possible. Denoting by R(N) = r the largest integer, for which N=H

r(a,b) for some a and 6, we give bounds for R(N) and a polynomial time algorithm for computing it. Some properties of R(

/V) are also proved. Introduction Let H

n(a,b) be a sequence of positive integers defined by HQ = a, II

1 = b and H

n = H

n _i -f II

n2 where a and b are arbitrary positive integers (the parameters). The sequence H

n(a,b

) occurs in a problem of COHN [1]: Given a positive integer N

, find positive integers a and b such that N = H

n(a

, 6) and n is as large as possible. COHN [1] actually formulated the problem slightly differently, replacing 'n is as large as possible' by 'a + 6 is as small as possible'. However this makes little difference. We shall consider the problem as stated above. Let R = R(N) be the largest integer R such that N — IIji(a

, b) for some a, b > 1. The function R is well defined. For any N > 1, there exist integers a, b and n such that N = H

n(a,b

), 1 < a, 1 < b. Since N = IIi(l,N), we can let n = 1, a = 1 and b = N

. If 2 < N

, we can also let a — 1, b = N — 1 and n = 2 so N = H

2(l,N — 1). Thus there always exist integers n, a and b such that N — H

n(a, 6), 1 < a and 1 < b. It is also easy to see that there exist a, b and r such that N = H

r(a

, b), 1 < a, 1 < b and r is maximal. If A

r = i/

r(a,6), 1 < a and 1 < 6, then r < H

r(a.b). Hence for all such r,a and b, r < N. Thus all possible values of r are bounded above by TV. In fact this argument shows that R(N) < N for all N. 1 Research supported by National Science and Research Council of Canada Grant No. OGP 0004525. 2 Research supported by Foundation for Hungarian Higher Education and Research and Hungarian OTKA Foundation Grant No. T 16975 and 020295.