![]() | ![]() |
Suppose we define f(x) in the following way, for positive integers x:
f(x)={x/2 if x is even3x+1 if x is odd
Construct the sequence of values a0,a1,a2,... so that a0=n and ai+1=f(ai). Verify that this sequence ultimately gets stuck in the loop 4, 2, 1, 4, 2, 1, ... for the following values of n:
Find the sequence described in part (a) for other values of n. What do you notice?
Suppose we use L(n) to denote the position where 1 first occurs in the sequence so generated and starting with n. Show that if n=8k+4, then L(n)=L(n+1).
Show that if n=128k+28, then L(n)=L(n+1)=L(n+2).
See below...
21 → 64 → 32 → 16 → 8 → 4 → 2 → 1 ...
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 ...
31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → 91 → 274 → 137 → 412 → 206 → 103 → 310 → 155 → 466 → 233 → 700 → 350 → 175 → 526 → 263 → 790 → 395 → 1186 → 593 → 1780 → 890 → 445 → 1336 → 668 → 334 → 167 → 502 → 251 → 754 → 377 → 1132 → 566 → 283 → 850 → 425 → 1276 → 638 → 319 → 958 → 479 → 1438 → 719 → 2158 → 1079 → 3238 → 1619 → 4858 → 2429 → 7288 → 3644 → 1822 → 911 → 2734 → 1367 → 4102 → 2051 → 6154 → 3077 → 9232 → 4616 → 2308 → 1154 → 577 → 1732 → 866 → 433 → 1300 → 650 → 325 → 976 → 488 → 244 → 122 → 61 → 184 → 92 → 46 → 23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 ...
Every number seems to generate a sequence that gets stuck in the loop 4, 2, 1, ...
Consider the first 4 iterations:
8k+4→4k+2→2k+1→6k+4
8k+5→24k+16→12k+8→6k+4
From there on, the sequences are identical, and thus get stuck in the loop 4,2,1 at the same time.
Consider the first 4 iterations:
128k+28→64k+14→32k+7→96k+22
128k+29→384k+88→192k+44→96k+22
128k+30→64k+15→192k+46→96k+23
Notice, the first two sequences have merged. Now consider the next 7 iterations:
96k+22→48k+11→144k+34→72k+17→
216k+52→108k+26→54k+13→162k+40
96k+23→288k+70→144k+35→432k+106→
216k+53→648k+160→324k+80→162k+40
So now, all three sequences have merged, which implies they will get stuck in the loop 4,2,1 at the same time.