Monday, December 19, 2022

Binary complement sequences

On Friday, Joshua Searle posted to the Sequence Fanatics Discussion list a neat procedure: take the binary complement of an integer multiplied by 3. Iterate. For example, starting with 3 we get the binary of 9 (1001), the complement of which (0110) is 6. Continuing, from 6 we get the binary of 18 (10010), the complement of which (01101) is 13. Arriving at zero, we stop.

 0 3
 1 6
 2 13
 3 24
 4 55
 5 90
 6 241
 7 300
 8 123
 9 142
10 85
11 0

Eleven steps to get to zero. The largest integer reached is 300 at step 7. We can shorthand the sequence data for 3 with (11,7,300) [steps to reach zero, steps to reach a maximum, the maximum]. Here are the statistics for integer starts up to 28:

 0 (0,0,0)
 1 (1,0,1)
 2 (2,0,2)
 3 (11,7,300)
 4 (12,8,300)
 5 (1,0,5)
 6 (10,6,300)
 7 (3,1,10)
 8 (4,2,10)
 9 (13,9,300)
10 (2,0,10)
11 (19,15,300)
12 (80,28,328536)
13 (9,5,300)
14 (2,1,21)
15 (15,11,300)
16 (16,12,300)
17 (81,29,328536)
18 (14,10,300)
19 (11,7,300)
20 (12,8,300)
21 (1,0,21)
22 (6,2,72)
23 (83,31,328536)
24 (8,4,300)
25 (73,21,328536)
26 (22,5,661)
27 (79,27,328536)
28 (7572,2962,123130640068522377168864228132316865867184046004226894)

Note the large number of steps and maximum in the last one. Somewhat more surprising are subsequent records. Do all integer starts eventually reach zero? Tom Duff has provided a list of the progressive record number of steps to get to zero:

1: 1
2: 2
3: 11
4: 12
9: 13
11: 19
12: 80
17: 81
23: 83
28: 7572
33: 7573
74: 7574
86: 7578
180: 7580
227: 664475
350: 664882
821: 3180929
3822: 3180930
4187: 3180931
5561: 3181981
6380: 3181988
6398: 3182002
22174: 3182226
22246: 120796790
26494: 556068798
34859: 556068799
49827: 556068871
70772: 556068872
103721: 572086553
104282: 572086610
204953: 1246707529
213884: 1246707552
225095: 1246707555
407354: 1246707602
425720: 87037147316

Update: Tim Peters has been working on extending the outcome of start numbers up to ten million. Here are a few results from his ongoing effort:

1671887:  128018188027
6264400: >383000000000
6524469: >327000000000
7011851:  225197172159
7404616: >370000000000

No comments:

Post a Comment