Summations and Recurrences 

Consider the sum 

_{} 

For example, we have 

_{} 

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 

_{} 

where C(m,n) = m!/[n!(mn)!] 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., 

_{} 

Now, for any nonnegative integer N, define 

_{} 

It follows that for any integer q > 2 we have the recurrence 

_{} 

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 

_{} 

By the definitions of S_{2N} and S_{2N+1} this relation is 

_{} 

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 

_{} 

which by definition is 

_{} 

By a shift of index the second sum on the right side can be written as 

_{} 

and since F(N1,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 

_{} 

Also, from the definition of F(m,n) we have 

_{} 

Therefore we have 

_{} 

If we evaluate the terms in the summation in reverse order by substituting N  k for each k, we have the equivalent expression 

_{} 

Consequently, the summation in question is an integer if and only if S_{6N+2} is divisible by 6N+2. Now, recall that 

_{} 

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 Newton’s sums for the roots of the cubic 

_{} 

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). 
