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 (always even) 4k+3: (3*(4k+3)+1)/2=(12k+10)/2=6k+5 (always odd)
We see that 4k+3 meets the requirements. This covers half of the odd numbers, the remainder are of the form 4k+1, which we have seen can generate odd or even results. We can partition 4k+1 into two more sets by replacing the original 'k' with either 2k or 2k+1, and when we expand we get two possibilities:
k{RA}2k, 4k+1{RA}8k+1: (3*(8k+1)+1)/4=(24+4)/4=6k+1 (always odd)
k{RA}2k+1, 4k+1{RA}8k+5: (3*(4k+5)+1)/4=(24+16)/4=6k+4 (can be odd or 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]. 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,3) | (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,3) | (1,1,5) | [(5*2^A-1)/3, 5]
The coefficient of 'k' is 2^[(a+1)] and for the 'b' values, b(a+2)=4*b(a)+1, b(1)=3, b(2)=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+40{RA}3*2^3+20{RA}3*2^2+10{RA}3*2^1+5}
All these numbers are of the form 3^n*2^m+b, which I shall represent by the ordered triple (n,m,b). Now the above sequence becomes
(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, so (0,4,13){RA}(1,4,40){RA}(1,3,20){RA}(1,2,10){RA}(1,1,5), effectively mapping 16k+13 to 6k+5. In this example, when k ranges from 0 to 5 we get:
k = 0: S(13) = [13, 40, 20, 10, 5] ≡ [13, 5] k = 1: S(13+16) = [29, 88, 44, 22, 11] ≡ [29, 11] k = 2: S(13+32) = [45, 136, 68, 34, 17] ≡ [45, 17] k = 3: S(13+48) = [61, 184, 92, 46, 23] ≡ [61, 23] k = 4: S(13+64) = [77, 232, 116, 58, 29] ≡ [77, 29] k = 5: S(13+80) = [93, 280, 140, 70, 35] ≡ [93, 35] ⋮
(0,4,13) generates all the A‐Lists that start with [3], but after that they all go their separate ways:
k = 0: S(13) = [3, 4] k = 1: S(39) = [3, 1, 2, 3, 4] k = 2: S(45) = [3, 2, 3, 4] k = 3: S(61) = [3, 1, 1, 5, 4] k = 4: S(77) = [3, 3, 1, 2, 3, 4] k = 5: S(93) = [3, 1, 5, 4] k = 6: S(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: S(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: S(141) = [3, 5, 4] ⋮
If we can find a way of prefixing atoms to an existing list we can build up lists of arbitrary length. For instance [a¬1]+[a¬2,a¬3]{RA}[a¬1,a¬2,a¬3]. We want to do this using the generic values. 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+b¬2*2^[n] }
{IMP}3b¬1 ∈ { 2^[(n+a2)]*x+b¬2*2^[n]+1 }
{IMP}b¬1 ∈ { (2^[(n+a2)]*x+b¬2*2^[n]+1)/3 }
{IMP}b¬1 = f(x¬0)/3 + 2^[(n+a2)]*k
For b¬1 to be an integer we need to find x such that 2^[(n+a2)]*x+b¬2*2^[n]+1 is divisible by 3. The resulting GV is (0, n+a¬2, f(x¬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, a¬2=4, b¬2=13 and b¬1 is our unknown
(3b¬1+1)/2^[n] ∈ { 2^[a2]*x+b¬2 }
{EQV}(3b¬1+1)/4 ∈ { 16*x+13 }
{IMP}(3b¬1+1) ∈ { 64*x+b¬2*4 }
{IMP}3b¬1 ∈ { 64*x+b¬2*4-1 }
{IMP}b¬1 ∈ { (64*x+b¬2*4-1)/3 }
{IMP}b¬1 ∈ { (64*x+b¬2*4-1)/3 } {EQV} { 51/3, 115/3, 179/3, 243/3, 307/3, 371/3, ... }
{IMP}b¬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]*k¬[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,b¬0){RA}(n,1,b¬e), but I suspect the only way to calculate b¬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 (b¬0). If the list contains a smaller 'b' value then b¬0 can't be the smallest divergent b.
If the list contains a second 'b' value equal to b¬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, b¬1/b¬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}b¬1/b¬0 (k=0)|{h}b¬1/b¬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}b¬2/b¬0 (k=0)|{h}b¬2/b¬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}b¬n/b¬0 (k=0)|{h}b¬n/b¬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 b¬0 values, for [1]^n, b¬0(n)=2*b¬0(n-1)-1, and for [1,2], b¬0(n)=8*b¬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