Consider an integer.

A large integer.

We are only given the leading digit of this integer in base 3.

The leading digit will be either 1 or 2 because 0 is not a leading digit.

Now imagine that this very large number is divided by 2 MANY time in a row.

There are only 2 sequences possible.

1#

2#

(next start which is always a 1# but part of next segment)

1#

2#

1#

(next start which is always a 1# but part of next segment)

Proof:

Consider the number at the bottom and imagine it is a 2 and we will go backwards multiplying by 2 taking the smallest number and stepping backwards in time.

The leading 2 times 2 gives 4 or 5 if some of the unknown number has a carry up of 1. in base 3 both 4 and 5 having a leading 1 as there are one 3 and either one or two 1s.

IF the smallest number is a 2 we will skip to the 2nd smallest number which we have just proven must be a 1 if it was a 1 we can stay in place.

Now consider the case of 1

1 times 2 is 2 (2 in base 3) or 3 (10 in base 3)

3 times 2 is 6 (20 in base 3) or 7 (21 in base 3) both of which have leading 2s

We already showed that leading 2s always have a leading 1 above so we have the following patterns moving Backwards in time

1#

2#

(1# next segment)

1#

1#

2#

(1# next segment)

These are the only patterns that can exist in the backwards direction

Converting to the forwards direction we merely read them from the bottom to the top and get

Lets call this segment A

1#

2#

(1# in next segment)

and

Lets call this Segment B

1#

2#

1#

(1# in next segment)

Every sequence of divide by 2s on very large integers must be made up of some combination of Segment A and Segment Bs arranged in some order.

Take a large integer and divide by 2 many times for yourself and see that it is true.

Although this doesn’t seem important it is part of an open problem.

submitted by /u/Academic_Trust

[link] [comments]