Contents

Introduction

We can search for loops by deriving a single equation that combines a number of iterations, f(x), and then solve it for being equal to the original number: f(x)=x. For the unmodified sequence this is tricky as the equation has an 'if' condition in it, but if we just focus on the odd sequence it becomes clearer.

1−cycles

The next-odd iterator maps x→(3x+1)/2^[a1], where 'a¬1' is an integer (>0).

If we can find an odd integer solution to (3x+1)/2^[a1]=x we will have a loop that contains a single odd number and 'a¬1' even ones. This expression rearranges to (2^[a1]-3)*x=1. The only positive integer factorisation of 1 is 1*1, so both x and (2^[a1]-3) must be 1. The second condition leads to a¬1=2. The corresponding loop is [1,4,2,1], with 2 even and one odd members. This is the only possible loop with one odd member.

If we relax the positive integer requirement we get a second solution where a¬1=1 and x=−1. This is a loop with one odd and one even member [-1,-2,-1].

2−cycles

For 2−cycles the equation to solve is f(x)=(9x+2^[a1]+3)/2^[(a1+a2)]=x (where 'a¬1 and 'a¬2' are integers greater than 0).

This can be rearranged to x=(2^[a1]+3)/(2^[(a1+a2)]-9). To solve this we need to find integral values of a¬1 and a¬2 so that (2^[a1]+3) is an integer multiple of (2^[(a1+a2)]-9). The following table contains the calculations for some small values of a1 and a2 and shows that there are 4 solutions.

a1 a2 2a1+3 2(a1+a2)−9 x
1 1 5 −5 −1
1 2 5 −1 −5
1 3 5 7 5/7
2 1 7 −1 −7
2 2 7 7 1
2 3 7 23 7/23
3 1 11 7 11/7
3 2 11 23 11/23
4 1 19 23 19/23

Two of these solutions (−1 and 1) are repeats of the solutions we already found among the for 1−cycles, leaving only −5 and −7, which turn out to be two halves of the same solution, [−5, −14, −7, −20, −10, −5]. This cycle contains a¬1+a¬2=3 even numbers.

There are no solutions for larger 'a' values as the potential values of x are already less then one, and become even smaller as the 'a' values increase.

As we move to larger cycles we will always see that setting all the 'a' values to 1 will lead to x = −1 and setting them all to 2 will produce x = 1.

n−Cycles

For larger cycles we can calculate a series of equations of the form K*x=S, where:

K=2^[(a1+a2+…+an)]-3^n
S=3^[n-1]+3^[(n-2)]*2^[a1]+3^[(n-3)]*2^[(a1+a2)]+…+3^0*2^[(a1+a2+…+a(n-1))]

The 'a' values are the number of even numbers between successive odd values in the loop. We can define 'm' as the number of even values in the loop, giving

m=a¬1+a¬2+…+a¬n
K=2^m-3^n

We can do a quick search for solutions when n is 3 by constructing a table similar to the one we wrote for n = 2 in the previous section. This table, even for small a values is quite long, so I've reproduced it on a separate page for 'a' values up to m = 8. The only integer solutions are the ones we've found already, −1 and 1.

For positive solutions we can reject values where K is negative, which shows that any loops will always have more even values than odd ones, in fact m>n*log(3)/log(2). log(3)/log(2) is just under 1.585, so there will be at least 58% more even values than odd ones.

Loops in 3x+k

First, let us define the sets:

A¬1=[a¬1,a¬2,…,a¬n],
A¬2=[a¬2,…,a¬n,a¬1],
A¬3=[a¬3,…,a¬n,a¬1,a¬2],
etc.

Where A¬[(i+1)] is obtained by rotating the values in A¬i one place to the left. The resulting set of sets [A¬1, A¬2, …] has n members, as A¬[(n+1)] is the same as A¬1.

We can then define the set of S-values [s¬1, s¬2, …]=[S(A¬1), S(A¬2), …], where S(A¬i) is the value obtained by inserting the A-values in A¬i into the equation for S we introduced above.

We can now show that s¬2=(3*s¬1+K)/2^a1,

     s¬1=3^[(n-1)]+3^[(n-2)]*2^[a1]+3^[(n-3)]*2^[(a1+a2)]+…+2^[(a1+a2+…+a(n-1))]
    3s¬1=3^n+3^[(n-1)]*2^[a1]+3^[(n-2)]*2^[(a1+a2)]+…+3*2^[(a1+a2+…+a(n-1))]
3s¬1+K=3^[(n-1)]*2^[a1]+3^[(n-2)]*2^[(a1+a2)]+…+3*2^[(a1+a2+…+a(n-1))]+2^[(a1+a2+…+an)]
       =2^[a1]*(3^[(n-1)]+3^[(n-2)]*2^[a2]+…+3*2^[(a2+…+a(n-1))]+2^[(a2+…+an)]
       =2^[a1]*s¬2

⇒ (3s¬1+K)/2^[a1]=s¬2

so the set [s¬1, s¬2, …] represents an n−cycle in x→3x+K.

Clearly all systems of the form x→3x+(2^m-3^n) will have cycles, with 'n' odd and 'm' even values.

For all cases other than n = 1, m = 2 there will be multiple loops as we can construct multiple A-lists for every (m,n) pair. For m=2, n=1 the only viable set A is [[2]] and there is only one loop.

The set of 'K' values seems rather sparse, but all systems 3x+k (k is odd) must have at least one loop (unless every seed diverges to infinity), so where do these come from?

Other values of k

If we start with the assumption that there is an s value, say s¬1, that has a common factor with K, say 'f', then we can define

t¬1=s¬1/f, k=K/f
.

Then,

s¬2=3*s¬1+K=3(f*t¬1)+(f*k)

Dividing through by 'f' gives

t¬2=3*t¬1+k

So the set [t¬1, t¬2, …] forms a cycle in 3x+k.

How can we use this to identify the loops in k = 11? I don't know of any solutions to 2^m-3^n=11, so we need to search for a solution where 2^m-3^n=11*x and then see if any of the s-values generated are also multiples of x. Or we could take the more direct approach of calculating the orbits of values in 3x+11 and see where the loops are, and then work backwards to find the s-values. This second approach sounds easier.

Starting with 1, we immediately find the 2−cycle [1,7],

3*1+11=14,
14/2=7,
3*7+11=32,
32/2^5=1

The corresponding A-list is A = [1,5], so m=6 and n=2, this gives

K=2^6-3^2=55 (5*11)
s¬1=3^1+2^1=5
s¬2=3^1+2^5=35

So the loop [1,7] in 3x+11 corresponds to [5,35] in 3x+55.

There is also a 1−cycle, [11] in 3x+11, which in hindsight is rather obvious, as (3k+k)/2^2 always equals k. This loop can be derived using multiplication from the [1, 4, 2, 1] cycle in 3x+1. Generally, if [s¬1, s¬2, …, s¬n] defines a cycle in x→3x+K, then [s¬1*f, s¬2*f, …, s¬n*f] will form a cycle in x→3x+K*f.

Interestingly, in 3x+11 there is a third loop [13, 25, 43, 35, 29, 49, 79, 31]. Here A = [1, 1, 2, 2, 1, 1, 3, 3], so m=14, n=8, giving K=2^[14]-3^8=9823=893*11. If there are any other cycles in 3x+11 they will involve very big numbers, I've searched up to 10 million.

Multiples of k

Generally to find cycles in 3x+k, when we can't express k in the form k=2^m-3^n, we need to find a value of 2^m-3^n that is a multiple of k. To do this we separate out 2^m and 2^n and look at the remainders when we divide them by k. Below we show the results for k=11:

   

You can see the results for other k values by entering the value into the box and clicking the "Show Remainders" button.

If 2^m mod k=3^n mod k then 2^m-3^n will be a multiple of k. The following table shows the results for the number you chose above.

The squares coloured in white are the pairs where this is true. If you chose a prime number then the pattern in the table will repeat indefinitely, so for 11, as well as the 5 (m,n) pairs (0,0), (2,4), (4,3), (6,2) and (8,1) there are an infinite number of other combinations achieved by adding (10j, 5k), j and k are positive integers, to each of these. For instance adding (0,5), (10,0), (10,5), (20,0), (20,5) and (20,10) to (2,4) gives us these examples.

2^2-3^4=−77=11*−7
2^2-3^[4+5]=−19679=11*−1789
2^[2+10]-3^4=4015=11*365
2^[2+10]-3^[4+5]=−15587=11*−1417
2^[2+20]-3^4=4194223=11*381293
2^[2+20]-3^[4+5]=4174621=11*379511
2^[2+20]-3^[4+10]=−588665=11*−53515

If you chose a non-prime k, say 15, then the sequence of remainders may start with a few non repeating terms before settling down into the cycle. In the table these numbers will be shown with a darker background.

Systematic Search

I ran a systematic search for loops in other systems for k values up to 199 and seed values up to 100 million. You can see the results here. In this search all the loop seeds were relatively small compared to k, the largest ratio being 243.4 for s = 7055 and k = 29. The sequence of record holders is…

System Seed Size Seed/K
3x+1 1 1 1.0
3x+5 347 17 69.4
3x+29 7055 41 243.3

This would be an interesting search to continue, but it is rather expensive in computer time. The absense of medium size loop seeds in this search doesn't rule out their existance but it does suggest that loops become scarcer as the range of numbers searched gets higher.

Other 3x+1 Pages

A-Lists: Explores the lists of A-Values described above, the loops they generate and the constraints they place on the locations of additional loops in 3x+1.
3x+47: 47 is 128-81 (2^7-3^4), so it should have some 4−cycles. It also has a 7 cycle and 16 cycle. Click the image for an illustration.
log(3)/log(2): Looking for integer approximations to this expression. The best candidates for finding loops are when m/n is close to log(3)/log(2).
Constraints on loop size: More ramblings on loop size.

Elsewhere on this site

(c) John Whitehouse 2011 - 2022