2002 BAMO p5 prime-testing trail of Professor Moriarty, station 1429
Source:
August 26, 2019
combinatoricsnumber theoryprime
Problem Statement
Professor Moriarty has designed a “prime-testing trail.” The trail has stations, labeled .
Each station is colored either red or green, and contains a table which indicates, for each of the digits , another station number. A student is given a positive integer , and then walks along the trail, starting at station . The student reads the first (leftmost) digit of and looks this digit up in station ’s table to get a new station location. The student then walks to this new station, reads the second digit of and looks it up in this station’s table to get yet another station location, and so on, until the last (rightmost) digit of has been read and looked up, sending the student to his or her final station. Here is an example that shows possible values for some of the tables. Suppose that :
https://cdn.artofproblemsolving.com/attachments/f/3/db47f6761ca1f350e39d53407a1250c92c4b05.png
Using these tables, station , digit leads to station m station , digit leads to station , and
station is green.
Professor Moriarty claims that for any positive integer , the final station (in the example, ) will be green if and only if is prime. Is this possible?