## Solution: Day 5, problem 3

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

The sequence ( *v*_{n} ) starts 2, 3, 5, 10, 28, 154, 3520, 1551880, 267593772160, 7160642690122633501504, ...

It is required to show that the first non - integral *v*_{n} is *v*_{43} = 5.4093 x 10^{178485291567} approximately. Again, the only problem is to show that the first index *n*_{0} with *v*_{n0} not in **Z** is *n*_{0} = 43, since the size of *v*_{n0} then follows from the easily proved formula *v*_{n} ~ (*n*^{2} + 2*n* - 1 + 4*n*^{-1} - 21*n*^{-2} + 137*n*^{-3} - ...) × *C*^{2n} with C = 1.04783144757641122955990946274313755459... .

We first replace *v*_{n} by *s*_{n} = 2 + *v*_{1}^{2} + ... + *v*_{n-1}^{2} = *n* *v*_{n}. Then the recursion becomes *s*_{n+1} = *s*_{n} = *s*_{n}^{2}/*n*^{2} with initial condition *s*_{1} = 2. Let us look at one prime *p* at a time. The first *s*_{n} which could fail to be *p*-integral is *s*_{p+1}, which will happen if and only if *s*_{p} is not divisible by *p*, so we can test this by looking at the sequence (*s*_{1}, *s*_{2}, ... ,*s*_{p} ) modulo *p*. This is an easy calculation since the numbers *s*_{j} (mod *p*) do not grow, and we find with a couple of minutes on a computer that *s*_{p} = 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 *s*_{n}'s for *n* bigger than about 22.) This proves that *v*_{43} is not integral (it has a denominator divisible by 43), and that *v*_{p} is at least p-integral for p less than 43.

To check that *v*_{n} is actually integral for *n* ≤ 42 we must only compute the sequence *s*_{n} modulo quite modest powers of primes less than 43, and this is easily done on the computer. The real question is why the congruence *s*_{p} = 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 *s*_{n}, if any *s*_{n} with *n* < *p* happens to take on the value -*n*^{2} mod *p* then all of the following *s*_{n} 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 *s*_{1}, and the value *s*_{1} = 2 has been chosen to make the first few primes behave.