We have seen elsewhere on this site that if we replace the standard 3x+1 iteration with one where x{RA}(3*x+1)/2^a we can generate sequences of odd numbers separated by 'a' even numbers. This exactly matches the original sequence, it just collapses the sequence of even numbers into the single value 'a'. For instance if a=4 we might get the mapping 325{RA}61, which expands to the sequence 325{RA}976{RA}488{RA}244{RA}122{RA}61.
Elsewhere on this site I have defined A‐Lists as the set of 'a' values that arise when a starting value 'b' is iterated using the 3x+1 algorithm. Each 'b' value generates a unique A‐List, which if the conjecture is 2, ends with an infinite sequence of '2's. Usually I chop these off, assuming that the iteration ends when the first '1' is encountered.
If though, if we start with a finite A‐List, we can derive an infinite set of 'b' values that will generate this list. These 'b' values can be encapsulated in a simple formula which I will call a "generic value". On the rest of this page we will start with the generic values for single member A‐Lists, which I shall call "atoms" and build up from there to provide an algorithm for the generic value corresponding to any A‐List.
In the introduction we saw that the number 325 is an example of a 'b' value that generates the A‐List [4]. This is not the smallest such value, if you experiment you will see that this is '5'; 5{RA}16{RA}8{RA}4{RA}2{RA}1. Considering the 1 member A‐Lists, [1], [2], [3], etc. Ignoring the even steps [1] maps x to (3x+1)/2. We have the additional constraint that the result must be odd (otherwise we could continue dividing by 2). If we try some candidate expressions (2k+1), (4k+1), (4k+3), where 'k' is an integer, we see
2k+1: (3*(2k+1)+1)/2=(6k+4)/2=3k+2 (can be odd or even) 4k+1: (3*(4k+1)+1)/2=(12k+4)/2=6k+2 (even) 4k+3: (3*(4k+3)+1)/2=(12k+10)/2=6k+5 (odd)
We see that 4k+3 meets the requirements. This covers half of the odd numbers. Conversely, 4k+1 always generates an even result. We can partition 4k+1 into two subsets by replacing the original 'k' with either 2k or 2k+1, giving 4(2k)+1 and 4(2k+1)+1, equivalent to 8k+1 and 8k+5.
8k+1: (3*(8k+1)+1)/4=(24+4)/4=6k+1 (odd) 8k+5: (3*(4k+5)+1)/4=(24+16)/4=6k+4 (even)
Where 8k+1 corresponds to [2], which covers half of the remaining numbers. This leaves one quarter, still unassigned, in the 8k+5 bucket. Substituting 2k and 2k+1 into 8K+5 gives us two possibilities for [3], 8(2k)+5 and 8(2k+1)+5, which become 16k+5 and 16k+13. (3*(16k+5)+1)/8=6k+4, which is even, so 16k+13 is the next entry in out sequence. Continuing this process we can generate the table:
{H}A‐List |{h}Start |{h}End |{h}GV¬[start] |{h}GV¬[end] |{h}B‐List {H}{lft}[1] | 4k+3 | 6k+5 | (0,2,3) | (1,1,5) | [3, 5] {H}{lft}[2] | 8k+1 | 6k+1 | (0,3,1) | (1,1,1) | [2, 1] {H}{lft}[3] | 16k+13 | 6k+5 | (0,4,13) | (1,1,5) | [13, 5] {H}{lft}[4] | 32k+5 | 6k+1 | (0,5,5) | (1,1,1) | [5, 1] {H}{lft}[5] | 64k+53 | 6k+5 | (0,6,53) | (1,1,5) | [53, 5] {H}{lft}[6] | 128k+21 | 6k+1 | (0,7,21) | (1,1,1) | [21, 1] {H}{lft}[7] | 256k+213 | 6k+5 | (0,8,213) | (1,1,5) | [213, 5] {H}{lft}…|{5} {H}{lft}[Even] | 2^[(A+1)]*k+(2^A-1)/3 | 6k+1 | (0,A+1,b¬n) | (1,1,1) | [(2^A-1)/3, 1] {H}{lft}[Odd] | 2^[(A+1)]*k+(5*2^A-1)/3 | 6k+5 | (0,A+1,b¬n) | (1,1,5) | [(5*2^A-1)/3, 5]
The coefficient of 'k' is 2^[(a+1)] and for the 'b' values, b¬1=3, b¬2=1, b¬[(a+2)]=4*b¬a+1, . You can see the values for larger 'a' using this widget: Enter a value and click "go".
Value: Result = ___
If we iterate one of the expressions above, say [3], we get the sequence
2^4*k+13{RA}3*2^4*k+40{RA}3*2^3*k+20{RA}3*2^2*k+10{RA}3*2^1*k+5},
k=0: 13{RA}40{RA}20{RA}10{RA}5,
k=1: 29{RA}88{RA}44{RA}22{RA}11,
k=2: 45{RA}136{RA}68{RA}34{RA}17.
k=3: 61{RA}184{RA}92{RA}46{RA}23,
⋮
All these numbers are of the form 3^n*2^m*k+b. We now have a whole family of sequences that only differ by the value of k, which I shall represent by the ordered triple (n,m,b) and call a generic value. This allows us to collapse the infinite set of sequences above to the single generic value sequence
(0,4,13){RA}(1,4,40){RA}(1,3,20){RA}(1,2,10){RA}(1,1,5)
The rules for iterating a particular generic value (GV) are:
'b' is odd: (n, m, b){RA}(n+1, m, 3b+1)
'b' is even: (n,m,b){RA}(n, m-1, b/2)
We stop the iteration when the 'm' value becomes 1. In this example, when k ranges from 0 to 5 we get:
k=0: S(0+13) → [13, 40,20, 10, 5] ≡ [13,5] k=1: S(16+13) → [29, 88,44, 22,11] ≡ [29,11] k=2: S(2*16+13) → [45,136,68, 34,17] ≡ [45,17] k=3: S(3*16+13) → [61,184,92, 46,23] ≡ [61,23] k=4: S(4*16+13) → [77,232,116,58,29] ≡ [77,29] k=5: S(5*16+13) → [93,280,140,70,35] ≡ [93,35] ⋮
The valueos of b¬2/b¬1 approach 3/8, 3^n/2^[m-1]. m=Σa and n is the length of the A‐list.
The sequence for k¬i will be the sequence for k¬0 plus [16k¬i, 8k¬i, 4k¬i, 2k¬i, k¬i].
All sequences generated from (0,4,13) start [3, …], but after that they all go their separate ways:
k=0: 13 → [3,4] k=1: 39 → [3,1,2,3,4] k=2: 45 → [3,2,3,4] k=3: 61 → [3,1,1,5,4] k=4: 77 → [3,3,1,2,3,4] k=5: 93 → [3,1,5,4] k=6: 109 → [3,2,1,1,1,1,2,2,1,2,1,1,2,1,1,1,2,3,1,1,2,1,2,1,1,1,1,1,3,1,1,1,4,2,2,4,3,1,1,5,4] k=7: 125 → [3,1,1,1,2,2,1,2,1,1,2,1,1,1,2,3,1,1,2,1,2,1,1,1,1,1,3,1,1,1,4,2,2,4,3,1,1,5,4] k=8: 141 → [3,5,4] ⋮
A one member A-list, [a¬1] encapsulates all the transformations of the form x{RA}(3x+1)/2^[a1]. For this transformation to generate an odd integer, x must be of the form 2^[(a1+1)]*k+b¬[a1]. b¬a values have been listed above and start [3,1,13,5,53,21,...]. The result of this operation will be 6k+1 for even numbers and 6k+5 for odd ones.
To extend the A‐list to [a¬1,a¬2] the output of [a¬1] (6k=c) needs to fit seamlessly into the input of [a2], so 6k+c needs to be matched with a number of the form 2^[(a2+1)]+b¬[a2]. We need to find the smallest k where 6k+c mod 2^[(a2+1)] = b¬[a2].
As an example, let's try to find sequences starting with [3,6], as none of these appeared as examples when we were just looking at [3]. [3] maps numbers of the form 16k+13 to 6k+5 and [6] maps 128k¬2+21 to 6k¬2+1, so taking c to be 5 we need 6k+5 mod 128k¬2=21
(6k+5) mod 128k¬2=21
k¬2=0 k¬2=1
{IMP}6k mod 128=16 6k mod 256=16
{IMP}3k mod 64=8 3k mod 128=8
{IMP}3k=64n+8 3k=128n+8
{IMP}64n+8 mod 3=0 128n+8 mod 3=0
{IMP}n+2 mod 3=0 2n+2 mod 3=0
{IMP}n=1 n=2
{IMP}3k=72 3k=264
{IMP}k=24 k=88
{IMP}b=16*24+13=397 b=16*88+13=1421
1421-397=1024=2^[10], so x¬k=2^[10]*k+397, giving us b¬[[3,6]] = 397. The exponent 'a' in the 2^a*k term will always be 1+Σa¬i.
Generically, starting with [a¬1]{EQV}2^[(a1+1)]+b¬[a¬1] and [a¬2]{EQV}2^[(a2+1)]+b¬[a¬2].
(6k+c) mod 2^[a2+1]=b¬[a2]
{IMP}6k mod 2^[(a2+1)]=b¬[a2]-c
{IMP}3k mod 2^[a2]=(b¬[a2]-c)/2
{IMP}3k=2^[a2]*n+(b¬[a2]-c)/2
{IMP}(2^[a2]*n+(b¬[a2]-c)/2) mod 3=0
{IMP}2^[a2]*n mod 3=−((b¬[a2]-c)/2) mod 3
As (2^x)^2=1 mod 3, we can multiply both side by (2^[a2]) to get
n mod 3=−(2^[a2]*((b¬[a2]-c)/2)) mod 3
{IMP}k=2^[a2]*n+(b¬[a2]-c)/2)/3
{IMP}b¬[a1,a2]=2^[(a1+1)]*k+b¬[a¬1]
Choose two atoms A1: A2:
?
Test:
?
We can do this in two ways, first create a 2 member A‐List as we did in the previous section, then add a third atom, either at the beginning (prefix) or at the end (postfix). The result should be the same either way. We will make use of 2^[Φ(3^n)] mod 3^n=1, so 2^m mod 3^n = 2^[m mod Φ(3^n)] mod 3^n. Φ(3^n)=2*3^[n-1]{IMP}Φ(3^2)=6{IMP}2^m mod 9 = 2^[(m mod 6)] mod 9. Let's work through an example:
A1: A2: A3:
?
Test
?
We can represent an arbitrary A‐list [a¬1,a¬2,…a¬n] by the generic value (0,1+m, b¬[a¬1,a¬2,…a¬n]), where m=Σa. Unfortunately there is no easy way to calculate the 'b' value, it has to be built up by combining the sub‐lists. Applying the iteration will end with the generic value (1,n,c¬[a¬1,a¬2,…a¬n]). For clarity let's replace b¬[a¬1,a¬2,…a¬n] by b¬1 and c¬[a¬1,a¬2,…a¬n] by c¬1. Then we introduce a second A‐list with the generic value (0,1+m¬2, b¬2[a¬1,a¬2,…a¬n]). Now we have to solve:
(0,1+m¬1,b¬1){RA}(n¬1,1,c¬1){EQV}(0,1+m¬2,b¬2), or
2^[(1+m1)]*k¬1+b¬1{RA}2x3^[n1]*k¬1+c¬1{EQV}2^[(1+m2)]*k¬2+b¬2
We can attack this in the same ways as the simpler atomic case earlier:
2x3^[n1]*k¬1+c¬1{EQV}2^[(1+m2)]*k¬2+b¬2
Setting k¬2 to 0 will give us the smallest solution. Note: b and c are odd, so b-c is even.
2x3^[n1]*k¬1+c¬1{EQV}2^[(1+m2)]+b¬2
{IMP}2x3^[n1]*k¬1 mod 2^[(1+m2)]=b¬2-c¬1
{IMP}3^[n1]*k¬1 mod 2^[m2]=(b¬2-c¬1)/2
{IMP}3^[n1]*k¬1=(2^[a2]-1)*n+(b¬2-c¬1)/2
{IMP}((2^[a2]-1)*n+(b¬[a2]-c)/2) mod 3=0
{IMP}n{MO}[0,1,2]
{IMP}k=(2^[a2]-1)*n+(b¬[a2]-c)/2)/3
{IMP}b¬[a1,a2]=2^[(a1+1)]*k+b¬[a¬1]
To build A‐lists of arbitrary length we need to find a way of prefixing atoms to an existing list. For instance [a¬1]+[a¬2,a¬3]{RA}[a¬1,a¬2,a¬3]. We want to do this in the generic value space. The iteration maps the b value in an atom like [n] to (3b+1)/2^n. To join this to an existing list (0,a¬2,b¬2) we need to find 'x' values such that
(3b¬1+1)/2^[n] ∈ { 2^[a2]*x+b¬2 }, x ∈ { 0-∞ }
{IMP}(3b¬1+1) ∈ { 2^[(n+a2)]*x+b2*2^[n] }
{IMP}3bA¬1 ∈ { 2^[(n+a2)]*x+bA¬2*2^[n]+1 }
{IMP}bA¬1 ∈ { (2^[(n+a2)]*x+bA¬2*2^[n]+1)/3 }
{IMP}bA¬1 = f(xA¬0)/3 + 2^[(n+a2)]*k
For bA¬1 to be an integer we need to find x such that 2^[(n+a2)]*x+bA¬2*2^[n]+1 is divisible by 3. The resulting GV is (0, n+aA¬2, f(xA¬0)/3). For example, if we want to create the generic value for [2,3] we first need the GV for [3], which is (0,4,13). The above becomes
n=2, aA¬2=4, bA¬2=13 and bA¬1 is our unknown
(3bA¬1+1)/2^[n] ∈ { 2^[a2]*x+bA¬2 }
{EQV}(3bA¬1+1)/4 ∈ { 16*x+13 }
{IMP}(3bA¬1+1) ∈ { 64*x+bA¬2*4 }
{IMP}3bA¬1 ∈ { 64*x+bA¬2*4-1 }
{IMP}bA¬1 ∈ { (64*x+bA¬2*4-1)/3 }
{IMP}bA¬1 ∈ { (64*x+bA¬2*4-1)/3 } {EQV} { 51/3, 115/3, 179/3, 243/3, 307/3, 371/3, ... }
{IMP}bA¬1=17+64*k.
And the resultant GV is (0, 6, 17). We can see this in action in the widget below. "Reset" will start a new sequence with the ingeger in the text box, "Insert" will then add the value in the text box to the beginning of the list. To see [2,3] enter 3 in the box and press reset, then 2 in the box and press insert.
Value:
Result
Can we combine two short lists and derive the generator of a longer one, for instance [2] + [11] = [2,11]. We would expect the generator to be of the form (0,14,B), where B is the value we are trying to derive. If we apply the [2] operation we arrive at (1,12,(3*B)/4). We need to match this with the generator of [11]: (0,12,3413). We can ignore the power of three and just solve:
(3b+1)/4 = 2^[12]*kA¬[11]+3413
{IMP}(3b+1)/4 ∈ [3413, 7509, 11605, 15701, 19797, ...]
{IMP}3b ∈ 13651, 30035, 46419, 62803, 79187, ...]
{IMP}b ∈ [x, x, 15473, x, x, 31857, ...]
Where 'x' indicates that the solution isn't an integer. Generally there will always be a solution among the first three potential values. So the generator for [2,11] is (0,14,15473). The first 2 sequences are:
S(15473) = 15473, [46420, 23210], 11605, [34816, 17408, 8704, 4352, 2176, 1088, 544, 272, 136, 68, 34], 17, ... S(31857) = 31857, [95572, 47786], 23893, [71680, 35840, 17920, 8960, 4480, 2240, 1120, 560, 280, 140, 70], 35,...
I've bracketed the even runs corresponding to [2] and [11].
When searching for interesting A‐Lists it would proabably be more useful to be able to append additional 'a' values to the end of the list. To do this we need to match the end of the sequence with the GV of the atom. For instances if we want to calculate [1,1,1,1] + [3] we first need to iterate the GV defining [1,1,1,1}, which is (0, 5, 31), giving (0,5,31){RA}(1,5,94){RA}(1,4,47){RA}(2,4,142){RA}(2,3,71){RA}(3,3,214){RA}(3,2,107){RA}(4,2,322){RA}(4,1,161). The n and m terms are easy to calculate, (0,m,bA¬0){RA}(n,1,bA¬e), but I suspect the only way to calculate bA¬e is to iterate the sequence, though it will be coprime to 2 and 3 and less that 2*3^n. Series can start on a multiple of three, but only when 'k' is 0, but can't end on one.
To identify the GV for [1,1,1,1,3] we need to find the smallest (4,1,161) that is consistent with (0,4,13).
2*3^4*k+161=2^4*x+13
{IMP}2*3^4*k+161%2^4=13
2*3^4*k+161%2^4=[1,3,5,7,9,11,13,15,1,3,…]
{IMP}k=6+8n
Replacing k in (0,5,31) with 8k+6 we get 2^5*(2^3*k+6)+31=2^8*k+6*2^5+31=2^8*k+223{EQV}(0,8,223), which generates the A‐List [1,1,1,1,3] as required:
(0,8,223){RA}(1,8,670}{RA}(1,7,335){RA}(2,7,1006){RA}(2,6,503}{RA}(3,6,1510){RA}(3,5,755){RA}
(4,5,2286){RA}(4,4,1133){RA}(5,4,3400){RA}(5,3,1700){RA}(5,2,850){RA}(5,1,425)
The first few examples are:
k=0: S(223) = [223, 670, 335, 1006, 503, 1510, 755, 2266, 1133, 3400, 1700, 850, 425] k=1: S(479) = [479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911] k=2: S(735) = [735, 2206, 1103, 3310, 1655, 4966, 2483, 7450, 3725, 11176, 5588, 2794, 1397] ⋮
The following controls will allow you to use the above algorithm to append additional terms to the end of an A‐List. "Reset" will start a new sequence with the value in the box, "Append" will add the value in the text box to the end of the current list:
Value:
Result
Or go directly from the A‐List to the generic value:
A‐List: . Repeat the list times.
Result
If we start with the assumption that there is a smallest integer that diverges to infinity then that must be a generic value that generates an infinite B‐List where all the 'b' values are greater than the first one (bA¬0). If the list contains a smaller 'b' value then bA¬0 can't be the smallest divergent b.
If the list contains a second 'b' value equal to bA¬0 we have found a loop.
From the nature of generic values, if we find one divergent series we have found an infinite number, as every 'k' value will generate a sequence with the same A‐List structure. Unfortunately this doesn't apply to loops, the A‐List [2] generates the B‐List [1,1], which is the loop [1,4,2,1], but when 'k' is greater than 0 the values are [8k+1, 24k+4, 12k+2, 6k+1].
So we need to search for A‐Lists where all the terms are greater than (or equal to) the first one. If we look at the Atoms above, we can see that [1] is the only 1 member A‐List that satisfies this requirement. So any number that diverges to infinity will be of the form 4k+3. There is one exception here, [2], when k=0, generates the B-List [1,4,2,1] loop. All other k values generate a sequence that gets smaller, bA¬1/bA¬0 converges on 3/4 as k approaches infinity.
Starting with [1] we can try appending the various atoms:
{H}A‐List |{h}Start |{h}End | {h}B‐List |{h}bA¬1/bA¬0 (k=0)|{h}bA¬1/bA¬0 (k=∞)|{h}OK {H}[1,1] | 8k+7 | 18k+17 | 7, 11, 17 | 17/7 | 9/4 | Yes {good} {H}[1,2] | 16k+11 | 18k+13 | 11, 17, 13 | 13/11 | 9/8 | Yes {good} {H}[1,3] | 32k+19 | 18k+11 | 19, 29, 11 | 11/19 | 9/16 | No {bad}
We can't start a divergent sequence with [1,3], [1,4] or any larger value. Let's examine a few three member lists:
We have a choice of [1,1] and [1,2] to extend.
{H}A‐List |{h}Start |{h}End | {h}B‐List |{h}bA¬2/bA¬0 (k=0)|{h}bA¬2/bA¬0 (k=∞)|{h}OK {H}[1,1,1] | 16k+15 | 54k+53 | 15, 23, 35, 53 | 53/15 | 27/8 | Yes {good} {H}[1,1,2] | 32k+7 | 54k+13 | 7, 11, 17, 13 | 13/7 | 27/16 | Yes {good} {H}[1,2,1] | 32k+27 | 54k+47 | 27, 41, 31, 47 | 47/27 | 27/16 | Yes {good} {H}[1,2,2] | 64k+43 | 54k+37 | 43, 65, 49, 37 | 37/43 | 27/32 | No {bad} {H}[1,1,3] | 64k+55 | 54k+47 | 55, 83, 125, 47 | 47/55 | 27/32 | No {bad}
The viable lists are those where 3^n>2^m, though it's possible that in some cases a list might be viable for small k even though it isn't in the limit.
By extending the sequence [1,1,1,...] we can get arbitrary large ratios between the end and start values.
{h}A‐List|{h}start|{h}end|{h}end/start {h}{lft}[1] | 7 | 17 | 17/7=2.42857 {h}{lft}[1]^2 | 15 | 53 | 53/15=3.53333 {h}{lft}[1]^3 | 31 | 161 | 161/31=5.19355 {h}{lft}[1]^4 | 63 | 485 | 485/63=7.69841
We are using [list]^n to represent n repetitions of [list], so [1,2]^4{EQV}[1,2,1,2,1,2,1,2]. How do powers of [1,2] behave?
{H}A‐List |{h}Start |{h}End | {h}B‐List |{h}bA¬n/bA¬0 (k=0)|{h}bA¬n/bA¬0 (k=∞) {H}{lft}[1,2] | (0,4,11) | (2,1,13) | 11, 17, 13 | 13/11 | 9/8 {H}{lft}[1,2]^2 | (0,7,123) | (4,1,157) | 123, 185, 139, 209, 157 | 157/123 | 81/64 {H}{lft}[1,2]^3 | (0,10,1019) | (6,1,1453) | 1019, 1529, 1147, 1721, 1291, 1937, 1453 | 1453/1019 | 729/512 {H}{lft}[1,2]^4 | (0,13,8187) | (8,1,13117) | 8187, 12281, 9211, 13817, 10363, 15545, 11659, 17489, 13117 | 13117/8187 | 6561/4096
So far it looks like repeated motifs generate predictable bA¬0 values, for [1]^n, bA¬0(n)=2*bA¬0(n-1)-1, and for [1,2], bA¬0(n)=8*bA¬0(n-1)+35 (n>0). But no such simple pattern appears for [1,2,1]^n.
{h}A‐List |{h}Generic value |{h}Expression |{h}B‐List |{h} Limit {h}{lft}[1,2,1] | (0,5,27) | 2^5*k+27 | 27, 41, 31, 47 | (3,1,47) {h}{lft}[1,2,1]^2 | (0,9,91) | 2^9*k+91 | 91, 137, 103, 155, 233, 175, 263 | (6,1,263) {h}{lft}[1,2,1]^3 | (0,13,5211) | 2^[13]*k+5211 | 5211, 7817, 5863, 8795, 13193, 9895, 14843, 22265, 16699, 25049 | (9,1,25049) {h}{lft}[1,2,1]^4 | (0,17,95323) | 2^[17]*k+95323 | 95323, 142985, 107239, 160859, 241289, 180967, 271451, 407177, 305383, 458075, 687113, 515335, 773003 | (12,1,773003)
Here the start values are 2^[3n+4]-5, and the ends 2*3^[2n+2]-5, where n is the repeat count, starting at 0. It looks like repeating lists always follow a pattern, To find a repeating pattern that diverges we need to find one where the solution to the join is k=0.
"Systematic" tests all the potential candidates of a particular length before moving onto the longer lists, "Smallest B" builds on lists that have already been ound with small 'B' values.
Search depth: Search Mode: Display Mode:
___
This will search for b-values that generate long lists of growing values (all b >= b0) or have the largest growth (max/start)
___
___
(c) John Whitehouse 2011 - 2023