Copyright © University of Cambridge. All rights reserved.
'Mathematical Swimmer' printed from https://nrich.maths.org/
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$