[seqfan] Re: Concatenate the sums of the neighboring digits

David Seal david.j.seal at gwynmop.com
Sat Nov 2 07:21:54 CET 2019


> There was some discussion on this (loops etc) on SeqFan in August 2011, cf http://list.seqfan.eu/pipermail/seqfan/2011-August/007775.html

Following that up, I noticed the following question from Lars Blomberg in http://list.seqfan.eu/pipermail/seqfan/2011-August/007842.html, another post in the same thread:

"Also, the count of predecessors of each number between 1 and 10^10 shows 
that a count of 0 is by far the most common with 85%.
Only 1233 numbers have 10 predecessors.
For example: 101091199 has predecessors
1918363 2827454 3736545 4645636 5554727 6463818 7372909 82810181 91009272 
91901090."

"No number has been found with more than 10 predecessors.
Can this curious circumstance be proven as a fact?"

I haven't found any answer posted to that question, but I can prove that no number N >= 0 has more than ten predecessors, as follows:

0 can only be generated from a number with no digit pairs, so its only predecessors are the ten single-digit numbers 0, 1, 2, ..., 9. Otherwise, N > 0 and any predecessor P must have at least two digits. Let p be the last digit of P, P' be P with its last digit removed (i.e. P' = floor(P/10)) and p' the last digit of P' = the next-to-last digit of P. I assert that for any (N,p) pair, there is at most one possible value of P, from which it clearly follows that for any value of N, there are at most ten possible values of P because p can only be one of the digits 0, 1, 2, ..., 9.

The proof is by induction on the value of N. The last digit sum p'+p that creates it must end with its last digit n, so either p'+p = n or p'+p = 10+n. Now split into cases:

* If n >= p, p'+p = 10+n isn't possible, since p' cannot be >= 10. So p'+p = n, i.e. the last digit of N is the sum of the last two digits of P. If N only has that one digit, the only possible value of P consists of p' = n-p followed by p. Otherwise define N' to be N without its last digit, i.e. N' = floor(N/10). It follows that P' has last digit p' = n-p, P' is a predecessor of N' and 0 < N' < N, and so there is at most one possible value of P' by inductive hypothesis.

* If n < p, p'+p = n isn't possible, since p' cannot be negative. So p'+p = 10+n, i.e. the last two digits of N are 1n. This isn't possible if the next-to-last digit of N is anything other than 1, so in that case, there are no possible values of P. Otherwise, if N only has those two digits, the only possible value of P consists of p' = 10+n-p followed by p. Otherwise define N' to be N without its last two digits, i.e. N' = floor(N/100). It follows that P' has last digit p' = 10+n-p, P' is a predecessor of N' and 0 < N' < N, and so there is at most one possible value of P' by inductive hypothesis.

When those cases conclude that there is at most one possible value of P', it follows from P = 10*P' + p that there is at most one possible value of P. So in all cases, there is at most one possible value of P, completing the proof.

To illustrate how this works, the predecessor of 101091199 with last digit 2 is uniquely determined by the following inductive steps:

(N,p) = (101091199,2): n=9, so n >= p and (N',p')
is calculated as (floor(101091199/10), 9-2). Inductively:
  (N,p) = (10109119,7): n=9, so n >= p and (N',p')
  is calculated as (floor(10109119/10), 9-7). Inductively:
    (N,p) = (1010911,2): n=1, so n < p and (N',p')
    is calculated as (floor(1010911/100), 10+1-2). Inductively:
      (N,p) = (10109,9): n=9, so n >= p and (N',p')
      is calculated as (floor(10109/10), 9-9). Inductively:
        (N,p) = (1010,0): n=0, so n >= p and (N',p')
        is calculated as (floor(1010/10), 0-0). Inductively:
          (N,p) = (101,0): n=1, so n >= p and (N',p')
          is calculated as (floor(101/10), 1-0). Inductively:
            (N,p) = (10,1): n=0, so n < p. N only has the two digits
            10, so P is 10+0-1 = 9 followed by 1, i.e. P = 91.
          P = 10*91+0 = 910.
        P = 10*910+0 = 9100.
      P = 10*9100+9 = 91009.
    P = 10*91009+2 = 910092.
  P = 10*910092+7 = 9100927.
P = 10*9100927+2 = 91009272.

David



More information about the SeqFan mailing list