Mathematical swimmer

Ian from Birmingham started us off:

 

A fraction can be simplified if the denominator and the numerator have a common factor. The number of lengths must have a common factor with every number smaller than it, apart from $1$ or a prime.

 

A number cannot have a common factor with one less than it apart from $1$ and $2$, so the number of lengths must be one bigger than a prime number for this to work.

 

I started experimenting with number one bigger than a prime number. The largest I found was $30$.

Jadryk from Fen Ditton C.P. School and Lynn from St Margaret's School sent us in their reasoning

I noticed that $30$ has $3$ factors, all of which are prime numbers. So all numbers under $30$ with one of these as a factor will simplify.

 

If there is a number under $30$ that does not simplify, it cannot have $2, 3$ or $5$ as factors. The next prime number is $7$. This does not need to simplify as it is prime. So I had to find the smallest number that was not prime and did not have $2, 3$ or $5$ as factors. This number is $7 \times 7 = 49$. As this is bigger than $30$ this is ok.

 

So the rule I found was that if the number of lengths is to work, then if it has $5$ prime factors, then the $6^{th}$ prime number squared must be bigger than the number of lengths.

 

So for a number with $4$ prime factors, it must have $2, 3, 5$ and $7$ as factors, and must be less than $11^2 = 121$. The smallest number with $4$ factors is $2 \times 3 \times 5 \times 7 = 210$, which is bigger than $11^2 = 121$ so does not work.

 

I don't think any numbers bigger than $30$ will satisfy the simplification.  So I think $30$ is the biggest number that saisfies the lengths.

 

Well done Jadryk and Lynn! Ellie from Wimbledon High School explained this is more general terms. Can you follow her argument and see how it relates to Jadryk and Lynn's from above?

 

For this question, I called the number of lengths $n$. By the fundamental theorem of arithmetic $n$ can be written uniquely as a product of prime numbers, we want at least one of these prime numbers to be a factor for all the numbers below $n$, except for the prime numbers.

Then if $n$ can be written $n = p_1^{r_1} \times p_2^{r_2} \times ... \times p_m^{r_m}$ then all other numbers are of the form $k = p_1^{s_1} \times ... \times p_m^{s_m} \times ... \times p_q^{s_q}$

For a number to be prime it must be of the form $p=p_i$.

For a number less than $n$ to have a common factor with $n$, it must share a common prime factor, and so be of the form $k = p_1^{s_1} \times ... \times p_q^{s_q}$ where at least one of the $s_1, ... , s_m$ is non zero.

So we know that for $n$ to satisfy the number of lengths condition that all $k$ less than $n$ must be of the form above, so be prime or share at least one prime factor.

 

For $n$ to satisfy the lengths conditions, there cannot be a non prime number less than $n$ that does not share a common prime factor. So there cannot exist a $j = p_{m+1}^{s_{m+1}} \times ... \times p_q^{s_q}$, with the sum of the $s_i$'s greater than 1, that is less than $n$

The smallest number this could be would be $(p_{m+1})^2$.

 

So we have a condition on $n = p_1^{r_1} \times ... \times p_m^{r_m}$ that for the lengths condition to hold, $(p_{m+1})^2 > n$

 

The largest $n$ I can find is $30$.

 

To prove this is the largest possible, I need to prove that

 $\prod_{m=1}^{N} p_m > (p_{N+1})^2$ for all $N> 3$