Summations and Recurrences Consider the sum For example, we have and so on. Is Sn ever an integer for any positive integer n? The answer is yes, but the first occurrence of an integer in this sequence is S2755452, 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 x3 - x - 1. For any integers m,n with m greater than or equal to n, define 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., Now, for any non-negative 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 S2N and S2N+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(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 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 S6N+2 is divisible by 6N+2. Now, recall that for all n > 2, and we have the initial values S3 = 3, S4 = 2, and S5 = 5. These happen to be the values that would result from the initial values S0 = 3, S1 = 0, and S2 = 2, so the entire sequence consists of Newton’s sums for the roots of the cubic and by Fermat's theorem we immediately know Sp = S1 = 0 (mod p) and so Sp is divisible by p for every prime p. However, composite integers n such that Sn 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 Sn = 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 S16532714 = 0 (mod 16532714). This is in fact the smallest even pseudoprime relative to (2).