At the primary and upper primary levels, students encounter and easily master the tests for divisibility by 2, 5, 3, 9, 4, 6, 8 and 11. They do not always study why the tests work, but they are easy to execute and students do not forget them easily.
A few observant students wonder at the absence of the number 7 from this list. Occasionally, a keen student may discover such a test for himself or herself. Of course, it is a thrilling experience when this happens, for the students as well as the teachers. Such a test was discovered by Chika Ofili, a Nigerian student in Westminster Under School1, London, UK.
Chika's test for divisibility by 7 is easy enough to perform by hand. We describe it here in the words of his math teacher, Miss Mary Ellis:
In a bored moment, Chika had turned his mind to the problem and this is what he came up with. He realized that if you take the last digit of any whole number, multiply it by 5 and then add this to the remaining part of the number, you will get a new number. And it turns out that if this new number is divisible by 7, then the original number is divisible by 7. What an easy test!
She adds:
The opposite is also true in that if you don't end up with a multiple of 7, then the original number is not divisible by 7 either.
We consider a few examples to illustrate how the test works:
-
Take the number 532. Its last digit is 2, so the prescribed operation is \[ 532 \longrightarrow 53 + (5 \times 2) = 63 \] Note that both 63 and 532 are multiples of 7.
-
Take the number 973. Its last digit is 3, so the prescribed operation is \[ 973 \longrightarrow 97 + (5 \times 3) = 112 \] We can repeat the same operation with the number 112. Its last digit is 2, so the prescribed operation is \[ 112 \longrightarrow 11 + (5 \times 2) = 21 \] Note that both 21 and 973 are multiples of 7.
-
Take the number 873. Its last digit is 3, so the prescribed operation is \[ 873 \longrightarrow 87 + (5 \times 3) = 102 \] We can repeat the same operation with the number 102. Its last digit is 2, so the prescribed operation is \[ 102 \longrightarrow 10 + (5 \times 2) = 20 \] Note that both 20 and 873 are non-multiples of 7.
Input
A line containing a number $$n \in \mathbb{N}_0$$.
Output
A reduction step on a number $$r \in \mathbb{N}$$ ($$r > 9$$) is an operation that yields a new positive integer by multiplying the last digit of $$r$$ by 5 and then adding this to the remaining part of $$r$$.
To test whether the number $$n \in \mathbb{N}_0$$ is divisible by 7, we repeatedly perform reduction steps until we arrive at the number 49 or a number smaller than 10. Print all intermediate results of the reduction steps on a separate line, starting with the number $$n$$ itself.
Then print a final line that indicates whether the number $$n$$ is divisible by 7. This is the case if and only if the reduction process ended at the number 49 or the number 7.
Example
Input:
77777
Output:
77777
7812
791
84
28
42
14
21
7
77777 is divisible by 7
Example
Input:
66666
Output:
66666
6696
699
114
31
8
66666 is not divisible by 7