A positive integer is written on the board. Each second you write 3 or 9 on the right next to it. Is it true that you always get a composite number in finite time?

(One can easily check that the digits 0,1,2,4,5,6,7,8 easily give a composite number. That's why I am asking only for 3 and 9.)

If we only allowed 3, then given a prime $p\geq10$, the infinite sequence 3, 33, 333, ... will have two numbers with the same remainder mod $p$ (Pigeonhole principle) and by subtracting and removing 0s we get a number $A$ composed of 3s and divisible by $p$ - in which case $\overline{pA}$ shall be composite.

Any help appreciated!

  • $\begingroup$ To clarify - are we repeating the same digit, or can we mix 3s and 9s? For example, $1\to 13\to 139\to 1393\to 13933\to 139339$. $\endgroup$ – jmerry Mar 23 at 9:58
  • $\begingroup$ @jmerry You can mix. $\endgroup$ – DesmondMiles Mar 23 at 10:01
  • $\begingroup$ Why is it clear that, say, using $1,7$ or $3,7$ can't work? $\endgroup$ – lulu Mar 23 at 10:04
  • 1
    $\begingroup$ Interesting question. I don't see any way to attack the $3,9$ case. Doesn't mean there isn't one, of course. $\endgroup$ – lulu Mar 23 at 10:57
  • 1
    $\begingroup$ An infinite sequence of this kind would be a miracle, but I do not see a possibility to rule it out. $\endgroup$ – Peter Mar 23 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.