On the Number of Integer Recurrence Relations

Abstract

This paper presents the number of k-stage integer recurrence relations (IRR) over the ring  Z₂   which generates sequences of maximum possible period (2^k-1)2^e-1 for e>1. This number corresponds to the primitive polynomials mod 2 which satisfy the condition proposed by Brent and is2^(e-2)k+1(2^k-1-1) for  e>3. This number is same as measured by Dai but arrived at with a different condition for maximum period. Our way of counting gives an explicit method for construction of such polynomials. Furthermore, this paper also presents the number of different sequences corresponding to such IRRs of maximum period.