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 easier.

1−cycles

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

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

If we relax the positive integer requirement we get a second solution where a1 = 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 + 2a1 + 3) / 2(a1+a2) = x (where 'a1' and 'a2' are integers greater than 0).

This can be rearranged to (2(a1+a2)−9)x = (2a1+3), so we need to find integral values of (2a1+3) which are multiples 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 for 1−cycles, leaving only −5 and −7, which are two halves of the same solution, [−5, −14, −7, −20, −10, −5]. This cycle contains 3 even numbers as a1+a2 = 3. 

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 equtions of the form K⋅x = S, where:

K = 2a1+a2+...+an - 3n
S = 3n-1 + 3n-2*2a1 + 3n-3*2a1+a2 + ... + 2a1+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 = a1 + a2 + ... + an
K = 2m - 3n

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 > (log(3) ∕ log(2))n. Log(3) ∕ log(2) is just under 1.585, so there will be at least 58% more even values than odd one.

Loops in 3x+k

First, let us define A1 as the set [a1,a2,...,an], A2 as [a2,...,an,a1], A3 as [a3,...,an,a1,a2], etc. (Ai+1 is obtained by rotating the values in Ai one place to the left). The set [A1, A2, ...] has n members, as An+1 is the same as A1.

We can then define the set [s1, s2, ...] = [S(A1), S(A2), ...] as the values obtained by inserting the sets [A1,...,An] into the numerator of the equation for 'x'.

S(A) = 3n-1 + 3n-2⋅2a1 + 3n-3⋅2a1+a2 + ... + 2a1+a2+...+a(n-1)

We can now see that s2 = (3⋅s1 + K) ∕ 2a1,

   s1 = 3n-1 + 3n-2⋅2a1 + 3n-3⋅2a1+a2 + ... + 2a1+a2+...+a(n-1)
  3s1 = 3n + 3n-1⋅2a1 + 3n-2⋅2a1+a2 + ... + 3⋅2a1+a2+...+a(n-1)
3s1+K = 3n-1⋅2a1 + 3n-2⋅2a1+a2 + ... + 3⋅2a1+a2+...+a(n-1) + 2a1+a2+...+an
      = 2a1⋅(3n-1 + 3n-2⋅2a2 + ... + 3⋅2a2+...+a(n-1) + 2a2+...+an)
      = 2a1⋅s2

so the set [s1, s2, ...] represents an n−cycle in x→3x+K.

Clearly all systems of the form x→3x + (2m − 3n) will have cycles, with 'n' odd and 'm' even values. For all cases other than n = 1, m = 2 there will be multiple loops. 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 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 s1, that has a common factor f with K, then we can define t1 = s1 ∕ f and k = K ∕ f. Then, s2 = 3⋅s1 + K = 3(f⋅t1) + (f⋅k), which is also a multiple of f, so, if s2 = f⋅t2 then t2 = 3⋅t1+k and the set [t1, t2, ...] forms a cycle in 3x+k.

How can we use this to identify the loops in k = 11? We could look for K values that have 11 as a factor, then search the corresponding s values looking for one that has K ∕ 11 as a factor, or we could construct the tree for 3x+11 and see where the loops are.

The second approach sounds easier. Starting with 1, we immediately find the 2−cycle [1,7], as 3⋅1 + 11 = 14 = 7⋅2 and 3⋅7 + 11 = 32 = 1⋅32. Here A = [1,5], so m=6 and n=2, giving K = 26−32 = 55 = 5⋅11.

s1 = 31 + 21 = 5
s2 = 31 + 25 = 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) ∕ 22 always equals k. This loop can be derived using multiplication from the 1−cycle in 3x+1. If [s1, s2, ..., sn] forms a n−cycle in x→3x+K, then [s1⋅f, s2⋅f, ..., sn⋅f] forms a n−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 and K = 214−38 = 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.

Factors of k

Generally to find cycles in 3x+11 we need to find m and n values where 2m−3n is a multiple of 11. If we look at 2m modulo 11 we get the sequence [2, 4, 8, 5, 10, 9, 7, 3, 6, 1] and for 3n [3, 9, 5, 4, 1]. To find a solution we need to match pairs of numbers, one from each set, m being the position in the first set and n that in the second. The 3 in position 8 in the first set matches the three in position 1 in the second, giving (m,n) = (8,1). The full list is

28-31 = 256-3 = 253 = 11⋅23
26-32 = 64-9 = 55 = 11⋅5
24-33 = 16-27 = -11 = 11⋅(-1)
22-34 = 4-81 = -77 = 11⋅(-7)
210-35 = 1024-243 = 781 = 11⋅71

Two of these, 24-33 and 22-34 are negative, but as the remainders modulo 11 cycle for every 10 'm' we can just add 10 to the 'm' values giving

210+4-33 = 16384−27 = 16357 = 11⋅1487
210+2-34 = 4096−81 = 4015 = 11⋅365

The remainders for powers of 3 also form a 5 cycle, so the 5 examples we have found; (m,n) ∈ [(8,1), (6,2), (14,3), (12,4), (10,5)]. We can generate the full set by adding the increments (10i,5j) to any of the values in this basic set (i and j are integers ≥0).

Generally, for all primes, p, if K(m,n) is a multiple of p then so is K(m+i(p−1),n+j(p−1)), where i and j can be any positive integer. This is because 2i(p−1) mod p = 3j(p−1) mod p = 1. As K(0,0) = 0, K(i(p−1),j(p−1)) is also a solution, so for every prime 'p' there is an infinite set of K values with p as a factor.

In the example for k=11, the generic equation for p misses out half the solutions as 35j%11 = 1 giving the set of solutions K = 2m+10i−3n+5j, where (m,n) ∈ [(8,1), (6,2), (14,3), (12,4), (10,5)] and i,j are integers.

Factors of k when k isn't prime

This factor analysis only applies to primes and our equations only work when k = 6i+1 or 6i+5. The first non-prime of this form is 25, the second 35. The remainder sets are

2i mod 25 = [1, 2, 4, 8, 16, 7, 14, 3, 6, 12, 24, 23, 21, 17, 9, 18, 11, 22, 19, 13]
3i mod 25 = [1, 3, 9, 2, 6, 18, 4, 12, 11, 8, 24, 22, 16, 23, 19, 7, 21, 13, 14, 17]
2i mod 35 = [1, 2, 4, 8, 16, 32, 29, 23, 11, 22, 9, 18]
3i mod 35 = [1, 3, 9, 27, 11, 33, 29, 17, 16, 13, 4, 12]

The important thing to note here is that although it is not so easy to predict how big the remainder sets are they still form a loop that includes 1, so there will always be an infinite set of answers.

There are at least 8 cycles in 3x+25, with seeds of [5,7,17,25,95,115,935,1735]. Six of these are multiples of cycles in 3x+5. The loop based on 7 has 8 members, [7, 23, 47, 83, 137, 109, 11, 29], A = [1, 1, 1, 1, 2, 5, 1, 4], m = 16, n = 8, K = 58975 = 25⋅2359.

There are at least 9 cycles in 3x+35, based on [7, 13, 17, 25, 35, 133, 161, 1309, 2429]. Of these, [7, 35, 133, 161, 1309] are multiples of cycles in 3x+5 and [25, 35] are multiples of cycles in 3x+7. Therefore, 17 is the only novel loop. This is a 4−cycle where A = [1,2,1,4], so K = 28−34 = 175 (5⋅35).

121 is the first composite k value where non of the factors are multiples of a K value. This has 5 loops based on [5, 11, 19, 121, 143]. The loop sizes are [18, 2, 46, 1, 8] so they all come from different K's.

For the 19-cycle:

A = [1,2,2,1,1,1,1,3,1,5,2,1,1,2,3,1,1,1,2,1,2,1,2,3,1,1,2,3,2,2,1,2,2,2,3,3,3,1,2,1,2,5,1,1,1,6]
K = 288 - 346 = 309476146883225416223685127 = 121 × 2557654106472937324162687

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 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, so it should have some 4−cycles. It also has a 7 and 16 cycle. Click the link for an illustration.

Integer approximations to log(3) ∕ log(2): 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.

Other pages

 

(c) John Whitehouse 2011 - 2017