Power Trap

Back in 2015, in an article called “Power Trip”, I looked at an unfamiliar sequence created by deleting zeroes from a familiar sequence. And I made a serious but fortunately-not-fatal error in my reasoning. The familiar sequence was powers of 2:

• 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576…

This is what happens when you delete the zeroes from the powers of 2 (and carry on multiplying by two):

2 * 2 = 4
4 * 2 = 8
8 * 2 = 16
16 * 2 = 32
32 * 2 = 64
64 * 2 = 128
128 * 2 = 256
256 * 2 = 512
512 * 2 = 1024 → 124
124 * 2 = 248
248 * 2 = 496
496 * 2 = 992
992 * 2 = 1984
1984 * 2 = 3968
3968 * 2 = 7936
7936 * 2 = 15872
15872 * 2 = 31744
31744 * 2 = 63488
63488 * 2 = 126976
126976 * 2 = 253952
253952 * 2 = 507904 → 5794
5794 * 2 = 11588
11588 * 2 = 23176
23176 * 2 = 46352
46352 * 2 = 92704 → 9274…


I pointed out that this new sequence has to repeat, because deleting zeroes prevents n growing beyond a certain size. Eventually, then, a number will repeat and the sequence will fall into a loop: “This happens at step 526 with 366784, which matches 366784 at step 490.”

But that’s deleting every zero. What happens if you delete every second zero? That is, you start with a zero-count, zc, of 0. When you meet the first zero in the sequence, zc = zc + 1 = 1. When you meet the second zero in the sequence, zc = zc + 1 = 2. So you delete that second zero and reset zc to 0. The first zero occurs when 1024 = 2 * 512, so 1024 is left as it is. The second zero occurs when 2 * 1024 = 2048, so 2048 becomes 248. The sequence for zc=2 looks like this:

1 * 2 = 2
2 * 2 = 4
4 * 2 = 8
8 * 2 = 16
16 * 2 = 32
32 * 2 = 64
64 * 2 = 128
128 * 2 = 256
256 * 2 = 512
512 * 2 = 1024 → 1024
1024 * 2 = 2048 → 248
248 * 2 = 496
496 * 2 = 992
992 * 2 = 1984
1984 * 2 = 3968
3968 * 2 = 7936
7936 * 2 = 15872
15872 * 2 = 31744
31744 * 2 = 63488
63488 * 2 = 126976
126976 * 2 = 253952
253952 * 2 = 507904 → 50794
50794 * 2 = 101588 → 101588
101588 * 2 = 203176 → 23176
23176 * 2 = 46352
46352 * 2 = 92704 → 92704
92704 * 2 = 185408 → 18548

Again, the sequence has to repeat and I claimed that it did so “at step 9134 with 5458864, which matches 5458864 at step 4166”. I also said that I hadn’t found the loop for the delete-every-third-zero sequence, where zc=3. Coming back to this type of sequence in 2021, I wrote a much faster machine-code program to see if I could find the answer for zc=3. And I thought that I had. My program said that the sequence for zc=3 repeats at step 166369 with 6138486272, which matches 6138486272 at step 25429.

Or does it repeat? Does it match? In 2021 I suddenly realized that I had neglected to consider something vital back in 2015: whether the zero-count was the same when the sequence appeared to repeat. Take the zc=2 sequence. If zc=0 at at step 4166 and zc=1 at 9134 (or vice versa), the sequence isn’t in a loop, because it will be deleting a different set of zeroes after step 4166 than it is after step 9134.

I checked whether the zero-count for that sequence is the same when the sequence appears to repeat. Fortunately, it is the same and the zero-delete sequence for zc=2 does indeed begin looping “at step 9134 with 5458864, which matches 5458864 at step 4166”.

So my error wasn’t fatal for the zc=2 sequence. But what about the zc=3 sequence? Alas, the zero-count is different for 6138486272 at step 166369 than for 6138486272 at step 25429. The sequence doesn’t behave the same after those steps and hasn’t looped. I needed to find the n1 = n2 for steps s1 and s2 where zc1 = zc2. And even with the much faster machine-code program it took some time. But I can now say that 958718377984 at step 379046, with zc=0, matches 958718377984 at step 200906, with zc=0.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.