[seqfan] Re: Bag of digits

David Seal david.j.seal at gwynmop.com
Sat Dec 14 19:48:21 CET 2019


> On 14 December 2019 at 15:38 "M. F. Hasler" <seqfan at hasler.fr> wrote:
> 
> On Sat, Dec 14, 2019 at 10:18 AM David Seal <david.j.seal at gwynmop.com>
> wrote:
> 
> > There is an ambiguity in the definition of this sequence: are digits
> > considered left-to-right or right-to-left? ...
> > ...
> > ... this is first relevant for k=414. After processing k=413, I think the bag
> > is {4,5,6,7,8,9}, so a 4 is thrown away and the remaining digits of k are a
> > 1 and a 4 - but is the resulting sequence term 14 (as a result of the
> > digits being considered in left-to-right order) or 41 (for right-to-left
> > order)?
> 
> I agree with the problem although I perceive it differently,
> If I understand correctly, the contents of the bag don't change until all
> digits of k are scanned.
> Only afterwards the bag is changed.
> (Else for example the first 1 of 11 would be retained but added to the bag
> and then the second one wouldn't be retained,
> but the given example says that it should, both 1's are retained, a(n)=11.)
> However, we now have that ambiguity: if we have one digit 4 in the bag and
> two digits 4 in the number.
> The rule says, the digit 4 in the bag and the digit 4 of the number cancel,
> toss them away.
> But the bag has only one digit 4 -- does it also "cancel" the second 4 in
> the number ?
> IMHO it should, in the same way the absence of 1 has allowed two digits '1'
> to "come in" earlier, and not only one.

That's an interesting third alternative, but it isn't the sequence Jonathan gave us. It's the same as his sequence up to and including k=99, because as it happens, when each of k=11, 22, 33, 44, 55, 66, 77, 88 and 99 is processed, there are none of the relevant digit in the bag and so two copies of that digit are added to the bag under any of the left-to-right, right-to-left and all-at-once interpretations. Those are the only cases of multiple identical digits appearing in k before k=100, so the bag's contents are the same up to and including k=99 under all three interpretations.

At this point, I need a quote from Jonathan's original post:

> On 10 December 2019 at 21:18 jnthn stdhr <jstdhr at gmail.com> wrote:
> ...
> The sequence begins:
> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 1, 1, 1, 20, 1, 22, 3, 4, 25, 6, 27, 8,
> 29, 3, 33, 3, 3, 40, 1, 42, 3, 44, 5, 6, 47, 8, 49, 5, 5, 55, 5, 60, 1, 62,
> 3, 64, 5, 66, 7, 8, 69, 7, 7, 7, 77, 80, 1, 82, 3, 84, 5, 86, 7, 88, 9, 9,
> 9, 9, 9, 99, 100, 1, 2, 103, 4, 105, 6, 107, 8, 10, 1, 11, 11, 11, 11, 11,
> 20, 1, 22, 13, 4, 125, 6, 127, 8, 129, 131, 33, 1, 13, 13, 140, 1, 42, 13,
> 44, 15, 6, 147, 8, 149, 151, 5, 1, 55, 1, 15, 160, 1, 62, 13, 64, 15, 66,
> 17, 8, 169, 171, 7, 1, 7, 1, 77, 1, 180, 1, 82, 13, 84, 15, 86, 17, 88, 19,
> 191, 9, 1, 9, 1, 9, 1, 99, 200]
> 
> The bag size always remains small.  For k > 9 record bag sizes occur at
> (k:record size) 808:11, 8008:12, 10008:13, 80008:15, 800008:16,
> 1000008:17. ...

The bag's contents after processing k=99 do not include any 0s or 1s, as evidenced by the fact that no digits of k=100 are thrown away. So after processing k=100, the bag contains two 0s and one 1. Then under the left-to-right and right-to-left interpretations (which always agree with regard to the bag contents, just not with regard to the generated terms of the sequence), k=101 loses a 0 and a 1, reducing the bag to containing one 0 and no 1s, but then producing a sequence term 1 and adding a 1 to the bag, so that it now contains a 0 and a 1. But under the all-at-once interpretation, k=101 loses a 0 and both 1s, again reducing the bag to containing one 0 and no 1s, but not producing a sequence term or adding any digits to the bag. Assuming the bag doesn't contain a 2 or a 3 after k=99 (which is in fact the case - the bag's contents at that time are {9,9} under all interpretations), k=102 and k=103 then produce sequence terms 2 and 103 under the left-to-right and right-to-left interpretations, but 12 and 3 under the all-at-once interpretation.

As Jonathan's sequence contains ..., 100, 1, 2, 103, ... and not ..., 100, 12, 3, ..., he is not using the all-at-once interpretation. I've also very easily been able to modify my spreadsheet to use the all-at-once interpretation - it just involved changing the formula for the new number of copies of a digit d in the bag in terms of the old number of copies and the number of occurrences of d in k from

if Occurrences < Copies_old then Copies_new = Copies_old - Occurrences
                            else Copies_new = Occurrences - Copies_old

to:

if Copies_old = 0 then Copies_new = Occurrences
                  else Copies_new = Max(Copies_old - Occurrences, 0)

The spreadsheet agreed with Jonathan's record bag sizes of 808:11, 8008:12, 10008:13, 80008:15 before making the change (and would probably have agreed with 800008:16 and 1000008:17 if I'd taken it beyond five digits), but after the change its record bag sizes are 229:11, 2229:12, 22229:13. So I'm fairly certain he's using the left-to-right or right-to-left interpretation and not the all-at-once interpretation.

As I indicated, there does seem to be something interesting going on under all interpretations, as the record bag sizes appear to have some pattern to them in each case. So I'm not arguing that Jonathan's interpretation is either better or worse than yours - just that it's different!

> On 14 December 2019 at 15:38 "M. F. Hasler" <seqfan at hasler.fr> wrote:
> 
> If not, then we have an asymmetry and the ambiguity David mentioned
> (although I would say that left-to-right would be natural,
> since it's the way we construct the sequence and we write the numbers).

Against that, under the right-to-left interpretation, the nth digit has significance 10^(n-1) in the number - rather simpler than the 1st digit having significance 1 if the number is less than 10, significance 10 if the number is at least 10 but less than 100, significance 100 if the number is at least 100 but less than 1000, etc, and the 2nd, 3rd, 4th, etc, digits similarly convoluted significances...

But basically, which is more natural is a variant of the "little-endian vs big-endian" argument in computer science - an argument that hasn't been resolved in any way other than "both exist and have their plus and minus points; learn to live with both" in that field and that I don't expect to have any other resolution in this one!

David



More information about the SeqFan mailing list