Solution: Day 5, problem 3

The solutions of the fifth day problems problems are somewhat longer and we only give highlights.

The sequence ( vn ) starts 2, 3, 5, 10, 28, 154, 3520, 1551880, 267593772160, 7160642690122633501504, ...
It is required to show that the first non - integral vn is v43 = 5.4093 x 10178485291567 approximately. Again, the only problem is to show that the first index n0 with vn0 not in Z is n0 = 43, since the size of vn0 then follows from the easily proved formula vn ~ (n2 + 2n - 1 + 4n-1 - 21n-2 + 137n-3 - ...) × C2n with C = 1.04783144757641122955990946274313755459... .

We first replace vn by sn = 2 + v12 + ... + vn-12 = n vn. Then the recursion becomes sn+1 = sn = sn2/n2 with initial condition s1 = 2. Let us look at one prime p at a time. The first sn which could fail to be p-integral is sp+1, which will happen if and only if sp is not divisible by p, so we can test this by looking at the sequence (s1, s2, ... ,sp ) modulo p. This is an easy calculation since the numbers sj (mod p) do not grow, and we find with a couple of minutes on a computer that sp = 0 modulo p for each prime p < 43 but not for 43. (Note that this calculation cannot be done directly since no computer can compute or store the sn's for n bigger than about 22.) This proves that v43 is not integral (it has a denominator divisible by 43), and that vp is at least p-integral for p less than 43.

To check that vn is actually integral for n ≤ 42 we must only compute the sequence sn modulo quite modest powers of primes less than 43, and this is easily done on the computer. The real question is why the congruence sp = 0 modulo p holds for all primes less than 43, since naively one would think that its probability of holding for even one prime p is about 1/p, which is quite small. But in fact its probability of holding for a given p is quite large, since in the recursion for the sn, if any sn with n < p happens to take on the value -n2 mod p then all of the following sn are 0 mod p, and the chance of this happening can be expected to be about 63%. Also, this argument holds for any initial value s1, and the value s1 = 2 has been chosen to make the first few primes behave.