Emerging Patterns in the Collatz (Hailstone) Sequence

The following is a paper I wrote at R's (my significant other) urging. The intuition for the paper emerged in a matter of seconds when first presented with the problem. The reason for the speed really lies in the serendipitious presence of the multiplication chart usually included as front matter/helpful aids for students in ruled college notebooks happened to be lying in front of me while R was sharing this bit of mathematical trivia. In any case my initial response to the problem was to point to the multiplication table. But this was far from convincing being a convincing argument for R. This was way back in 2001 or 2002. I have struggled to write up what I saw in that first encounter with the problem over the last few years. Initial drafts were sent to my former math professors. But math and this particular puzzle is not my life business - at that time I was in fact attempting to launch an online women's wear business. But a few years ago (2005) I really got serious and tried to make a more concerted effort at trying to put down all my insights. The resultant product was then sent off to a mathematics journal primarily because it was the first journal that came up in an online alphabetical list of Mathematics Journals that did not require paper submissions to be especially formatted. After waiting for many months I finally received notification that the paper had been rejected. So now I am free to publish it myself in my very own blog space (Blogger is actually better for posting this article than my other blogspace hosted by Windows Live Spaces). R says that the paper should be properly broken down into several papers each focusing on a particular insight but I wanted to get the original out into blogspace as soon as possible - I'm very much into immediate results -very much a product of my age I suppose. If time and interest permits I may in fact get around to doing what R suggests. But for the moment, I hope that there is someone out there who will be able to make it through my paper and be able to appreciate and enjoy the patterns that are so evident to me in Hailstone Sequence. The title and abstract below were used in the submitted version of the paper. I think "Emerging Patterns in the Oscillating Collatz (Hailstone) Sequence" is perhaps more appropriate to the nature and content of the paper. Enjoy!!!


Observations on the Collatz Problem


Abstract

The Hailstone Sequence has been shown computationally to converge to the repeating cycle 4 2 1 for integers up to approximately 367 * 1015. Although the Hailstone Sequence is a bobbing sequence it sees periods where a mini-decreasing sequence is embedded within it. The key to this behavior lies in how the recursion formula used to generate the sequence splinters the set of integers into two subsets: the set of odd integers and the set of even integers. The recursion formula associated with odd integers ensures that the term following an odd integer will be an even integer. But the recursion formula associated with even integers makes it possible for an even integer to be followed by not just one even integer but for a limitless number of other even integers. In particular there are special even integers that reduce to 4 2 1 because these even integers are continuously followed by even integers that require the repeated application of the recursion formula associated with even integers. These special even integers can be picked out by the formula (2x)n, where x Z+: {x = 1,2,3,….}and n = 1. Subsets described by (2x)n, where x Z+: {x = 1,2,3,….}and n Z+: {n = 1,3,5,7,….} pick out integers with the same number of subsequent even integers and same number of applications of the recursion rule for even integers. The sheer prevalence of the occurrence of numbers which will initiate a mini-decreasing sequence within the Hailstone Sequence including those numbers that go to 4 2 1 suggest that it is an inherent property of the set of Z+ that the Hailstone Sequence behaves the way it does. In short the key to the Hailstone Sequence is how Z+ is structured around 2x with respect to the Hailstone Sequence recursion formulas.

Introduction

In this paper I would like to consider the Collatz Problem and suggest some new ways of looking at the problem that may point to a possible solution.

The Collatz Problem goes by a number of different names: 3x + 1 Mapping, the 3x + 1 Problem, Kakutani’s Problem, Ulam’s Problem, the Syrcacuse Problem, the Syracuse Algorithm, Hasse’s Algorithm, Thwaite’s Conjecture.[1] It is also called the Hailstone Problem and Hailstone Series (erroneously since the problem defines a sequence and not a series) after the numbers in the sequence that are generated by the 3x + 1 Problem.[2]

Statement of the Collatz Problem

Consider the sequence {an} generated by the following recursion formulas. Let an Z+; the first term in the sequence, a0, is given.

an+1 = (an) / 2, if an is even
3(an) + 1, if an is odd,

n = 0, 1, 2, 3, ….

The Collatz Problem poses the following question: Does the sequence generated by the recursion formulas described above converge? Show for any an Z+ k > 0 such that ak = c, a constant. In short we are asking the question does the sequence {an} as n goes to infinity, have a limit:

lim n → ( an) = c

Another way to phrase the problem is to ask does the sequence {an} converge. Of course if a limit exists for the sequence {an} we can say it converges.

Example: Let a0 = 3. The recursion formulas defined above generates the following sequence:

3 10 5 16 8 4 2 1 4 2 1…..

where a1 = 10, a2 = 5, a3 = 16, a4 = 8, a5 = 4, a6 = 2, a7 = 1, a8 = 4, a9 = 2, a10 = 1,….

The Collatz recursion formulas set up two different ways to handle an integer depending on whether it is even or odd. If the integer an is even, divide it by 2. If the integer an is odd, perform the following operation: 3(an) + 1. Notice a8 come back to the same value as a5. Iteration of the recursion formulas results in a sequence that ‘converges’ to a repeating cycle of 4,2,1. The Hailstone Sequence does not converge to a particular constant but to a cycle. One alternative would be to think of the first term in the cycle, 4, as a constant that the Hailstone Sequence converges to since any Hailstone sequence which converges to 4, really converges to the cycle 4 2 1. As of this writing, numbers up to approximately 367 * 1015 have been checked for convergence to this cycle.[3] Another interesting feature of the sequence generated by the Collatz Problem is that it “bobs”. By “bobs” we mean a sequence of integers whose members alternately increase and decrease.[4]


Preliminaries: Definition of Terms, Background on Sequences, and Statement of Objective

Definition of the More Ubiquitous Terms

In this paper I have gathered together my reflections on the behavior of the Collatz iteration procedure. I have organized these reflections into observations revolving around odd integers and observations revolving around even integers. Before proceeding with my observations, I would like to define terms I will constantly use and present guiding intuitions that will be in play throughout the paper.

I will use the term Hailstone Sequence to refer to the sequence generated by the recursion formulas (iteration procedure) associated with the Collatz Problem. Secondly, for the purpose of this paper, I will name the two actions of the iteration procedure as follows:

Let Even Rule be defined as the recursion formula assigned to even integers: an+1 = (an) / 2

Let Odd Rule be defined as the recursion formula assigned to odd integers: an+1 = 3(an) + 1

I will use the term Collatz Problem to refer to both the iteration procedure and the question regarding convergence. In such cases use the context to determine the correct meaning. I will also use the term iteration procedure to refer the rules used to generate the Hailstone Sequence. Further I will use the terms Hailstone Sequence, Collatz sequence, or sequence generated by the Collatz Problem to point to the same sequence. Other terms will be defined as they occur in the context of the paper.

Background on Sequences

There are a handful of general facts one should be familiar with when thinking about sequences. A sequence {an} is an ordered succession of numbers. These numbers are called terms of the sequence. The number of terms can be infinite (infinite sequence) or finite (finite sequence). The terms in a sequence {an} are ordered – i.e. a sequence is distinguished by the arrangement of its terms. The first term in a sequence would be identified as a1, the second term in the sequence as a2, etc. The method for generating a sequence {an} can be done using a general term or via recursion formula. In a general term sequence there is a relationship between the term and its location in the sequence (term number). In a recursive sequence, the first term is given and to obtain the next term in the sequence one must use the specified formula. The specified formula is known as the recursion formula for the sequence. The terms in a sequence can increase, decrease, strictly increase, strictly decrease, or bob. A sequence is said to be increasing if each successive term in the sequence is equal to or greater than the term preceding it. A sequence is said to be strictly increasing if each successive term in the sequence is larger than the term preceding it. A sequence is said to be decreasing if each successive term in the sequence is equal to or less than the term preceding it. A sequence is said to be strictly decreasing if each successive term in the sequence is smaller than the term preceding it. In a bobbing sequence the a particular term will be followed by smaller (or larger) term which in turn would be followed larger (smaller) term etc. A sequence can be said to converge or diverge. If it converges, there exists a limit for the sequence. If the sequence does not converge, no limit for the sequence exists. [5] In the Collatz Problem we have a bobbing recursive sequence with two recursion formulas (alternatively one recursion formula with two components) that does not have limit.

Statement of Objective

First I would like to present my guiding intuitions. The most salient feature of the Collatz Problem’s iteration procedure is the categorization of the positive integers into even integers and odd integers and assigning a separate rule to each type of integer.

Let us consider what each rule does individually within the context of the Collatz Problem. When you encounter an even integer term in a Hailstone Sequence, the Collatz Problem specifies that to generate the next term in the sequence you have to divide the even integer term by two. Thus the term following an even integer in Hailstone Sequence will be smaller than it. To put it formally:

Let an be an even term in a Hailstone Sequence, where all an Z+. By definition of the Collatz Problem: an+1 = an/2, therefore an+1 < 1 =" 3an"> an.

We can see now why the Hailstone Sequence is a bobbing sequence – i.e. the sequence alternates between a larger term and a smaller term. The words “larger” and “smaller” is meant relative only to adjacent terms.

Let us step away from the Collatz Problem for a moment to see how these rules would function in a slightly different context.

Consider iterating the Even Rule by itself to generate a sequence. Let en R, e0 is given.

en+1 = (en) / 2, n = 0,1,2,3,…..

We can describe this sequence in another way to see the ramification of the Even Rule. Let x and n R and x is given. We can define a sequence using the following expression:

x/2n, n = 0, 1, 2, 3, ….

The value of x is fixed therefore x can be considered a constant. We know that the limit of this sequence as n approaches infinity is 0: lim n → ( x/2n) = 0. We realize if we iterate the Even Rule we will generate a strictly decreasing sequence. In other words using the Even Rule alone to generate a sequence we generate a sequence whose terms get smaller and smaller ultimately heading to zero. In short, we have a decreasing sequence that converges to 0.

Similarly, consider iterating the Odd Rule to generate a sequence. Let on Z+ and o0 is given.

on+1 = 3(on) + 1, n = 0,1,2,3,…..

lim n → (3(on) + 1) = . If we iterate the Odd Rule to generate a sequence, the terms in the sequence will get larger and larger. In other words, we have a strictly increasing sequence. However, unlike the Even Rule Sequence, the Odd Rule Sequence diverges.

The iteration procedure in the Collatz Problem combines the Even Rule and the Odd Rule and results in a sequence that reduces eventually to a cycle or ground state consisting of a three-element unit that repeats: 4,2,1, 4, 2, 1,….[6]

Thus we know three independent and seemingly trivial facts about the Collatz Problem. First, the procedure assigned to an even integer acts to reduce it to generate a smaller subsequent term. Second, the procedure assigned to an odd integer acts to increase it to yield a larger number as the next term. Further, outside the context of the Collatz Problem, we know that iterating the Even Rule by itself generates a sequence that converges to zero; iterating the Odd Rule generates a sequence that diverges. Third, we also know that for numbers up to 367 * 1015, the sequence generated by the Collatz Problem is a pseudo-decreasing sequence that ultimately “converges” to 4, 2, 1, 4, 2, 1…. Why does a Hailstone Sequence “decrease” to a repeating cycle? The crux of the problem lies in understanding how these actions come together to produce the behavior that we see in sequences generated by the Collatz Problem.

My primary tactic in trying to explain the behavior of the Hailstone Sequence is to look at the characteristics of the odd integers and the even integers separately and in particular to focus on the role the even numbers play in the Collatz Problem because it seems the reducing mechanism of the Even Rule plays an important role in creating a pseudo-decreasing sequence.


Catalog of Observations of the Collatz Problem


Observation 1[7]. Result of Applying the Odd Rule: Application of the Odd Rule to a term in a Hailstone Sequence results in an even number as the next integer in the sequence. In spite of the fact that the Odd Rule increases the next element in the Hailstone Sequence, this number will always be even and therefore reducible by the Even Rule. So in any particular sequence, a term in the sequence is even and immediately reducible or will become even in one step and the resulting term will be reducible.

The first claim made by Observation 1 can be recast by asking the question “Does the Collatz Problem’s rule for odd positive integers, an, namely substituting it into [ 3(an) + 1 ], yield an even integer?”

Let x Z+. We define even integers

2x
and odd integers,
2x + 1


We know that the Odd Rule is only applied to odd integers so for “an” we can substitute (2x + 1), by definition of odd numbers given above.

So, 3(an) + 1 → 3(2x + 1) + 1 → 6x + 3 + 1 → 6x + 4 → 2(x + 2) → if we let xk = (x + 2), then 2(x+2) becomes 2xk which is nothing other than a form of 2x. (The arrows in this context are used to facilitate the flow of text.) [8]

We have now established the result of applying the Odd Rule is an even number. Next we have to show that this results in the application of the Even Rule. Since the iteration procedure associated with the Collatz Problem assigns to even integers what we call the Even Rule we are done. In other words to generate the next integer in the sequence we take this even result and apply

an = (an+1) / 2

When an odd integer appears as a term in a Hailstone Sequence application of the Odd Rule results in the following term in the sequence being larger and even. This even term is then reduced by the Even Rule to generate the next term in the sequence. In short, we see that the sequence bobs from a larger term to a smaller term.


Observation 2. Result of Applying the Even Rule: Application of the Even Rule to an entry in a Hailstone sequence will result in either an odd or even integer as the next element in the sequence.

Using the definitions for even integers in Observation 1 above and substituting “2x” for (an) into the Even Rule we have: (an) / 2 → 2x / 2 → x. We know x is a positive integer by the parameters set by the Collatz Problem but we cannot tell whether x is odd or even.

From Observation 1 we have that the Odd Rule generates an even integer as the next element in the sequence. In Observation 2 we have that the Even Rule generates either an even integer or an odd integer as the next element in the sequence. These two observations can be visualized in the following schematic:



Odd Integer is increased → Even Integer is decreased → Odd Integer is increased → ….4 2 1

Or

Even Integer is decreased →….4 2 1


I have chosen to start the diagram with an odd term but it could just as easily have started with an even term. At every occurrence of an even integer entry we are to insert the bifurcation of possible integer type. At every occurrence of an odd integer we show an even integer as the next term. We are to assume that this is a representation of a Collatz sequence.

With this observation we can see that we have moved away from a simply bobbing sequence that alternates between smaller and larger terms to a sequence where a distinct decreasing phase is possible – using the diagram as an example, a decreasing phase that lasts for two terms. With the Even Rule we have moved away from a consistent alternation between applications of the Odd Rule and Even Rule. Rather, we have a situation where the Even Rule can be applied consecutively to generate terms for the sequence. As we have seen in the Preliminaries Section above, iteration of the Even Rule solely (outside the context of the Collatz Problem) generates a strictly decreasing sequence. In the Collatz Problem the consecutive application of the Even Rule is possible only under certain conditions – namely when an even integer appears as a term in a Hailstone Sequence. This raises the following question: Which even integers will start consecutive application of the Even Rule in a Hailstone Sequence?

Observation 3. Which Even Integers will start consecutive application of the Even Rule in the Hailstone Sequence: To answer this question, let us look at the set of positive even integers referred to henceforth as the 2n Set. We notice right away the 2n Set falls neatly into two subsets: even integers which when divided by two result in an odd integer and even integers which when divided by two result in an even integer. In the table below I have captured the results for the first few positive even integers. (Note: Tables will have the data in each column presented by itself because I don't know how to format the table as it appears in my paper.)

Table 1: Dividing Even Integers by Two (2)

Column 1: Positive Even Integers, E

2
4
6
8
10
12
14
16
18
20
22
24
26
28
30
32
34
36
38
40
….


Column 2: E/2 = Odd Integer


1
-
3
-
5
-
7
-
9
-
11
-
13
-
15
-
17
-
19
-
….


Column 3: E/2 = Even Integer


-
2
-
4
-
6
-
8
-
10
-
12
-
14
-
16
-
18
-
20
….

Another way to say the same thing is to say that the set of even integers can be seen as a union of the following two subsets:

2n Set where n Z+: {2n ‌ n = {1,2,3,4,5,6,7,8….}


Odd Subset of 2n Even Subset of 2n (4n Subset)
2n where n Z+: {2n ‌ n = {1,3,5,7,….} 2n where n Z+: {2n ‌ n = {2,4,6,8,….}

The Odd Subset of 2n picks out from the 2n Set even integers that when divided by two yield an odd result. Similarly, the Even Subset of 2n picks out even integers from the 2n Set that when divided by two yield an even result. We shall use the terms Odd Subset of 2n and Even Subset of 2n to refer to these subsets in our discussion.

Coming back to the Collatz Problem, we can see the appearance of an even integer in the sequence can be used to signal what will follow it. When an even integer from the Odd Subset of 2n appears as an entry in the Collatz Sequence, the following entry in the sequence will be odd. When an even integer from the Even Subset of 2n appears as an entry in the Collatz Sequence, the following entry in the sequence will be even. To answer the question “How many even entries will follow a member of the Even Subset of 2n when it appears in the Hailstone Sequence?” we need to consider the characteristics of members of the Even Subset of 2n.

Let us now explore integers from the Even Subset of 2n in Table 2 below. The first column lists members of the Even Subset of 2n. The second column contains the sequence generated by iterating the Even Rule on the integer in the first column. In other words, we take the integer given in the first column and keep dividing the result by two until we reach a number that cannot be divided by two to generate a sequence. The third column lists the number of applications of the Even Rule possible from the integer in column one. The fourth column lists the number of even integers in the sequence illustrated in column two.

Table 2: Even Subset of the Set Even Integers, henceforward represented as 2n, with Information Regarding Number of Subsequent Evens and Number of Even Rule Applications

Column 1: Integers from Even Subset of 2n, e

4
8
12
16
20
24
28
32
36
40
44
48
52
56
60
64
68
72
76
80
84
88
92
96
100
104
108
112
116
120
124
128
132
136
140
144
148
152
156
160
164
168
172
176
180
184
188
192
196
200
204
208
212
216
220
224
228
232
236
240
244
248
252
256
260
264
268
272
276
280
284
288
292
296
300
304
308
312
316
320
324
328
332
336
340
344
348
352
356
360
364
368
372
376
380
384
388
392
396
400
404
408
412
416
420
424
428
432
436
440
444
448
452
456
460
464
468
472
476
480
484
488
492
496
500
504
508
512
….


Column 2: Sequence generated by iterating Even Rule on e, the integers in the Even Subset of 2n.



4→2→1
8→4→2→1
12→6→3
16→8→4→2→1
20→10→5
24→12→6→3
28→14→7
32→16→8→4→2→1
36→18→9
40→20→10→5
44→22→11
48→24→12→6→3
52→26→13
56→28→14→7
60→30→15
64→32→16→8→4→2→1
68→34→17
72→36→18→9
76→38→19
80→40→20→10→5
84→42→21
88→44→22→11
92→46→23
96→48→24→12→6→3
100→50→25
104→52→26→13
108→54→27
112→56→28→14→7
116→58→29
120→60→30→15
124→62→31
128→64→32→16→8→4→2→1
132→66→33
136→68→34→17
140→70→35
144→72→36→18→9
148→74→37
152→76→38→19
156→78→39
160→80→40→20→10→5
164→82→41
168→84→42→21
172→86→43
176→88→44→22→11
180→90→45
184→92→46→23
188→94→47
192→96→48→24→12→6→3
196→98→49
200→100→50→25
204→102→51
208→104→52→26→13
212→106→53
216→108→54→27
220→110→55
224→112→56→28→14→7
228→114→57
232→116→58→29
236→118→59
240→120→60→30→15
244→122→61
248→124→62→31
252→126→63
256→128→64→32→16→8→4→2→1
260→130→65
264→132→66→33
268→134→67
272→136→68→34→17
276→138→69
280→140→70→35
284→142→71
288→144→72→36→18→9
292→146→73
296→148→74→37
300→150→75
304→152→76→38→19
308→154→77
312→156→78→39
316→158→79
320→160→80→40→20→10→5
324→162→81
328→164→82→41
332→166→83
336→168→84→42→21
340→170→85
344→172→86→43
348→174→87
352→176→88→44→22→11
356→178→89
360→180→90→45
364→182→91
368→184→92→46→23
372→186→93
376→188→94→47
380→190→95
384→192→96→48→24→12→6→3
388→194→97
392→196→98→49
396→198→99
400→200→100→50→25
404→202→101
408→204→102→51
412→206→103
416→208→104→52→26→13
420→210→105
424→212→106→53
428→214→107
432→216→108→54→27
436→218→109
440→220→110→55
444→222→111
448→224→112→56→28→14→7
452→226→113
456→228→114→57
460→230→115
464→232→116→58→29
468→234→117
472→236→118→59
476→238→119
480→240→120→60→30→15
484→242→121
488→244→122→61
492→246→123
496→248→124→62→31
500→250→125
504→252→126→63
508→254→127
512→256→128→64→32→16→8→4→2→1
….

Column 3: List of the number of repeated applications of the Even Rule for each of the integers in the Even Subset of 2n. Given an integer in the even subset of 2n listed in Column 1 above, we discover that we can apply the Even Rule at least twice. In short we are allowed to repeat the application of dividing the resulting integer by 2 as long as the result is even. This column keeps track of the emerging pattern of the number of applications of the Even Rule.

2
3
2
4
2
3
2
5
2
3
2
4
2
3
2
6
2
3
2
4
2
3
2
5
2
3
2
4
2
3
2
7
2
3
2
4
2
3
2
5
2
3
2
4
2
3
2
6
2
3
2
4
2
3
2
5
2
3
2
4
2
3
2
8
2
3
2
4
2
3
2
5
2
3
2
4
2
3
2
6
2
3
2
4
2
3
2
5
2
3
2
4
2
3
2
7
2
3
2
4
2
3
2
5
2
3
2
4
2
3
2
6
2
3
2
4
2
3
2
5
2
3
2
4
2
3
2
9

Column 4: Number of Subsequent Evens. Given an integer from the even subset of 2n, we discover that division by 2 will yield another even integer. This column keeps track of the number of ensuing even integers for the initial members of the even subset of 2n.

1 even
2 evens
1 even
3 evens
1 even
2 evens
1 even
4 evens
1 even
2 evens
1 even
3 evens
1 even
2 evens
1 even
5 evens
1 even
2evens
1even
3 evens
1 even
2evens
1 even
4 evens
1 even
2 evens
1 even
3 evens
1 even
2 evens
1 even
6 evens
1 even
2 evens
1 even
3 evens
1 even
2 evens
1 even
4 evens
1 even
2 evens
1 even
3 evens
1 even
2 evens
1 even
5 evens
1 even
2 evens
1 even
3 evens
1 even
2 evens
1 even
4 evens
1 even
2 evens
1 even
3 evens
1 even
2 evens
1 even
7 evens
1 even
2 evens
1 even
3 evens
1 even
2 evens
1 even
4 evens
1 even
2 evens
1 even
3 evens
1 even
2 evens
1 even
5 evens
1 even
2 evens
1 even
3 evens
1 even
2 evens
1 even
4 evens
1 even
2 evens
1 even
3 evens
1 even
2 evens
1 even
6 evens
1 even
2 evens
1 even
3 evens
1 even
2 evens
1 even
4 evens
1 even
2 evens
1 even
3 evens
1 even
2 evens
1 even
5 evens
1 even
2 evens
1 even
3 evens
1 even
2 evens
1 even
4 evens
1 even
2 evens
1 even
3 evens
1 even
2 evens
1 even
8 evens
….




Earlier, Table 1 revealed which even integers would be followed by another even integer. Even integers from the Odd Subset of 2n will be followed by an odd integer. Even integers from the Even Subset of 2n will be followed by an even integer. Table 2 shows that it is possible for an even integer from the Even Subset of 2n to be followed by as many as 8 evens and presumably more. This suggests that were a member of the Even Subset of 2n to appear as term in a Hailstone Sequence we will see repeated applications of the Even Rule turning the sequence from being a bobbing sequence to a decreasing sequence until an odd integer appears as a term. Based on the foregoing charts we can derive expressions to describe how many even entries will follow a given even integer. Equivalently, we can say we can determine the number of times the Even Rule will be applied for any even integer.

Given any even integer, rewrite it as a product of a power of 2, 2x , and an odd integer, n:

(2x)n

where x is an exponent of 2 and x Z+: {x = 1,2,3,….},
and n Z+: {n = 1,3,5,7,….}

By rewriting an even integer in this form, henceforth to be called the 2x Product Formula, we can predict the number of applications of the Even Rule that is possible if one were to iterate the Even Rule on it by looking at the exponent, x, and also the number of even integers that will follow it by subtracting one from x. In short, x represents the number of applications of the Even Rule and, x – 1 represents the number of even entries that will follow a given even integer. So when an even integer term is encountered in a Hailstone Sequence, we can tell how many applications of the Even Rule will ensue as well as the number of even integer terms before the sequence goes back to an odd integer term.

The value x takes must produce the largest power of 2 that can be accommodated by the even integer; the value n takes must be the smallest odd integer which when multiplied by the power of 2 will result in the even integer we are rewriting.

Example: Let us consider the Hailstone Sequence generated by the integer 15:

15→46→23→70→35→106→53→160→80→40→20→10→5→16→8→4→2→1

Let us take each even integer term as it occurs in this Hailstone Sequence.

46:
let us rewrite 46 in the 2x Product Formula: (21)23
the largest power of 2 that can be accommodated by 46 is 2
x = 1, we can expect that there will be one application of the Even Rule
x – 1 = 0, we can expect that an odd integer term will immediately follow 46.

70:
let us rewrite 70 in the 2x Product Formula: (21)35
the largest power of 2 that can be accommodated by 70 is 2
x = 1, we can expect that there will be one application of the Even Rule
x – 1 = 0, we can expect that an odd integer term will immediately follow 70.

106:
let us rewrite 106 in the 2x Product Formula: (21)53
the largest power of 2 that can be accommodated by 106 is 2
x = 1, we can expect that there will be one application of the Even Rule
x – 1 = 0, we can expect that an odd integer term will immediately follow 106.

160:
let us rewrite 160 in the 2x Product Formula: (25)5
the largest power of 2 that can be accommodated by 160 is 32
x = 5, we can expect that there will be five applications of the Even Rule
x – 1 = 4, we can expect four even integer terms to follow 160 in the sequence before an odd integer reappears as a term.

16:
let us rewrite 16 in the 2x Product Formula: (24)1
the largest power of 2 that can be accommodated by 16 is 16 – we have an ankin
x = 4, we can expect that there will be four applications of the Even Rule
x – 1 = 3, we can expect three even integer terms to follow 16 in the sequence before an odd integer reappears as a term.

In this example we can see that the sequence goes from initially being a bobbing sequence with alternating terms increasing and decreasing to a sequence that sees two periods of being strictly decreasing. The second decreasing period is a result of the appearance of an ankin which reduces to 4 2 1. So here we see a concrete example of how a Hailstone Sequence can have periods where it is decreasing and periods where it is bobbing. Second we can see how the appearance of an ankin goes to the 4 2 1 cycle. Third, we saw how the 2x Product Formula can be a useful tool to making predictions about applications of the Even Rule and the number of even integer terms that will follow an even term in a Hailstone Sequence.

Analysis of 2x Product formula reveals that the set of positive even integers has a structure that splinters along 2x to create subsets of 2n that has ramifications for the Collatz Problem. Let us consider a few examples.

Integers having the form 2n where n Z+: {2n ‌ n = {1,3,5,7,….}} will have zero even integers following it were it to appear in a Hailstone Sequence. Alternatively, we can say that the Even Rule is only applied once if we encounter such an entry in the Hailstone Sequence.

Integers having the form (22)n where n Z+: {(22)n ‌ n = {1, 3, 5, 7, 9, ….}} will be followed by one even integer were it to appear in a Hailstone Sequence. Alternatively, it is possible for the sequence to experience two consecutive applications of the Even Rule.

Integers having the form (23)n where n Z+: {(23)n ‌ n = {1, 3, 5, 7, 9, ….}} will be followed two even integers were it to appear in a Hailstone Sequence. If an entry of this form occurs in the Hailstone Sequence, the sequence will experience three applications of the Even Rule.

Integers having the form (24)n where n Z+: {(24)n ‌ n = {1, 3, 5, 7, 9, ….}} will be followed three even integers were it to appear in a Hailstone Sequence; and the sequence will undergo four applications of the Even Rule.

Integers having the form (25)n where n Z+: {(25)n ‌ n = {1, 3, 5, 7, 9, ….}} will be followed by four even integers were it to appear in a Hailstone Sequence; and the sequence will undergo five applications of the Even Rule.

These examples illustrate that the 2x Product formula will allow us to determine how many applications of the Even Rule to expect when we encounter any even integer in a Hailstone Sequence. But more importantly they really drive home the fact that the number of applications of the Even Rule keeps pace with the exponent – as the exponent increases the number of applications of the Even Rule also increase. Further each exponent has associated with it a subset consisting of infinitely many even integers so the possibility of even integers from these subsets appearing in a Hailstone Sequence is highly likely.

Let us consider a set of integers having the form (2x), where x Z+: {2x ‌ x = {2,3,4,5,6,7, 8….}}. These integers are the first elements in each of the subsets described above. We have fixed n to 1 and have allowed the exponent to change. Let us call such integers of the form 2x ankin. To determine the number of applications of the Even Rule to expect of the index we calculate it by looking at the exponent of two, x. And to determine the number of subsequent even entries in the sequence we subtract one from the exponent: x – 1. Ankins are special because they reduce to the 4→2→1 cycle shared by all Collatz Sequences.

Examples: 22 = 4: 4→2→1, two applications of the Even Rule; one even
23 = 8: 8→4→2→1, three applications of the Even Rule; two evens
24 = 16: 16→8→4→2→1, four applications of the Even Rule; three evens
25 = 32: 32→16→8→4→2→1, five applications of the Even Rule; four evens
26 = 64: 64→32→16→8→4→2→1, six applications of the Even Rule; five evens
27 = 128: 128→64→32→16→8→4→2→1, seven applications of the Even Rule; six evens
28 = 256: 256→128→64→32→16→8→4→2→1, eight applications of the Even Rule; seven evens
29 = 512: 512→256→128→64→32→16→8→4→2→1, nine applications of the Even Rule; eight evens


Let us take a brief moment to sum up the progress of our discoveries. Observation 1 establishes that the application of the Odd Rule always produces an even integer as the next entry in the Hailstone Sequence. Observation 2 establishes that the application of the Even Rule yields either an even integer or an odd integer as the next entry in the Hailstone Sequence. Observation 3 makes several points. An even integer from the Odd Subset of 2n will be followed by an odd integer upon the application of the Even Rule; even integers from the Even Subset of 2n will be followed by an even integer Alternatively, we can use the 2x Product formula -- (2x)n, where x Z+: {x = 1,2,3,….} and n Z+: {n = 1,3,5,7,….} -- to predict exactly how many applications of the Even Rule are possible for any even integer. The possible number of applications of the Even Rule is commensurate with the exponent of 2. The 2x Product Formula describes infinite subsets of 2n consisting of infinitely many members since x can take values from {1,2,3,… } and n can take values from {1,3,5,7,…. }. The 2x Product formula therefore not only reveals that the possible number of applications of the Even Rule increase steadily but also that associated with each exponent is an infinite subset of the 2n Set. Lastly, we discovered that an ankin, integers of the form (2x), where x Z+: {x = 1,2,3,….}, when iterated using the Even Rule generates a sequence that reduces to 4 2 1. Because 1 is an odd number the sequence stops at 1. We can see by looking at the definition of ankin that there are an infinite number of ankins in Z+.

The consequences of our discoveries to the Collatz Problem are the following: instead of having a bobbing sequence with a balanced alternation between the application of the Odd and Even Rule to generate entries in the sequence it seems there are multiple occasions where the Even Rule can be applied consecutively to generate terms for a Hailstone Sequence while the Odd Rule can never be applied consecutively. Because of this we can say that the Collatz Problem favors the application of the Even Rule. As a result of this, a Hailstone Sequences experience periods where they bob interspersed with periods where they are strictly decreasing. Moreover, because ankins reduce to 4 2 1, it seems fair to assume that an ankin will eventually appear as a term in every Hailstone Sequence.

To state it all another way, we know the appearance of even entries in the Hailstone Sequence means that the sequence will not diverge simply as happens when iterating the Odd Rule by itself to generate a sequence. Rather there seems to be a weighting toward opportunities for the consecutive application of the Even Rule in the Hailstone Sequence. This suggests that the sequence is “converging” to something as happens with the x/2n Sequence. And since Hailstone Sequences reduce to 4 2 1 it seems that ankins must of necessity always appear at some point in these sequences.


Observation 4. Three Tables: The 2x Product formula – i.e. (2x)n, where x Z+: {x = 1,2,3,….} and n Z+: {n = 1,3,5,7,….}- while useful in determining if an even integer term in a Hailstone Sequence will go to another even doesn’t capture other dimensions of the 2n Set that may shed further illumination on the Collatz Problem. The three tables in this observation captures in different format information presented in Table 2, Observation 3. The reason for looking at the same information in a different way is to understand how the structure of the set of integers is responsible for the behavior of the Hailstone Sequence.

We had discovered that the 2n Set splinters into subsets described by (2x)n (2x Product formula ) with respect to the Collatz Problem. The first table we will look at, Table 3, analyses the elements of a few subsets described by (2x)n, where x Z+: {x = 1,2,3,….} and n Z+: {n = 1,3,5,7,….}.. Since the 2x Product formula has two variables, x and n, each column will feature a different exponent of 2 (e.g. 23n, 24n, etc). Meanwhile, the members of each (2x)n subset will be generated by n taking values from its range in the sequence they occur beginning with 1 (i.e. 1,3,5,7, etc).

Table 3: Members of a Few (2^x)n Subsets with Information about the Number of Even Rule Applications/Subsequent Evens

Column 1: Each integer belonging to (2^2)n Subset sees 2 applications of the Even Rule and and is followed only by one even integer.

4
12
20
28
36
…
Recursion No.:
8 (= 23)
(23)n Subset
3Apps/2Even

8
24
40
56
72
…
Recursion No.: 16 (= 24)
(24)n Subset
4Apps/3Even

16
48
80
112
144
…
Recursion No.:
32 (= 25)
(25)n Subset
5Apps/4Even

32
96
160
224
288
…
Recursion No.:
64 (= 26)
(26)n Subset
6Apps/5Even

64
192
320
448
576
…
Recursion No.:
128 (=27)


First, Table 3 is not meant to seem comprehensive. It captures just enough data to give a sense for the pattern that I attempting to point out. Earlier in our discussion in Observation 3 we had discovered that the 2x Product Formula could be used to identify integers having the same characteristics (i.e., number of subsequent even integers and number of Even Rule applications) with respect to the Collatz Problem. We have now uncovered another means of obtaining the same information. Again we see that 2x plays a role in grouping together similar even integers with respect to the Collatz Problem.

Let us now look at Table 3 in detail first at columns and then rows. Each column features the first few members of the (2x)n Subset with which it is associated. If you look down each column to see how the members in each subset are related it becomes clear that each set can be obtained recursively in the sense that given the first member[9] the next member in the set can be obtained by adding an appropriate recursion number to the preceding number. The recursion number turns out to be a power of two for each column. The recursion number (and its form as power of two) associated with each column is listed at the bottom following the ellipsis.

If we look across each row we discover that a doubling mechanism is at work – i.e., to get the next number in the row you have to multiply the current number by two (alternatively, divide by two to get the preceding number) to pick out numbers from Z+. For example if you are given the number 40 (3rd member of the (23)n Subset), you can find the 3rd member in the (24)n Subset by multiplying by 2; similiarly, the 3rd member in the (22)n Subset can be obtained by dividing by 2.[10] The first row is populated with ankins which reduce to 4 2 1 with repeated applications of the Even Rule. For example given one ankin we can pick out other ankins (going across the table by multiplying each new value by 2) or other even integers which will have the same number of subsequent evens (going down the column by adding the recursion number to each new value). Another example: If you have an even integer which will see three applications of the Even Rule, you can find an even integer which will see four applications of the Even Rule by multiplying it by 2. There are many ways of hopping around on this table but essentially there are only two actions: going across the table we multiply by 21 and going down each column we add by a power of 2, 2x.

As we study this table we notice the inescapable fact that there seems to be an infinite number of ankins – i.e. there are infinitely many ways for a Hailstone Sequence to reduce to 4 2 1. Furthermore, each column in Table 3 serves to reinforce the fact that there are an infinite number of integers in each 2xn Subset. This is simply another way to say that there are an infinite number of even integers which will see two applications of the Even Rule, an infinite number of even integers which will see three applications of the Even Rule, etc. The very structure of the 2n Set ensures that even integers from the Even Subset of 2n (alternatively, using our 2x Product Formula notation, (2x)n Subsets of 2n) will make an appearance in Hailstone Sequences.

The second table we will look at, Table 4, focuses on the pattern of occurrence of the number of subsequent even entries for each member of the Even Subset of 2n (i.e., {4,8,12,16,..}) using ankins to define an interval. The first column identifies the interval. The second column identifies the ankin marking the interval. The third column lists the number of subsequent even integers for each integer as they occur in the interval marked out by the ankin. The fourth column lists the number of applications of the Even Rule for each integer in the same interval. The fifth column lists the number of integers in the interval. The first two members of the Even Subset of 2n, 4 and 8, are ankins so the interval they define will only contain themselves therefore columns three and four will list only one number. Please note that as the number of integers in each interval increases, columns three and four will capture information for all the integers in the interval. For each interval the last number in columns three and four is associated with the ankin for the interval. . The fifth column tells us that ankins occur at intervals described by 2n where {(2n) ‌ n = {0,1,2,3,….}} if we omit the first ankin, 4.

Table 4: Occurrence of the Number of Subsequent Even Entries etc. following a member of the 2n Subset.
Interval



1st

2nd

3rd

4th

5th

6th

7th


8th
Ankin



4

8

16

32

64

128

256


512
Occurrence of Number of
Subsequent Even Integers


1

2

1 3

1 2 1 4

1 2 1 3 1 2 1 5

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 8

Number of Applications of Even Rule


2

3

2 4

2 3 2 5

2 3 2 4 2 3 2 6

2 3 2 4 2 3 2 5 2 3 2 4 2 3 2 7

2 3 2 4 2 3 2 5 2 3 2 4 2 3 2 6
2 3 2 4 2 3 2 5 2 3 2 4 2 3 2 8

2 3 2 4 2 3 2 5 2 3 2 4 2 3 2 6
2 3 2 4 2 3 2 5 2 3 2 4 2 3 2 7
2 3 2 4 2 3 2 5 2 3 2 4 2 3 2 6
2 3 2 4 2 3 2 5 2 3 2 4 2 3 2 9
# Ints.
Interval


1

1

2

4

8

16

32


64


Table 4 reveals in more detail the periodic appearance of the number of subsequent even integer terms and number of Even Rule applications. If we look at the numbers in columns three and four without worrying about which even integer they refer to, we are made very aware of a regular periodic pattern. First, the last number in each interval increases by an increment of one from interval to interval in both columns. Second, the string of numbers in each interval repeats all the intervals preceding it. For example, the 8th interval concatenates the numbers associated with each interval with the exception of the last number - it is increased by one. In other words, each interval essentially contains the numbers from all the intervals preceding it. We have two patterns from Table 4. One, ankins occur at intervals of 2n; two, each interval concatenates the string of numbers from the preceding intervals the only modification being the last number from the preceding interval is increased by one. This characteristic of repeating everything is very interesting because each interval doesn’t simply repeat everything in the interval just prior to it but repeats everything from every interval prior to it in a sequential manner – i.e, data from the first interval comes first followed by data from the second interval followed by data from the third interval, etcetera.

Thus far we have looked at columns three and four as collections of numbers. If we now consider these numbers as characteristics of members of the Even Subset of we can see that each interval is populated with an increasing number of integers from each of the (2x)n subsets preceding it. For example, in the seventh interval we notice that there are sixteen members from the (22)n Subset, there are eight members from the (23)n Subset, there are four members from the (24)n Subset, there are two members from the (25)n Subset, and one member each from the (26)n Subset and (28)n Subset.

Again we have another way of looking at the same thing: namely, given the structure of the set of 2n it seems inevitable that any Hailstone Sequence will see the appearance of even integers from the (2x)n subsets. It is an argument based on number. The sheer number of even integers that will see some number of applications of the Even Rule makes their appearance in a Hailstone Sequence a foregone conclusion. And while ankins are a bit more rare, it is not as if we need to show that all Hailstone Sequences rely on one ankin to get to 4 2 1. (Remember, ankins are special because they reduce to 4 2 1 – in other words the even rule is applied until 1 is reached.) What seems more reasonable to say is that each integer in Z+ has associated with it an ankin with respect to the Collatz Problem.

I will bring to the reader’s attention one last place where 2x seems to be at work in the Even Subset of 2n. Its value lies in giving some gloss of the mechanism at work in columns three and four in Table 4 above. If we look at the second column of Table 2 located under Observation 3, we notice a superficial resemblance to the Binary System of enumeration. For ease of reference I have recreated a portion of Table 2 below in Table 5.




Table 5: Sequences Generated by Members of the Even Subset of 2n
Integers from Even Subset of 2n, e

4
8
12
16
20
24
28
32
36
40
…
Sequence generated by iterating Even Rule

4→2→1
8→4→2→1
12→6→3
16→8→4→2→1
20→10→5
24→12→6→3
28→14→7
32→16→8→4→2→1
36→18→9
40→20→10→5
…


The sequence on each row takes the form 4n → 2n → n → n …→n. A new “n” is added at intervals described by 2n, where n takes values from {0,1,2,3,…}. This should sound familiar and indeed the new n is added when an ankin appears. If we were to look only at the sequences generated by ankins, we will immediately see the similarity to the Binary System.
To further elucidate this similarity let us look at the functionality of the Binary System of enumeration.

A number expressed in Binary is a string of 0’s and 1’s, each of which define a location with a place value. Each location can hold either a “0” or a “1”; further each place value is described by a power of 2. When the two options have been exhausted we need to introduce a new place to express values greater than that particular location can express. For example, in the 20 place, we cannot express numbers greater than 1. To denote 2 we need the 21 place. With these two places we can express numbers from 0 through 3.


……_ _ _ _ _ _ _ _ _ _……..

…….210 29 28 27 26 25 24 23 22 21 20………..

Number 3 expressed in binary: 11
(21 * 1 ) + (20 * 1) = 3

In the Binary System, when a new place is added, a one-higher power of two is introduced. Remember, ankins occur at intervals of 2n. Thus, at each ankin, we get a new n-place added to the reducing sequence. This is nothing more than a fancy way of saying that for each ankin the number of subsequent evens increases by one from the preceding ankin.

In the Binary System of enumeration a new place is generated when the existing places are insufficient to express the number we are attempting to write in Binary. Although this is not an issue with the sequences depicted in Table 5, we can use this idea to come to grips with understanding the pattern of numbers in the third column (number of subsequent evens) and fourth column (number of Even Rule applications) of Table 4. First we notice in Table 4 that each interval repeats all the preceding intervals in a sequential order beginning with the first interval and continuing (not at all what happens in the Binary System); the feature that interests us with respect to the Binary System is the changing of the last number in each interval. The last number is associated with the ankin marking the interval. This number increases by an increment of one from the last number in the preceding interval. In short, the changing of the exponent, increase of the last number in the intervals described in Table 4 and adding another term to the sequence generated by iteration of the Even Rule on members of the Even Subset of 2n, described in Table 5, are intertwined. (Remember, the sequences in Table 5 represent the subsequent even integers that will follow any particular member of the Even Subset of 2n.) We can now attempt to explain the pattern of numbers visible in columns three (number of subsequent evens) and four (number of Even Rule applications) of Table 4. In each interval of Table 4 after all numbers but the last have been repeated, the last number is increased by one. This change reflects the appearance of an ankin. Ankins are described by powers of two. As the exponent increases, the number of Even Rule applications and the number of subsequent evens also increase. The periodicity of this change is reflected in the number of places in the sequences of Table 5 (nothing other than the actual subsequent even integers following the given integer in first column), and in the intervals of Table 4.

It seems inescapable that the likelihood of even integers with some number of subsequent evens appearing in a Hailstone Sequence is very high. For example, we can see from Table 3 that each interval is populated with numbers of subsequent evens from all the intervals preceding it. For example, the 7th interval contains the number of subsequent evens (number of Even Rule applications) from intervals 1 through 6 with only the last number in the interval modified to reflect the identity of the interval. This means that in any particular interval it is possible to find not simply even integers that will result in one subsequent even entry in the Hailstone Sequence but even integers that will result in 2, 3, 4, etc.


Observation 5. How Odd Numbers Behave In the Collatz Problem: Thus far we have looked in detail at the behavior of even integers with respect to the Collatz Problem. If we turn our attention to how odd integers behave with respect to the Collatz Problem we discover similar patterns. Table 6 below presents information on the first 171 odd integers. Columns 2 and 4 of Table 6 are self-explanatory. Note that for Odd Integers the number of subsequent evens and number of Even Rule applications are equal.

How Column 1 works: Let us consider the set of odd integers, the 2n+1 Set. Let us divide the 2n+1 Set into two subsets.

2n+1 Set where n Z+: {2n+1 ‌ n = {1,2,3,4,5,6,7,8….}


Odd Subset of 2n + 1 Even Subset of 2n + 1
n Z+: {2n+1 ‌ n = {1,3,5,7,….} n Z+: {2n+1 ‌ n = {2,4,6,8,….}

Integers belonging to the Odd Subset of 2n+1 are followed by only one even integer; integers belonging to the Even Subset of 2n+1 are followed by two or more even integers.

How Column 3 works: it takes the odd Integer in column 2, first applies the Odd Rule and then iterates the Even Rule until an odd integer appears as a term in the ensuing sequence.





Table 6: Odd Integers (2n+1 Set) with Information regarding Salient Characteristics with Respect to the Collatz Problem
Odd/Even
Subset of 2n + 1

E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
O
E
…
Odd Integers


1
3
5
7
9
11
13
15
17
19
21
23
25
27
29
31
33
35
37
39
41
43
45
47
49
51
53
55
57
59
61
63
65
67
69
71
73
75
77
79
81
83
85
87
89
91
93
95
97
99
101
103
105
107
109
111
113
115
117
119
121
123
125
127
129
131
133
135
137
139
141
143
145
147
149
151
153
155
157
159
161
163
165
167
169
171
173
175
177
179
181
183
185
187
189
191
193
195
197
199
201
203
205
207
209
211
213
215
217
219
221
223
225
227
229
231
233
235
237
239
241
243
245
247
249
251
253
255
257
259
261
263
265
267
269
271
273
275
277
279
281
283
285
287
289
291
293
295
297
299
301
303
305
307
309
311
313
315
317
319
321
323
325
327
329
331
333
335
337
339
341
…
Sequence Generated by Application of Odd and Even Rules



1→4→2→1
3→10→5
5→16→8→4→2→1
7→22→11
9→28→14→7
11→34→17
13→40→20→10→5
15→46→23
17→52→26→13
19→58→29
21→64→32→16→8→4→2→1
23→70→35
25→76→38→19
27→82→41
29→88→44→22→11
31→94→47
33→100→50→25
35→106→53
37→112→56→28→14→7
39→118→59
41→124→62→31
43→130→65
45→136→68→34→17
47→142→71
49→148→74→37
51→154→77
53→160→80→40→20→10→5
55→166→83
57→172→86→43
59→178→89
61→184→92→46→23
63→190→95
65→196→98→49
67→202→101
69→208→104→52→26→13
71→214→107
73→220→110→55
75→226→113
77→232→116→58→29
79→238→119
81→244→122→61
83→250→125
85→256→128→64→32→16→8→4→2→1
87→262→131
89→268→134→67
91→274→137
93→280→140→70→35
95→286→143
97→292→146→73
99→298→149
101→304→152→76→38→19
103→310→155
105→316→158→79
107→322→161
109→328→164→82→41
111→334→167
113→340→170→85
115→346→173
117→352→176→88→44→22→11
119→358→179
121→364→182→91
123→370→185
125→376→188→94→47
127→382→191
129→388→194→97
131→394→197
133→400→200→100→50→25
135→406→203
137→412→206→103
139→418→209
141→424→212→106→53
143→430→215
145→436→218→109
147→442→221
149→448→224→112→56→28→24→7
151→454→227
153→460→230→115
155→466→233
157→472→236→118→59
159→478→239
161→484→242→121
163→490→245
165→496→248→124→62→31
167→502→251
169→508→254→127
171→514→257
173→520→260→130→65
175→526→263
177→532→266→133
179→538→269
181→544→272→136→68→34→17
183→550→275
185→556→278→139
187→562→281
189→568→284→142→71
191→574→287
193→580→290→145
195→586→293
197→592→296→148→74→37
199→598→299
201→604→302→151
203→610→305
205→616→308→154→77
207→622→311
209→628→314→157
211→634→317
213→640→320→160→80→40→20→10→5
215→646→323
217→652→326→163
219→658→329
221→664→332→166→83
223→670→335
225→676→338→169
227→682→341
229→688→344→172→86→43
231→694→347
233→700→350→175
235→706→353
237→712→356→178→89
239→718→359
241→724→362→181
243→730→365
245→736→368→184→92→46→23
247→742→371
249→748→374→187
251→754→377
253→760→380→190→95
255→766→383
257→772→386→193
259→778→389
261→784→392→196→98→49
263→790→395
265→796→398→199
267→802→401
269→808→404→202→101
271→814→407
273→820→410→205
275→826→413
277→832→416→208→104→52→26→13
279→838→419
281→844→422→211
283→850→425
285→856→428→214→107
287→862→431
289→868→434→217
291→874→437
293→880→440→220→110→55
295→886→443
297→892→446→223
299→898→449
301→904→452→226→113
303→910→455
305→916→458→229
307→922→461
309→928→464→232→116→58→29
311→934→467
313→940→470→235
315→946→473
317→952→476→238→119
319→958→479
321→964→482→241
323→970→485
325→976→488→244→122→61
327→982→491
329→988→494→247
331→994→497
333→1000→500→250→125
335→1006→503
337→1012→506→253
339→1018→509
341→1024→512→256→128→64→32→16→8→4→2→1
…
Number of SE/ER
Application

2
1
4
1
2
1
3
1
2
1
6
1
2
1
3
1
2
1
4
1
2
1
3
1
2
1
5
1
2
1
3
1
2
1
4
1
2
1
3
1
2
1
8
1
2
1
3
1
2
1
4
1
2
1
3
1
2
1
5
1
2
1
3
1
2
1
4
1
2
1
3
1
2
1
6
1
2
1
3
1
2
1
4
1
2
1
3
1
2
1
5
1
2
1
3
1
2
1
4
1
2
1
3
1
2
1
7
1
2
1
3
1
2
1
4
1
2
1
3
1
2
1
5
1
2
1
3
1
2
1
4
1
2
1
3
1
2
1
6
1
2
1
3
1
2
1
4
1
2
1
3
1
2
1
5
1
2
1
3
1
2
1
4
1
2
1
3
1
2
1
10
…

Before we start analyzing the patterns in Table 6, let us take a moment to reconsider some of the salient points made in the earlier observations. From Observation 1 we know that an odd integer in a Hailstone Sequence is followed by an even integer term in the sequence. In other words, the application of the Odd Rule to an odd integer entry in a Hailstone Sequence will result in the subsequent entry in the sequence being even. From Observation 2 we know that an even integer in a Hailstone Sequence can be followed by either an even term or an odd term. Observation 3 divides the set of even integers, the 2n Set, into two subsets: the Odd Subset of 2n consisting of integers which when divided by two go immediately to an odd, and the Even Subset of 2n consisting of integers which when divided by two go to another even. Observation 3 went on to show there are even integers that are followed by one even, two evens, three evens, etc. Observation 4 delved into the frequency of the occurrence of even integers that are followed by one or more even integers and we discovered that this happens in a periodic manner that could best be described in terms of the 2x Product Formula: – i.e. (2x)n, where x Z+: {x = 1,2,3,….} and n Z+: {n = 1,3,5,7,….}. Ankins occur at every 2x, where the variable n is fixed to 1. When the variable x is fixed and n is allowed to vary, we pick out all the even integers which have the same number of subsequent evens (or same number of Even Rule applications). For example if 25 is an ankin and has 4 subsequent evens (5 Even Rule applications), then the integers (25)2, (25)3, (25)4, (25)5, … will also have the same two characteristics. Finally it was pointed out that if we look at the Even Subset of 2n the integers that occur between any two ankins cycle through the possible values that these two characteristics have taken in the previous interval. By looking at Table 6 we can see that there is a consistent pattern revolving around the number of subsequent evens associated with an odd integer. This should not be surprising since the Odd Rule stipulates that an odd integer will produce an even integer as the following term. This even integer can belong to either the Odd Subset of 2n or the Even Subset of 2n. Earlier we had looked at these two subsets in isolation without taking into consideration odd integers. The question before us now is twofold: First, what are the discernible patterns of the 2n +1 Set; second, how do the patterns we had seen in the 2n Set play out in the 2n + 1 Set given the parameters of the Collatz Problem.

Salient patterns discernible in Table 6:

1) As we glance down the first column we can notice the regular alternation between “E” and “O”. This has two renderings. The first conclusion one can draw from this is that members of the 2n + 1 Set alternate between belonging to the Odd or Even Subsets of 2n+1. The second conclusion one can draw is that if an integer belongs to the Odd Subset of 2n +1 then upon processing by the Odd Rule, it will go to an even integer in the Odd Subset of 2n.

Subsets of 2n + 1 Set

After Application of Odd Rule
Subsets of 2n Set
Odd Subset of 2n+1

Goes to a member of the
Odd Subset of 2n
Even Subset of 2n+1
Goes to a member of the
Even Subset of 2n


2) The following expression picks out members of the Even Subset of 2n+1 from Z+:

4n + 1, where n {0,1,2,3,…..}

Using this formula, the first few members of the Even Subset of 2n+1 are {1,5, 9,13,…}. In contrast, compare this to the formula to pick out members of the Even Subset of 2n: 4n, n {0,1,2,3,…}; the first few members of the Even Subset of 2n are {4,8,12,16,….}.

3) Let’s recall the formal definition of the set of ankins: x Z+: {2x ‌ x = {2,3,4,5,6,7, 8….}}. We notice that in the 2n+1 Set not all ankins are represented – in fact only ankins of the even exponents are represented: x Z+: {2x ‌ x = {2,4,6,8….}}. Table 7 below organizes this data for the first few elements of the 2n+1 Set.


Table 7
Odd Integers that go to an Ankin

1
5
21
85
341
…

Ankin associated with Odd Integer

4
16
64
256
1024
…

A recursive formula to derive ankins associated with the odd integers can also be suggested: 4n + 1, where n is the prior odd integer associated with an ankin. In other words to find the next odd integer associated with an ankin after 1 substitute 1 into the recursive formula to get 5. To find the next odd integer after 5 that is associated with an ankin, use 5 as the value for n - the result is 21. And so on…

4) The following is a list of formulas to determine the number of even integers that will follow an odd integer. As with other tables in this paper the following table is not meant to be comprehensive but is presented to indicate emergent patterns.

Table 8
Number of Subsequent Evens

1 even


2 even



3 even



4 even



5 even







….
Definition of Subset

2n+1, n = {1,3,5,7,9,…},
i.e. the 2n+1 Set

2n+1, n = {0,4,8,12,16,…}
each successive member of the set n takes values from increases by 4

2n+1, n = {6,14,22,…}
each successive member of the set n takes values from increases by 8

2n+1, n = {2,18,34,50,66,…}
each successive member of the set n takes values from increases by 16

2n+1, n = {26,58,90,122,…}
each successive member of the set n takes values from increases by 32

…
Alternative Definition

None


4n+1, n = {0,2,4,6,8,…}
each successive member of the set n takes values from increases by 2

4n+1, n = {3,7,11,…}
each successive member of the set n takes values from increases by 4

4n+1, n = {1,9,1725,33,…}
each successive member of the set n takes values from increases by 8

4n+1, n = {13,29,45,61,…}
each successive member of the set n takes values from increases by 16

….


Table 8 reveals that odd integers followed only by one even belong to the Odd Subset of 2n+1. The Even Subset of 2n+1 seems to be divided into further subsets. This is as we expect from our discussion of the Even Subset of 2n. Recall, the Even Subset of 2n is divided into subsets based on the 2x Product formula:
(2x)n

where x is an exponent of 2 and x Z+: {x = 1,2,3,….},
and n Z+: {n = 1,3,5,7,….}

Each value x takes defines a smaller subset of the Even Subset of 2n. For example:
Integers having the form (23)n where n Z+: {(23)n ‌ n = {1, 3, 5, 7, 9, ….}} will be followed two even integers (initiate 3 applications of the Even Rule) were it to appear in a Hailstone Sequence.

While the actual definitions of the subsets of the Even Subset of 2n+1 in the second column of Table 8 do not feature powers of two, we can see that powers of two are at play in two places: the set n takes values from and the actual members of the subsets as defined. Given the first member of the subset n takes values from, the remaining members of the set n takes values from are generated by using a power of 2. Another place where we can see powers of two at play is in the actual members of the subsets of 2n+1. Remember these subsets pick out odd integers with the same number of subsequent evens (same number of Even Rule applications). Table 9 below lists these members and also reveals how they increase by providing the recursion number at the bottom of the column.

Table 9: Members of a Few 2n+1 Subsets
1 Even

3
7
11
15
19
…
Recursion No.:
4( = 22)
2 Even

1
9
17
25
33
…
Recursion No.:
8( = 23)
3 Even

13
29
45
61
77
…
Recursion No.:
16( = 24)
4 Even

5
37
69
101
133
…
Recursion No.:
32( = 25)
5 Even

53
117
181
245
309
…
Recursion No.:
64( = 26)

5) Last we have the patterns that emerge from analyzing the number of subsequent evens that follow an odd integer. The first column identifies the interval. The second column identifies the those odd integers that go to an ankin upon application of the Even Rule. The third column lists the number of subsequent even integers that follow each integer in the interval. The fourth column lists the number of Even Rule applications that will occur for each integer in the interval. The fifth column lists the number of integers in each interval.

Table 9: Occurrence of the Number of Subsequent Even Integers/Even Rule Applications
Interval



1st

2nd

3rd

4th


5th

Odd→Ank



1→4

5→16

21→64

85→256


341→1024


Occurrence of Number of
Subsequent Even Integers


2

1 4

1 2 1 3 1 2 1 6

1 2 1 3 1 2 1 4 1 2 1 3
1 2 15 1 2 1 3 1 2 1 4
1 2 1 3 1 2 1 8

1 2 1 3 1 2 1 4 1 2 1 3
1 2 1 5 1 2 1 3 1 2 1 4
1 2 1 3 1 2 1 6 1 2 1 3
1 2 1 4 1 2 1 3 1 2 1 5
1 2 1 3 1 2 1 4 1 2 1 3
1 2 1 7 1 2 1 3 1 2 1 4
1 2 1 3 1 2 1 5 1 2 1 3
1 2 1 4 1 2 1 3 1 2 1 6
1 2 1 3 1 2 1 4 1 2 1 3
1 2 1 5 1 2 1 3 1 2 1 4
1 2 1 3 1 2 1 10
Number of Applications of Even Rule


2

1 4

1 2 1 3 1 2 1 6

1 2 1 3 1 2 1 4 1 2 1 3
1 2 1 5 1 2 1 3 1 2 1 4
1 2 1 3 1 2 1 8

1 2 1 3 1 2 1 4 1 2 1 3
1 2 1 5 1 2 1 3 1 2 1 4
1 2 1 3 1 2 1 6 1 2 1 3
1 2 1 4 1 2 1 3 1 2 1 5
1 2 1 3 1 2 1 4 1 2 1 3
1 2 1 7 1 2 1 3 1 2 1 4
1 2 1 3 1 2 1 5 1 2 1 3
1 2 1 4 1 2 1 3 1 2 1 6
1 2 1 3 1 2 1 4 1 2 1 3
1 2 1 5 1 2 1 3 1 2 1 4
1 2 1 3 1 2 1 10
# Int
Intvl


1

2

8

32


128

Table 9 shares a lot in common with Table 4 presented and discussed in Observation 4. For this reason I will forego an extensive discussion of the patterns in Table 9 since I have already gone on at length about it in the discussion following Table 4. It should suffice to point out some major differences and point out similarities. First we shall point out the differences. The number of integers in each interval listed in the fifth column seem to increase by 22x, x = {0,1,2,3,…}. This seems to go hand in hand with the fact that only the even exponent ankins appear in the 2n+1 Set. Second, the column representing the occurrence of the number of Even Rule applications is identical to the column representing the occurrence of the number of subsequent evens – different from Table 4 where number of subsequent evens is one less than the number of Even Rule applications. Now let us consider the similarities in the two tables. Both tables reveal a periodicity in the appearance of certain numbers in each of the intervals. Further columns three and four of Table 9 repeat the numeric data in column three of Table 4. This is not surprising since what happens to the set of even integers has to be reflected in the set of odd integers.


Conclusion

Let us summarize our findings. Observation 1 established that the application of the Odd Rule results in an even integer as the next term in the Hailstone Sequence. Observation 2 established that the application of the Even Rule results in either an even integer or an odd integer as the next term in the Hailstone Sequence. Observation 3 established a number of related facts regarding the occurrence of odd and even integers in the Hailstone Sequence. First it clarified exactly when an even integer is followed by an even or odd integer in the Hailstone Sequence. An even integer from the Odd Subset of 2n will be followed by an odd integer in the Hailstone Sequence. An even integer from the Even Subset of 2n will be followed by one or more even integers in the Hailstone Sequence. As a result, a Hailstone Sequence will see periods where it bobs, alternating between increasing and decreasing even integers and odd integers as well as periods where it is decreasing when clusters of even integers adjacent to each other occur. The ramification of this observation is that the increasing tendency we noted when the Odd Rule is iterated by itself to generate a sequence doesn’t get much opportunity to exercise its influence in a Hailstone sequence. When a cluster of even integer terms appears in a Hailstone Sequence the application of the Odd Rule is held at bay until an odd integer occurs once again in the sequence. Observation 3 established that the Even Subset of 2n itself is compartmentalized into subsets, grouping together even integers with the same number of subsequent even terms. Further, even integers iterated using the Even Rule that reduce to 4 2 1 were identified as ankins. Observation 4 went into detail regarding the ubiquitous presence of even integers that are followed by other evens that it seemed inevitable that they would turn up in a Hailstone Sequence. Observation 5 presents a number of patterns in the 2n+1 Set that mirror patterns in the 2n Set.

We could go into all sorts of relationships between the 2n Set and the 2n+1 Set but what strikes me as important in looking at all these patterns is to show that both 2n Set and the 2n+1 Set have members that go to an ankin or are ankins or have multiple subsequent evens. It seems then for any integer, q, in Z+, the Hailstone Sequence generated by q will have periods which bob and periods which are decreasing – i.e. periods where a mini-decreasing sequence is embedded within a Hailstone Sequence. Second, since a Hailstone Sequence decreases to 4 2 1 and an ankin also reduces to 4 2 1, it seems fair to postulate that all Hailstone Sequences will see an ankin appear as a term. That leaves the question of determining the relationship between ankin and Z+ with respect to the Collatz Problem. For example the integers 3, 5, 6, 7, 9,10, 11, 12, 13, 14, 15 all eventually see the ankin 16 appear as a term in the Hailstone Sequence they generate. There are probably others and this listing is not meant exhaustively; however, what can be gleaned by looking at this listing is that it is not necessary for each integer to have associated with it a unique ankin.


References:

Eric W. Weisstein. "Collatz Problem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/CollatzProblem.html – last accessed April 11, 2005

Erik Roosendaal. “On the 3x + 1 Problem.” http://www.ericr.nl/wondrous/index.html – last accessed July 3, 2005.

Anton, H. Calculus: A New Horizon. 6th Edition. New York: John Wiley and Sons, Inc. 1999. pp. 616-632

H. Chad Lane. “The Hailstone Series” (Computer Science Class Project Assignment Sheet) http://www.cs.pitt.edu/~hcl/pdt/logs/HailstoneSummary.html

http://www.utah.edu/utahlogic/misc/hailstone.html – last accessed April 11, 2005

http://mathworld.wolfram.com/HailstoneNumber.html – last accessed April 12, 2005
[1] Eric W. Weisstein. "Collatz Problem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/CollatzProblem.html – last accessed April 11, 2005

[2] See for example, http://www.utah.edu/utahlogic/misc/hailstone.html – last accessed April 11, 2005 and http://mathworld.wolfram.com/HailstoneNumber.html – last accessed April 12, 2005
[3] Erik Roosendaal. “On the 3x + 1 Problem.” http://www.ericr.nl/wondrous/index.html – last accessed July 3, 2005.
[4] H. Chad Lane. “The Hailstone Series” (Computer Science Class Project Assignment Sheet) http://www.cs.pitt.edu/~hcl/pdt/logs/HailstoneSummary.html
[5] Anton, H. Calculus: A New Horizon. 6th Edition. New York: John Wiley and Sons, Inc. 1999. pp. 616-632
[6] Roosendaal calls the repeating integers 4,2,1 a cycle. Erik Roosendaal. “On the 3x + 1 Problem.” http://www.ericr.nl/wondrous/index.html - accessed April 11, 2005
[7] Although the numbering of observations is just a method for keeping track I have attempted to arrange them in a logical progression.
[8] Alternatively, 2x – 1: 3(an) + 1 → 3(2x - 1) + 1 → 6x - 3 + 1 → 6x - 2 → 2(3x - 1) → if we let xk = (3x - 1), then 2(3x-1) becomes 2xk which is nothing other than a form of 2x.
[9] You could pick another member, but then you will need to perform subtractions as well to capture all members in the subset from Z+.
[10] Earlier I had mentioned that n will be taking va
lues from its range in the sequence they occur beginning with 1 (i.e. 1,3,5,7, etc). The ordering relies on the natural ordering of the set of positive integers.