SESNs: Self-Erasure Surviving Numbers & memories of childhood math games

I enjoy algorithmic/computational number puzzles. When I was a kid (age 9 or 10?) I checked out a book from the public library that, among other things, had a simple game you could play on paper or with a calculator:

• Pick a whole number > 0
• If it is odd, multiply it by 3 and add 1
• If it is even, divide it by 2

The book said (IIRC) that all numbers would eventually reach 1. For example, the unlucky number 13 reaches 1 in 9 steps:

• Start with 13.

1. (13 x 3) + 1 = 40
2. 40/2 = 20
3. 20/2 = 10
4. 10/2 = 5
5. (5 x 3) + 1 = 16
6. 16/2 = 8
7. 8/2 = 4
8. 4/2 = 2
9. 2/2 = 1

As a child I didn't know that this game had a real name other than "3x+1". It's actually the Collatz Conjecture, and it is an unsolved problem in number theory as to whether every number will eventually reach 1 or not.

A few years ago I produced some computer generated art based on the 3x+1 problem.

But all this has just been by way of introduction to Eric Angelini's rec.puzzles posting this morning about Self-erasing numbers. In his own words:

Take an integer like 36, for example.
Concatenate an infinite amount of copies. You get:

  363636363636363636363636363636...

- read the leftmost digit -"3"-,
- jump *over* 3 digits (to the right), land on (3) and erase
  it:

  3636(3)6363636363636363636363636...
  ^
- read the leftmost unread digit, jump only visible digits,
  erase:

  3636(3)6363(6)36363636363636363636...
  ^^
- repeat until you see a substring like this [...(a)36(b)...]
   [(a) and (b) are erased digits - "36" is the integer you
   are, testing]: bingo, you have found a "Self-erasure survi-
   ving number" (SESN):

"36" is such a number:

  3636(3)63(6)3(6)36(3)(6)3(6)36363636363636...
  ^^^^   ^^       ..  <-- hit

This erasing technique gives sometimes quite complicated pat-
terns. "16", for instance, is not a SESN -- but it takes a
while to see:

16(1)616(1)61(6)1(6)(1)6(1)(6)1(6)1(6)1(6)1(6)(1)6(1)616(1)61(6)1(6)
^^   ^^^   ^^   ^      ^      ^   ^   ^   ^      ^   ^^^   ^^   ^
     |_______________________________________________|
                    recurrent pattern 

The first SESN I have found by hand are:

0 1 2 3 4 5 6 7 8 9 10 20 23 24 25 26 27 28 29 30 32 36 37
38 39 40 42 ...

[BTW, reading "0" means erasing the closest visible digit
immediately to the right]

No SESN > 10 begins with "1" -- see why?
No SESN > 299 begins with "2", etc.

The sequence is finite, thus.

Last term?

I wrote a program to compute whether a number is a Self-Erasure Surviving Number tonight—a fun diversion.

Though, either I have a bug, or I don't see why a number beginning with 1, which is greater than 10, can't be an SESN... it would appear that 114 is a valid SESN. Consider the output from my program (which adopts the notation used by Eric) for ./SESN.tcl 114:

114114114114114114114114114114114114114114114114114114114114
11(4)114114114114114114114114114114114114114114114114114114114
^
11(4)1(1)4114114114114114114114114114114114114114114114114114114
^^
11(4)1(1)4(1)14114114114114114114114114114114114114114114114114114
^^   ^
11(4)1(1)4(1)1411(4)114114114114114114114114114114114114114114114114
^^   ^   ^
11(4)1(1)4(1)14(1)1(4)114114114114114114114114114114114114114114114114
^^   ^   ^   ^
11(4)1(1)4(1)14(1)1(4)114(1)14114114114114114114114114114114114114114114
^^   ^   ^   ^^       !!!
114 is a Self-Erasure Surviving Number (SESN)!

Time for bed; there will be time to ponder 114 more deeply during the commute.

Oh, and if you want to play the 3x+1 game sometime—perhaps during a boring meeting, or when you are stuck in traffic and have a lot of time to kill—start with 27...

—Michael A. Cleverly
Thursday, July 07, 2005 at 23:53