How do I identify pattern of different bases? For example, base $3$?

Question

Recently,I asked a question on number patterns.Turns out it wasn't the usual number pattern question.It was the sum of the digits at base 3.

How do I identify such number patterns or even know that it's at a different base?I can't really conclude that it's a number pattern of a sum of digits at a different base just by looking at it right?Any advice on such questions?

For example,

$(0,1,2,1,2,3,2,3,4,1,2,3,2,3,4,3,4,5,2,3,4,...)$

Supposedly,that is the sum of digits of n at base 3.How can I identify such patterns?

Answer 1

Look up Kolmogorov complexity. One can fix a programming language and then define the answer to such pattern-continuation questions as the shortest program $P$ such that $P(0),P(1),\cdots$ agrees with the given terms. Now in general it is impossible to systematically find such a program, which means that we cannot hope to solve all except the simplest questions, but at least we can compare solutions according to this standard to see which is simpler.

Suppose we choose Javascript (as of today) as the programming language, and the required program must be named f and take a single variable as input. Then for the pattern in your question, your proposed solution would be f=function(n){return n==0?0:n%3+f((n-n%3)/3)}, indeed quite short! It wins f=function(n){return [0,1,2,1,2,3,2,3,4][n%9]+(n-n%9)/9}, and I guess it would win all others too, since the sequence you gave is rather long.

Now how to guess the solution? Well the first observation is that it splits into triples of increasing consecutive numbers starting with "0,1,2" and "1,2,3" and "2,3,4", and if you look at the starting number of each triple it is "0,1,2,1,2,3,2" which looks exactly like the sequence itself! This is sufficient to generate the whole pattern, because we start with "0", and then replace each term $x$ by a triple "$x,x+1,x+2$", and repeat this as many times as we want:

$0$

$0,1,2$

$0,1,2,1,2,3,2,3,4$

$0,1,2,1,2,3,2,3,4,1,2,3,2,3,4,3,4,5,2,3,4,3,4,5,4,5,6$

...

Since this generates the pattern we desire, and is quite simple, we can justifiably say that it is 'the right solution'. It turns out that this is equivalent to the base-3 interpretation that you mention in your question. Here's why.

The base-3 interpretation would mean that the desired function $f$ satisfies:

$f(3n) = f(n)$ for any natural $n$.

$f(3n+1) = f(n)+1$ for any natural $n$.

$f(3n+2) = f(n)+2$ for any natural $n$.

Now notice that this is exactly what the other interpretation does! The triple at positions $3n,3n+1,3n+2$ in the sequence is generated from the term at position $n$, where $f(n)$ was replaced by $f(n),f(n)+1,f(n)+2$. Therefore the two interpretations give the same sequence.

Which interpretation you prefer is subjective. Some people would argue that "sum of digits in base-3" is simpler than my replacement interpretation, but that is only if you already know the notion of "base-3"! If you have to give an explanation of base-3 notation it would be longer than the description of my interpretation, so mine wins. That really is the whole point of using a fixed programming language, which just means that you have to do by yourself everything the programming language does not know. It essentially forces you to define everything except a fixed set of basic notions.