Maths Olympiad Prep

Library / /81 of 397

Number theory Difficulty 5.2 AIME, harder Prove it Taiwan

Starting from the positive integer 3737, a digit 55 is added in front of each term in succession, forming the following sequence:

3737, 537537, 55375537, 5553755537, 555537555537, ...

How many terms in this sequence are prime?

Solution

Only the 11st term of this sequence is prime; all other terms are composite.

Denote the nnth term of this sequence by ana_n. By mathematical induction, the following facts can be established:

- a1a_1 is divisible by 3737. an+3=55510n+1+ana_{n+3} = 555 \cdot 10^{n+1} + a_n, and 555=3537555 = 3 \cdot 5 \cdot 37. So a1,a4,a7,a_1, a_4, a_7, \dots are all multiples of 3737.

- a2=537a_2 = 537 is divisible by 33. an+3=55510n+1+ana_{n+3} = 555 \cdot 10^{n+1} + a_n, and 555=3537555 = 3 \cdot 5 \cdot 37. So a2,a5,a8,a_2, a_5, a_8, \dots are all multiples of 33.

- a3=5537=7791a_3 = 5537 = 7 \cdot 791 is a multiple of 77. an+6=55555510n+1+ana_{n+6} = 555555 \cdot 10^{n+1} + a_n, and 555555=5551001555555 = 555 \cdot 1001 is a multiple of 77. So a3,a9,a15,a_3, a_9, a_{15}, \dots are all multiples of 77.

- a6=5555537=13427349a_6 = 5555537 = 13 \cdot 427349 is a multiple of 1313. an+6=55555510n+1+ana_{n+6} = 555555 \cdot 10^{n+1} + a_n, and 555555=5551001555555 = 555 \cdot 1001 is a multiple of 1313, so a6,a12,a18,a_6, a_{12}, a_{18}, \dots are all multiples of 1313.

In summary, only a1=37a_1 = 37 is prime; all other terms are divisible by one of 7,13,377, 13, 37, and are therefore composite.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.