The problem is very simple to state, and the actions are very simple to perform, but the question is, given any starting integer x > 0, will the sequence generated end with the integer 1 in a finite number of steps?
Here are the sequences generated for the first few integers:
1: 1
2: 2 1
3: 3 10 5 16 8 4 2 1
4: 4 2 1
5: 5 16 8 4 2 1
6: 6 3 10 5 16 8 4 2 1
7: 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
8: 8 4 2 1
9: 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
10: 10 5 16 8 4 2 1
11: 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
12: 12 6 3 10 5 16 8 4 2 1
13: 13 40 20 10 5 16 8 4 2 1
14: 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
15: 15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
16: 16 8 4 2 1
17: 17 52 26 13 40 20 10 5 16 8 4 2 1
18: 18 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
19: 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
20: 20 10 5 16 8 4 2 1
21: 21 64 32 16 8 4 2 1
22: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
23: 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
24: 24 12 6 3 10 5 16 8 4 2 1
25: 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
26: 26 13 40 20 10 5 16 8 4 2 1
27: 27 82 41 124 62 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
28: 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
29: 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
30: 30 15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
31: 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
32: 32 16 8 4 2 1
33: 33 100 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
34: 34 17 52 26 13 40 20 10 5 16 8 4 2 1
35: 35 106 53 160 80 40 20 10 5 16 8 4 2 1
36: 36 18 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
37: 37 112 56 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
38: 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
39: 39 118 59 178 89 268 134 67 202 101 304 152 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
40: 40 20 10 5 16 8 4 2 1
41: 41 124 62 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
42: 42 21 64 32 16 8 4 2 1
43: 43 130 65 196 98 49 148 74 37 112 56 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
44: 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
45: 45 136 68 34 17 52 26 13 40 20 10 5 16 8 4 2 1
46: 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
47: 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
48: 48 24 12 6 3 10 5 16 8 4 2 1
49: 49 148 74 37 112 56 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
50: 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
51: 51 154 77 232 116 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
52: 52 26 13 40 20 10 5 16 8 4 2 1
53: 53 160 80 40 20 10 5 16 8 4 2 1
54: 54 27 82 41 124 62 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
55: 55 166 83 250 125 376 188 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
56: 56 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
57: 57 172 86 43 130 65 196 98 49 148 74 37 112 56 28 14 7 22 11 34 17 52 26 13 40
20 10 5 16 8 4 2 1
58: 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
59: 59 178 89 268 134 67 202 101 304 152 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40
20 10 5 16 8 4 2 1
60: 60 30 15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
Here is, perhaps, a neater way of showing it: (under construction)
1: 1
2: 2 [1]
3: 3 10 5 16 8 4 [2]
4: [4]
5: 5 [16]
6: 6 [3]
7: 7 22 11 34 17 52 26 13 40 20 [10]
8: [8]
9: 9 28 14 [7]
10: [10]
11: [11]
12: 12 [6]
13: [13]
14: [14]
15: 15 46 23 70 35 106 53 160 80 [40]
16: [16]
17: [17]
18: 18 [9]
19: 19 58 29 88 44 [22]
20: [20]
21: 21 64 32 [16]
22: [22]
23: [23]
24: 24 [12]
25: 25 76 38 [19]
26: [26]
27: 27 82 41 124 62 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]
28: [28]
29: [29]
30: 30 [15]
31: [31]
32: [32]
33: 33 100 50 [25]
34: 34 [17]
35: [35]
36: 36 [18]
37: 37 112 56 [28]
38: [38]
39: 39 118 59 178 89 268 134 67 201 604 302 151 454 227 682 341 1024 512 256 128 [64]
40: [40]
41: [41]
42: 42 [21]
43: 43 130 65 196 98 49 148 74 [37]
44: [44]
45: 45 136 68 [34]
46: [46]
47: [47]
Depth
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
- 3 - 6 - 12 - 24 - 48 - 96 - 192 - 384 - 768 - 1536
- 5 - 10 |
| | - 7
| | - 11 - 22 |
| | | - 44
| | - 17 - 34 |
| | | | - 45
| | | - 68 - 136 |
| | | - 272
| | - 13 - 26 - 52 |
| | | | - 69 - 138 - 276
| | | - 104 - 208 |
| | | | - 277
| | | - 416 - 832 |
| | | - 1664
| - 20 - 40 |
| | - 23 - 46
| | - 35 - 70 |
| | | - 140 - 280
| | - 53 - 106 |
| | | | - 141 - 282
| | | - 212 - 424 |
| | | - 848 - 1696
| - 80 - 160 |
| | - 213 - 426 - 852 - 1704
| - 320 - 640 |
| | - 853 - 1706
| - 1280 - 2560 |
| - 5120 - 10240
1 - 2 - 4 - 8 - 16 |
| - 21 - 42 - 84 - 168 - 336 - 672 - 1344 - 2688 - 5376 - 10752
- 32 - 64 |
| - 75 - 150 - 300
| - 113 - 226 |
| | | - 301
| | - 452 - 904 |
| | - 1808
| - 85 - 170 - 340 |
| | | - 453 - 906 - 1812
| | - 680 - 1360 |
| | | - 1813
| | - 2720 - 5440 |
| | - 10880
- 128 - 256 |
| - 151 - 302
| - 227 - 454 |
| | - 908 - 1816
| - 341 - 682 |
| | | - 909 - 1818
| | - 1364 - 2728 |
| | - 5456 - 10912
- 512 - 1024 |
| - 1365 - 2730 - 5460 - 10920
- 2048 - 4096 |
| - 5461 - 10922
- 8192 - 16384 |
- 32768 - 65536
Here is another view of the same tree:
Depth
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
- 3 - 6 - 12 - 24 - 48 - 96 - 192 - 384 - 768 - 1536
|
| - 7
| |
| - 11 - 22 - 44
| |
| | - 45
| | |
| - 17 - 34 - 68 - 136 - 272
| |
| | - 69 - 138 - 276
| | |
| | | - 277
| | | |
| - 13 - 26 - 52 - 104 - 208 - 416 - 832 - 1664
| |
| | - 23 - 46
| | |
| | - 35 - 70 - 140 - 280
| | |
| | | - 141 - 282
| | | |
| | - 53 - 106 - 212 - 424 - 848 - 1696
| | |
| | | - 213 - 426 - 852 - 1704
| | | |
| | | | - 853 - 1706
| | | | |
- 5 - 10 - 20 - 40 - 80 - 160 - 320 - 640 - 1280 - 2560 - 5120 - 10240
|
| - 21 - 42 - 84 - 168 - 336 - 672 - 1344 - 2688 - 5376 - 10752
| |
| | - 75 - 150 - 300
| | |
| | | - 301
| | | |
| | - 113 - 226 - 452 - 904 - 1808
| | |
| | | - 453 - 906 - 1812
| | | |
| | | | - 1813
| | | | |
| | - 85 - 170 - 340 - 680 - 1360 - 2720 - 5440 - 10880
| | |
| | | - 151 - 302
| | | |
| | | - 227 - 454 - 908 - 1816
| | | |
| | | | - 909 - 1818
| | | | |
| | | - 341 - 682 - 1364 - 2728 - 5456 - 10912
| | | |
| | | | - 1365 - 2730 - 5460 - 10920
| | | | |
| | | | | - 5461 - 10922
| | | | | |
1 - 2 - 4 - 8 - 16 - 32 - 64 - 128 - 256 - 512 - 1024 - 2048 - 4096 - 8192 - 16384 - 32768 - 65536
Here is a simplified view. If a number is produced that is a multiple of 3, then function g will never be applied to any number in that number's subtree. All numbers generated in that subtree will simply be the sequence of the number multiplied by the successive powers of 2.
Depth
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
- 3 * 2 ^ i
|
| - 7
| |
| - 11 - 22 - 44
| |
| | - 45 * 2 ^ i
| | |
| - 17 - 34 - 68 - 136 - 272
| |
| | - 69 * 2 ^ i
| | |
| | | - 277
| | | |
| - 13 - 26 - 52 - 104 - 208 - 416 - 832 - 1664
| |
| | - 23 - 46
| | |
| | - 35 - 70 - 140 - 280
| | |
| | | - 141 * 2 ^ i
| | | |
| | - 53 - 106 - 212 - 424 - 848 - 1696
| | |
| | | - 213 * 2 ^ i
| | | |
| | | | - 853 - 1706
| | | | |
- 5 - 10 - 20 - 40 - 80 - 160 - 320 - 640 - 1280 - 2560 - 5120 - 10240
|
| - 21 * 2 ^ i
| |
| | - 75 * 2 ^ i
| | |
| | | - 301
| | | |
| | - 113 - 226 - 452 - 904 - 1808
| | |
| | | - 453 * 2 ^ i
| | | |
| | | | - 1813
| | | | |
| | - 85 - 170 - 340 - 680 - 1360 - 2720 - 5440 - 10880
| | |
| | | - 151 - 302
| | | |
| | | - 227 - 454 - 908 - 1816
| | | |
| | | | - 909 * 2 ^ i
| | | | |
| | | - 341 - 682 - 1364 - 2728 - 5456 - 10912
| | | |
| | | | - 1365 * 2 ^ i
| | | | |
| | | | | - 5461 - 10922
| | | | | |
1 - 2 - 4 - 8 - 16 - 32 - 64 - 128 - 256 - 512 - 1024 - 2048 - 4096 - 8192 - 16384 - 32768 - 65536
Now start with a number in the tree. You can find the sequence leading back to 1 by simply following the links back to the root of the tree. Even more interesting is since all splits occur in exactly two ways, a binary representation of each integer in the tree can be made by starting with a null string and by beginning at the 1 in the tree, following the path to the desired number and appending a "0" each time the (x - 1) / 3 route is folowed, and appending a "1" each time the x * 2 route is followed, so, the number 5 would have the representation "11110", because the route {2, 4, 8, 16, 5} is followed from 1. The number 80 would be represented as "111101111" because the route {2, 4, 8, 16, 5, 10, 20, 40, 80} is followed. When the problem is analyzed this way, the problem becomes:
Given f(x) = 2 * x and g(x) = (x - 1) / 3 , starting with initial x = 1, is it possible to produce any given integer using compositions of f and g on x, given that f may be applied to any integer greater than or equal to 1, and g may only be applied if the result of its application is an odd integer?
A very interesting thing I have noticed about the tree structure is that the two subtrees that split off from 16 (that 5 and 32 are the roots of) have identical structure until depth 16 is reached. At 22, there is a split in the upper subtree, but at the corresponding point in the lower subtree, at 150, there is no split.
Once a multiple of 3 is produced at a point in the tree, then the subtree starting at that number will never "split" again. That means that function f will be applied at every level in that subtree, and never g. If a number is divisible by 3, then the number minus 1 can never be divisible by 3, so g will not be applied. Each level afterwards will contain a multiple of 3 multiplied by a power of 2, and that result is divisible by 3, so g will never be applied to any number produced in a subtree starting with a multiple of 3.
The binary representations are a compact way of representing the compositions of f and g. The integer 5 represented as "11110" represents g(f(f(f(f(1))))). "0" represents an application of g and "1" represents an application of f, and the applications are applied in left-to-right order of appearance in the binary string.
Here are the binary representations of the first 16 integers:
1: (null string) 2: 1 3: 1111010 4: 11 5: 11110 6: 11110101 7: 1111011101101010 8: 111 9: 1111011101101010110 10: 111101 11: 11110111011010 12: 111101011 13: 111101110 14: 11110111011010101 15: 11110111110101010 16: 1111A few things become obvious about valid binary representations:
More to come as I have time...