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

[Frank Adams-watters]

Note that this generalizes: in base b there can be at most b predecessors.

Franklin T. Adams-Watters


-----Original Message-----
From: David Seal <david.j.seal at gwynmop.com>
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
Sent: Sat, Nov 2, 2019 4:07 am
Subject: [seqfan] Re: Concatenate the sums of the neighboring digits

> 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:

...

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.

...

David