Dtyjlui

I recently posed a question on Code Golf on what I'm terming "Fibonacci Digits", where each number is the sum of the previous two digits, not necessarily the previous two numbers. So, for instance, the series beginning $1,1$ is $1,1,2,3,5,8,13,4,7,11,2dots$ and cycles from there.

As I note in the various examples I bring there, unless something in the series manages to add to either $0$ or $14$, the series seems to always loop to some rotation of $2,3,5,8,13,4,7,11$. Further, it always reaches $0$ or $14$ no later than the third entry in the series. For instance, $S_1=7,7,14,5,9dots$, $S_2=14,5,9dots$, $S_3=68,14,5,9dots$.

In other words, it seems that for $0le(a,b)le9$, then, for $a+b=c$:

1. If $c<10$, let $d=b+c$
   


2. If $cge10$, $c=10x+y$ for some integers $0le(x,y)le9$. Let $d=x+y$.


3. Repeat the above using $c$ and $d$.

Eventually, assuming that you don't start with $0$, this algorithm will yield either $11$ or $14$. Seemingly.

My question is two parts:

1. Is my assessment correct?


2. If so, why?

I'll assume you do not allow negative starting values (it makes sense not to, since we're interested in digits).

Let's start with the second question: Why are 0 and 14 always reached early?

Let's start with 14. How can we reach 14? Let's start with 14, and reconstruct the sequence backwards, digit by digit.

The only two-digit numbers possible are $10$ to $18$, so we need to take care of the case of having two-digit numbers only if the digit-by-digit reconstruction generates a one after a digit 0-8 (remember, we're reconstructing backwards).

• 
  $14, 9, 5, 4, 1$. This makes two options
  
  
  
  
  • The 4, 1 actually comes from 14 (backwards), so the forward sequence is $14, 5, 9, 14$ and we're already in a cycle.
  
  
  • The sequence is $14, 9, 5, 4, 1, 3$. We can't continue beyond the 3 unless we allow negative numbers.
  
  
  
  


• 
  $14, 8, 6, 2, 4$. We can't proceed without allowing negative numbers.


• $14, 7, 7, 0, 7$


• $14, 6, 8$


• $14, 5, 9$

So 14 can't come later than position 6.

The only way to get 0 is if you start with 0, 0. Otherwise you can get 10, but then you have 10, 1, 1, 2, and you get into the standard sequence.

Now, to the first question. Again, we have only 9 possible 2-digit numbers that we can reach, so we can easily confirm that each eventually sends us to the standard sequence $1, 1, 2, dots$:

• $10, 1, 1$


• 
  $11$ done :)


• 
  $12$ done :)


• $13, 4, 7, 11$


• $15, 6, 11$


• 
  $16, 7, 13$ and we know $13$ sends us to 11


• 
  $17, 8, 15$ and we know $15$ sends us to 11


• 
  $18, 9, 17$ and we already know 17


• 
  $19, 10, 1, 1$.

Now, this brute force check is simple enough, but it's boring. That said, there is some intuition behind why (almost) all Fibonacci digit sequences eventually send us to the standard sequence 1, 1, 2... And it's because 10 and 11 send us there. If you consider sums of digits, then there's only 1 way to get 0: 0 + 0. Similarly, we have only 1 way to get 19. However, we many more ways to get 10 and 11 as a sum of two digits. In fact, if you take 2 random digits, the most likely outcome is 10, followed shortly by 11 (and 9). So, eventually, you're very likely to reach either 10 or 11.

From the second entry on, no entry can be larger than $9+9=18$. As an entry only depends on the previous two entries, there must be one or more cycles that can be created. I have found $(2,3,5,8,13,4,7,11)$, $(5,9,14)$, and $0$ as cycles. We can just try all $100$ pairs of single digits to start the sequence. Starting with a two digit number is the same as starting with the two individual digits, so we don't have to try that.

$0$ only comes from starting $(0,0)$
$5,9,14$ comes from $ (0,7),(1,4),(2,6),(3,1),(4,2),(4,5),(5,9),(6,8),(7,0),(7,7),(8,6),(9,5)$

Note that $(3,1)$ only gets to $14$ at the sixth term.

All other starting pairs go to $2,3,5,8,13,4,7,11$ eventually. The latest $11$ comes up is the sixteenth term starting from $(0,2)$