Sunday, March 10, 2019

Repeat-Delete Sequences

This week I've been investigating what I call repeat-delete sequences. I have no theory about them, just observations and questions. I thought of them as a variation on the hailstone sequence. To generate a repeat-delete sequence with multiplier m, pick a number and repeatedly apply this rule:

  • If any consecutive digits repeat, delete them.
  • If no consecutive digits repeat, multiply the number by m.
I started with multiplier 2 (m = 2) and checked with a calculator that every (base 10) number up to 50 ended up in one of these cycles:
  • the degenerate 0-cycle (all numbers that consist only of repeats, like 11 or 7744 end up here regardless of the multiplier m)
  • the 1-cycle of length 23
  • the 5-cycle of length 23 (which consists of the terms of the 1-cycle times 10 with one exception)
Whereas every hailstone sequence appears to end up in a 1-cycle of length 3, these sequences appear to end up in one of three cycles. I have now verified this claim with a computer program up to 99999.

Multiplier 3 (m = 3)

The 1-cycle for multiplier 3 has length 25. 2 enters this cycle after 36 iterations.

2, 4, and 6 all enter this cycle after about 35 iterations, but 5 has its own cycle of length 24. For a while all the numbers that are not multiples of 5 enter the 1-cycle while the multiples of 5 either enter the 5-cycle or, if they are also multiples of 10, the 10-cycle (excluding degenerate cases). 29 is the first exception, which has its own cycle of length 24. Other exceptions quickly pile on. 31 enters the 5-cycle, 35 has its own cycle of length 25, and 37 is the first non-degenerate to enter the 0-cycle.

Interesting behavior in the hundreds includes 134 and 142 entering the 6375-cycle of length 25. 175 enters the 425-cycle of length 13, which is the first cycle we've seen whose length isn't about 25. (Are there reasons any of these cycles have the lengths they do?) It appears that if we keep looking we will keep finding more cycles. Here are two lists of cycles. The list on the left contains cycles reached by numbers less than 10,000. The right list is cycles for numbers less than 100,000. Why are the smallest numbers in each cycle all divisible by 5 except for 29?

Using Computer Power

I was having a fun time working out these sequences with a calculator, but I started to run into trouble with m = 5. The number one didn't seem to enter a cycle, so I skipped to three and found that it entered the 9375-cycle of length 28. 7 entered the 875-cycle of length 41. The other multipliers had started with 1-cycles and 5-cycles - these were some (relatively) big numbers!

I switched to m = 7 and found that every number seemed to act differently:

I then took some time to write a computer program. The first thing I wanted to do when I had the program running was try some big starting numbers with big multipliers. It seemed that multipliers could get up into the hundreds and the starting numbers could exceed the trillions and the sequence still would enter a cycle. Here are some random facts I noted:
  • 19394820483094829394 after 1219 iterations with multiplier 93 becomes 990044055 and then enters the 0-cycle
  • 19394820483094829394 with multiplier 219 eventually enters a 4-cycle of length 3810
  • Applying multiplier 613 to 4 yields 7 after 2646 iterations. 7 yields 5 after 1732 iterations. 5 yields 2 after 1166 iterations. 2 yields 50 after 3836 iterations. 50 yields 20 after 1165 iterations. Turns out that the 2-cycle has length 10,004.
Multipliers and their Cycles

Here are the cycles of some multipliers for starting numbers less than 100,000:
Click here for a file that lists all the cycles for multipliers up to 99 for starting numbers up to 99. What do you notice and wonder? I wonder why some multipliers send numbers to a small number of cycles while others seem to explode.

Does every multiplier create cycles? I would imagine that large enough multipliers would overwhelm the deletion of repeats and yield sequences that increase without bound, but I don't know how large the multipliers would have to be. Multipliers as large as 9147 still produce cycles for small inputs:
  • 1 enters the 1-cycle of length 8713
  • 2, 3, and 4, and 5 enter the 5-cycle of length 35,375
Are there any patterns that can be explained in the lengths of the cycles? For example, with multiplier 1591 we find these two cycles:
  • 5 enters the 78-cycle of length 8122
  • 7 enters the 52-cycle of length 8121
Could it be mere coincidence that the length of these cycles differs by one?

Please share any insight you have into these sequences. Have you explored any other variations on the hailstone sequence?

No comments:

Post a Comment