Problem of the Week 803:

Superbase Shrinkage

Superbase 2 notation is power-of-2 notation in which each power is also written in base 2, and each power of a power as well, etc. For example: In base 2, 41 = 2^5 + 2^3 + 1 In superbase 2, 41 = 2^2^2+1 + 2^2+1 + 1. So, in superbase 2, only 1's and 2's appear.

Consider the following sequence of integers, from a given starting value n:
n₁ = n;
For n₂, write n₁ in superbase 2 notation and replace each 2 by a 3
For n₃, subtract 1 from n₂, write the result in superbase 3 notation, and replace each 3 by a 4
For n₄, subtract 1 from n₃, write the result in superbase 4 notation, and replace each 4 by a 5
and so on.

It is an amazing fact that, for any n₁, this sequence becomes 0 eventually!

Problem: Let n₁ = 4. How many steps until the sequence zeros out?

I would be pleased to see answers (not necessarily complete solutions!) on this one to see if they agree with what I think the answer is.

---

To see that you understand the definition and to underscore the surprising nature of the result, here are a few steps for n₁ = 41.

41                             n1 = 41

2^(2^2+1) + 2^(2+1) + 1
3^(3^3+1) + 3^(3+1) + 1        n2 = 22876792455043


3^(3^3+1) + 3^(3+1)    
4^(4^4+1) + 4^(4+1)            So n3 = 

        53631231719770388398296099992823384509917463\
         2823695735108942457748870561202941879072074\
         9719266761371076012743274594420341501553124\
         7786279785734596024337408


4^(4^4+1) + 4^(4+1) - 1
4^(4^4+1) + 3*4^4 + 3*4^3 + 3*4^2 + 3*4 + 3
5^(5^5+1) + 3*5^5 + 3*5^3 + 3*5^2 + 3*5 + 3
                               So n5 is about 10^2184


5^(5^5+1) + 3*5^5 + 3*5^3 + 3*5^2 + 3*5 + 2
6^(6^6+1) + 3*6^6 + 3*6^3 + 3*6^2 + 3*6 + 2
                               So n6 is about 10^36305

Again: The problem is: How many steps (approximately) until the result is 0?

© Copyright 1996 Stan Wagon. Reproduced with permission.