## The Collatz Problem

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 🙂

## Leave a Reply