- MacTutor History of Mathematics

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}

v_{43}

= 5.4093 x 10178485291567 approximately. Again, the only problem is to show that the first index

n_{0}

with

v_{n¬0}

not in Z is

n_{0} = 43

, since the size of

v_{n¬0}

then follows from the easily proved formula

v_{n} ~ (n^{2} + 2n - 1 + 4n^{-1} - 21n^{-2} + 137n^{-3} - ...) \times C^{2^n}

with C = 1.04783144757641122955990946274313755459... .

We first replace

v_{n}

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.