Collatz Sequence – part 4

[This article was first published on NEONIRA, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Find previous posts if you haven’t yet read them. first post, second post, third post, .

Analysis of cluster 1

A reminder first.

cluster 1 is made of numbers with unit digit being part of set S1 = { , , , }.

cluster 1 paths

Reusing results from second post about digit mutation, we can determine all the paths of cluster 1.

Entry point is unique and is a number ending with digit , at the notable exception of the starting number that could be any other number of the cluster.

The typical path is (loop possible here) .

That path is the only one in the cluster. Its length vary considering the loop on and therefore, the expansion factor will vary also according to this condition.

The entry condition in cluster 1 has already been demonstrated on second post, and must own an number of tens to enter the cluster. if not the case, then the will bring and switch to cluster 2.

cluster 1 expansion factor

υn
ntucomputation sequenceexpansion factor
1t is η1 / 2 = 0.5
2ω3
3η1 / 2k <= 0.5
4ω3

So, following the path, brings an expansion factor of 9 / 2k + 1 with k being the number of times we loop on . Forcibly k 1.

if k 3 then expansion factor becomes a compression factor, meaning the output will be less than the input. You may think to k as the number of 0 on the right of the number. So k 3 means the number being a multile of 1000.

Computation analysis

step υn
nhturule to apply
1t is 02468η
2 h – 1 if t = 051234ω
3 h + 1 if t = 3, 4 or 56
k = 2
4
k = 3
7
k = 1
0
k = 3
3
k = 1
η
410321ω
5h + 1 if t = 3 or 441074η

Read vertically, as cases of tens are shown vertically.
So, let’s take a number that ends with digit . Its canonical form is 10 t + 0.

If t is , t = 2p this reduces to 5 p + 0, applying η two times. Now, if p is a further reduction can be applied, and this will happen as long as p / 2 is . Let’s put e this number of times, starting from t input, the total number of times applying η is therefore 1 + e with e 1. a

If t is , t = 2p + 1, this reduces to 5 (2p+ 1) + 0. applying η one time. b

Note that if a number ends with d digits , then the number of times η will be applied is d.

Expansion factor

So the expansion factor turns to be taken from set { 9 / 2k with k = 2 when tens of digit are , and k = 2 + e with e being the number of times those tens can be divided by 2 staying }.

This expansion factor, is really an expansion factor when tens of digit are or when e 2. Otherwise, the expansion factor is a compression factor, meaning that the output of cluster 1 will be in this case a number less than the input number.

Expansion factor pattern

Let’s consider input number 13. Applying ω, it brings 40. Applying η brings successively 40 20 10 5. So e = 3, and the reduction factor applied is 9 / 16.

I will show that the expansion factor follows a clearly defined pattern.

ωn + 1 = 3 ωn + 1     by definition

ωn + 1 = 3 (100 h + 10 t + 3) + 1 = 100 3h + 10 3t + 10 = 100 3h + 10 (3t + 1) + 0

Therefore, input number has t tens, and output number has 3t + 1 tens. Or input number tens have to be taken among { 1, 3, 5, 7, 9 }, leading to following table.

input digit output digit minimum e
input tensoutput tensoutput hundreds
143
30+12
56+12
72+22
98+25

So what’s a surprise! All tens digits of output numbers turns to be , and their respective expansion factors are shown on the table. Following table expresses the final and definitive expansion factors of cluster 1.

input digit cluster 1 impact
input tensminimum factoreffect
19 / 16 = 0.5625reduction
39 / 8 = 1.125expansion
59 / 8 = 1.125expansion
79 / 8 = 1.125expansion
99 / 64 = 0.140625reduction

To leave a comment for the author, please follow the link and comment on their blog: NEONIRA.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)