Pythonism

Writing about my life. When I'm well it's math and code… But when the schizy demon rises it's prose and poetry.

The Collatz Problem

leave a comment »

I played around with this code, built for speed. It’s so simple there’s not even much point in functionalising it, no gain in readability. I will be doing more code to generate OEIS sequences in future, because it’s a nice pastime. I included extensive comments as a vague attempt to embody more of Knuth’s ‘literate programming’ style so that documentation and code are in more of a self-explanatory whole.

#!/usr/bin/python

# The Collatz conjecture is a conjecture in mathematics that concerns a 
# sequence defined as follows: start with any positive integer n. Then 
# each term is obtained from the previous term as follows: if the 
# previous term is even, the next term is one half the previous term. 
# If the previous term is odd, the next term is 3 times the previous 
# term plus 1. The conjecture is that no matter what value of n, the 
# sequence will always reach 1. 

# It is also known as the 3n + 1 conjecture, the Ulam conjecture, 
# Kakutani's problem, the Thwaites conjecture , Hasse's algorithm,
# or the Syracuse problem.

# The sequence of numbers involved is referred to as the hailstone 
# sequence  or hailstone numbers because the values are usually 
# subject to multiple descents and ascents like hailstones in a cloud.

# Paul Erdos said about the Collatz conjecture: "Mathematics may not 
# be ready for such problems." He also offered $500 for its solution.

# This code will generate sequence OEIS: A006877.

# In the Collatz problem, these values for the starting value set new 
# records for number of steps to reach 1. 

results, seed, best = [], 1, 0

while True:

    path_length, term = 0, seed

    while term != 1:
        if term % 2 == 0:
            term /= 2
        else:
            term = term * 3 + 1
        path_length += 1

    results.append((path_length, seed))

    if max(results)[0] > best:
    	print max(results)
        trunc = [max(results), ]
        results = trunc

    best = max(results)[0]
    seed += 1

Here’s a plot of the first few… “Linear, moi?” 😉

===========

Regarding the elusive proof of the Collatz Problem, one might be forgiven for forming an intuition that the path length will grow steadily to infinity as the seed number increases. Also of course for all these numbers (I tested under approximately 2,000,000) there was not a single counterexample. If such was found it would, of course, be a sufficient disproof without any further explanation needed. “I refute it thus!”.

Informally one might note that nearly all the record breakers are odd. Is this significant? What about primality? 6 out of 45 of these numbers are prime, 13.3%.

For all numbers below 1.8M roughly 7.5% are prime. A higher preponderance then.

So far my intution is that for any positive integer the sequence will indeed always terminate. But how to prove this. The opposite assertion is that

For some n the process results in a sequence that goes on forever without reaching 1.

Could this be disproved?

Notice that for any starting number that is odd, 3n+1 will always be even, hence the next step will always be to halve. So for any odd number the two steps can be elided into

n → 3n/2 + ½

if, for some number, there is a sequence that diverges, then for continued growth there would have to be more odd than even terms by a ratio of > 4:3

Let’s look at the numbers involved in some of the sequences

when n = 25 we have

76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

Nearly all these are even, certainly greater than 3/7ths which would have to be the case for termination.

Let’s call

n → 3n + 1 step (i)

and

n → n/2 step (ii)

step (i) is what we need to look at if we wish for a counterexample to the rule that every sequence converges. Since (i) always produces an even number we might ask, “how many even numbers are twice odd numbers?”. Well… half of them… but we need at least 4/7ths of the numbers in a given sequence to be odd. Ahh but are the numbers in any of our sequences distributed with the same frequency of occurrence as all the positive integers? If some are found to crop up more often, then the argument won’t work.

By observation, as soon as a power of 2 is reached the process trivialises into a subsequence that ends …, 16, 8, 4, 2, 1. In fact all sequences that do end will show this.

So for our counterexample we might try to find a sequence that never lands on a power of 2.

well, on what occasions will we get a power of 2? whenever the previous number was odd and rule (i) results in it. So for how many odd n does 3n+1 work out as 2^x for some x?

Let’s look at some

1 4
3 10
5 16
7 22
9 28
11 34
13 40
15 46
17 52
19 58
21 64
23 70
25 76
27 82
29 88
31 94
33 100
35 106
37 112
39 118
41 124
43 130
45 136
47 142
49 148
51 154
53 160
55 166
57 172
59 178
61 184
63 190
65 196
67 202

69 208
71 214
73 220
75 226
77 232
79 238
81 244
83 250
85 256
87 262
89 268
91 274
93 280
95 286
97 292
99 298
101 304
103 310
105 316
107 322
109 328
111 334
113 340
115 346
117 352
119 358
121 364
123 370
125 376
127 382
129 388
131 394
133 400
135 406

So when rule (i) is applied to odd numbers there are some powers of 2 that aren’t generated

we have

3 x 1 + 1 = 4
3 x 5 + 1 = 16

but 32 is missed out, as are 128, 512 and endless more. So maybe if there are some non trivial sequences that never hit certain powers of 2 we might find one that diverges. If you look at 128 this is not possible, because there is no preceding number that under rule (i) will ever generate 128 because 127 = 128 – 1 is prime and cannot have factor of 3. so 128 can only feature in trivial cases where the seed is always a power of 2. And these cases always converge.

So of all terminating sequences none of them can ever end.

32, 16, 8, 4, 2, 1

Another way a non-terminating counterexample could be found is to establish that there exists a cyclic loop that will eternally fail to reach 1. I haven’t found one but again, proper mathematical reasoning would be the only thing that would cut the mustard over computer processes that would bog down with big numbers.

It seems that if there are hidden mysterious super-weird numbers out there which act to disprove the hypothesis that they may be so vast that computational searches prove fruitless. (OK, until we invent something as kick-ass as computronium and make a planet sized blob of it…)

Again intuitionally I feel that there will not be just one counterexample, because any larger number than the counterexample can be constructed to non-terminate too, say just by doubling the original number. So if this is followed there must be a smallest non-terminating number. By logic we can see that the sequence it generates has certain provable properties. One is that no integer in the first three terms of the sequence can be a multiple of 4. This is because two successive applications of rule ii would then result in a number smaller than the seed. This can’t happen because as stipulated there can’t be a smaller non-terminating number than the smallest.

But when the numbers sail off towards infinity and start to create the head-boggle so many of us know and love, only a rigorous proof will suffice to settle the matter. Why was Erdos so sure this was such a hard problem? He must have thrown every weapon in his extensive armoury at it and still not got a success.

If I get hooked on this the next step will be to try and introduce reasoning about primes, and possibly use base 2 representations. I didn’t read the Wikipedia until after I’d had a stab or my old tutors would surely have turned in their graves seeing me cheat… but it’s really a lovely problem because you can get to see a fascination which only requires basic arithmetic to encounter.

So I leave it open ended – any ideas??

===========

for more see

https://oeis.org/A006877
https://en.wikipedia.org/wiki/Collatz_conjecture

Happy Christmas 🙂

Advertisements

Written by Luke Dunn

December 23, 2018 at 3:36 pm

Posted in Math, programming

Tagged with , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: