What is so great about 7?

Question

I'm going to write down my problem verbatim:

Write down the integers from $1$ to $50$ in rows of $10$ numbers each. Mark out $1$, and then cross out all multiples of $2$ greater than $2$ (i.e., cross out, $4, 6, 8, . . . ). 3$ is not crossed out, so cross out all multiples of $3$ greater than $3$ (i.e., cross out $6, 9, 12, . . . )$. Find the next number $f$ after $3$ which is not crossed out. This is the next prime. Cross out all non-unary multiples of $f$. Continue in this way until you get to the end of the list, and the numbers which haven’t been crossed out are the primes less than $50$. Notice that the last sequence of multiples you crossed off while doing this were multiples of $7$.

What’s special about $7$ in this list?

If, instead of using just the numbers from $1$ to $50$ you had used the numbers from $1$ to $1000$, what’s the smallest composite number that would not have been crossed off after crossing off the multiples of $7$?

Answer 1

It is known that a composite integer $a$ has a prime divisor $p$ that satisfies the inequality $p\leq a$. If you let $a=50$, then it will have prime divisor $p$ that is less than or equal to $\sqrt{50}$.The greatest among possible p's is 7. Thus in employing the Sieve you will just cross out the multiples of prime $p$ 2,3,5 and lastly multiples of 7. The numbers that are not cross out are the primes from 1 to 50 which are 2,3,5,7,11,13,17,19,23,29,31,37,41,43 and 47. The special in 7 is that it is the greatest prime that you need to cross out its multiple.

Answer 2

$7$ is the largest integer less than the square root of $50$.

Answer 3

First, write down each number like you told me to do:

$\begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\ 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20\\ 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30\\ 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40\\ 41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 & 50 \end{array}$

Now cross out $1$ and multiples of $2$ greater than $2$:

$\begin{array}{cccccccccc} \not1 & 2 & 3 & \not4 & 5 & \not6 & 7 & \not8 & 9 & \not10\\ 11 & \not12 & 13 & \not14 & 15 & \not16 & 17 & \not18 & 19 & \not20\\ 21 & \not22 & 23 & \not24 & 25 & \not26 & 27 & \not28 & 29 & \not30\\ 31 & \not32 & 33 & \not34 & 35 & \not36 & 37 & \not38 & 39 & \not40\\ 41 & \not42 & 43 & \not44 & 45 & \not46 & 47 & \not48 & 49 & \not50 \end{array}$

Now cross out multiples of $3$ greater than $3$:

$\begin{array}{cccccccccc} \not1 & 2 & 3 & \not4 & 5 & \not6 & 7 & \not8 & \not9 & \not10\\ 11 & \not12 & 13 & \not14 & \not15 & \not16 & 17 & \not18 & 19 & \not20\\ \not21 & \not22 & 23 & \not24 & 25 & \not26 & \not27 & \not28 & 29 & \not30\\ 31 & \not32 & \not33 & \not34 & 35 & \not36 & 37 & \not38 & \not39 & \not40\\ 41 & \not42 & 43 & \not44 & \not45 & \not46 & 47 & \not48 & 49 & \not50 \end{array}$

The next not-crossed out number is $5$, which is then $f$. Cross out all the non-unary numbers of that:

$\begin{array}{cccccccccc} \not1 & 2 & 3 & \not4 & 5 & \not6 & 7 & \not8 & \not9 & \not10\\ 11 & \not12 & 13 & \not14 & \not15 & \not16 & 17 & \not18 & 19 & \not20\\ \not21 & \not22 & 23 & \not24 & \not25 & \not26 & \not27 & \not28 & 29 & \not30\\ 31 & \not32 & \not33 & \not34 & \not35 & \not36 & 37 & \not38 & \not39 & \not40\\ 41 & \not42 & 43 & \not44 & \not45 & \not46 & 47 & \not48 & 49 & \not50 \end{array}$

As you just saw, $49$ is not crossed out, so that's the smallest composite number of the group that hasn't been crossed out, plus it's $7^2$.