Consider the sum N (2N+k)! S(N) = SUM ---------------- k=0 (2N-2k)! (1+3k)! For example, we have S(1) = 5/4 S(2) = 51/14 S(3) = 277/20 and so on. Is S(n) ever an integer for any positive integer n? The answer is yes, but the first occurrence of an integer in this sequence is S(2755452), which is an integer having just over 2 million digits. This is related to the fact that n=6*2755452+2 is the smallest pseudoprime of the form 6N+2 relative to the cubic polynomial x^3 - x - 1. For any integers m,n with m greater than or equal to n, define F(m,n) = 2C(m,n) + C(m-1,n-1) where C(m,n) = m!/(n!(m-n)!) is the binomial coefficient. We also define F(m,n)=0 if m < n or n < 0. Since the F coefficients are just a linear function of the binomial coefficients they clearly satisfy the same recurrence, i.e., F(m,n) = F(m-1,n) + F(m-1,n-1) (1) Now, for any non-negative integer N, define S(2N) = SUM F(N-k,2k) S(2N+1) = SUM F(N-k,2k+1) k > =0 k > =0 It follows that for any integer q > 2 we have the recurrence S(q) = S(q-2) + S(q-3) To prove this, first consider the case where q is odd. In that case we can put q=2N+1 and the recurrence can be written as S(2N+1) = S(2(N-1)+1) + S(2(N-2)) By the definitions of S(2N) and S(2N+1) this relation is SUM F(N-k,2k+1) = SUM F(N-1-k,2k+1) + SUM F(N-1-k,2k) k > =0 k > =0 k > =0 which follows immediately from (1) for each k. On the other hand, if q is even, we can put q=2N and the recurrence can be written as S(2N) = S(2(N-1)) + S(2(N-2)+1) which by definition is SUM F(N-k,2k) = SUM F(N-1-k,2k) + SUM F(N-2-k,2k+1) k > =0 k > =0 k > =0 By a shift of index the last sum can be written as SUM F(N-2-k,2k+1) = SUM F(N-1-k,2k-1) k > =0 k > =1 and since F(N-1,-1)=0 the summation can be carried over k > = 0, so again we can apply relation (1) for each k to give the result. We now consider the values of S(6N+2) for any positive integer N. By definition we have N S(6N+2) = S(2(3N+1)) = SUM F(3N+1-k,2k) k=0 Also, from the definition of F(m,n) we have 2 (m!) (m-1)! F(m,n) = --------- + ------------- n! (m-n)! (n-1)! (m-n)! 2 (m!) n m! = --------- + - ---------- n! (m-n)! m n! (m-n)! (m-1)! = (2 + n/m) C(m,n) = (2m+n) -------- n!(m-n)! Therefore we have N [(3N+1-k)-1]! S(6N+2) = SUM [2(3N+1-k)+(2k)] --------------------- k=0 (2k)![(3N+1-k)-(2k)]! N (3N-k)! = (6N+2) SUM ------------------ k=0 (2k)! (3N-3k+1)! If we evaluate the terms in the summation in reverse order by substituting N-k for each k, we have the equivalent expression N (2N+k)! S(6N+2) = (6N+2) SUM ---------------- k=0 (2N-2k)! (3k+1)! Consequently, the summation in question is an integer if and only if S(6N+2) is divisible by (6N+2). Now, recall that S(n) = S(n-2) + S(n-3) for all n > 2, and we have the initial values S(3)=3, S(4)=2, and S(5)=5. These happen to be the values that would result from the initial values S(0)=3, S(1)=0, and S(2)=2, so the entire sequence consists of Newtons sums for the roots of the cubic x^3 - x - 1 = 0 (2) and by Fermat's theorem we immediately know S(p)=S(1)=0 (mod p) and so S(p) is divisible by p for every prime p. However, composite integers n such that S(n) is divisible by n are quite rare. These are called pseudoprimes relative to the cubic (2). We are seeking a pseudoprime of the form n = 6N+2. To prove that N=2755452 gives such a number, we need only show that S(n) = 0 (mod n) for n = 6*2755452+2 = 16532714. The nth term of any linear recurring sequence (mod n) can be evaluated in log(n) steps (using binary exponentiation), so it's not hard to verify that s(16532714)=0 (mod 16532714). This is in fact the smallest even pseudoprime relative to (2).

Return to MathPages Main Menu