1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
### Remarks
The program is run with a positive integer as an argument, e.g.,
```shell
ruby entry.rb 27
```
It has been confirmed to be run on
```
ruby 1.9.3p385 (2013-02-06 revision 39114) [x86_64-darwin11.4.2]
ruby 2.0.0p481 (2014-05-08 revision 45883) [universal.x86_64-darwin13]
ruby 2.2.3p173 (2015-08-18 revision 51636) [x86_64-linux]
```
### Description
The program prints a Collatz sequence started with a given number,
that is, it repeatedly outputs numbers obtained by applying the
following Half-Or-Triple-Plus-One (HOTPO) process to the previous
number:
> If the number is even, divide it by two, otherwise, multiply it by three and add one.
until the number becomes 1. Collatz conjectured that no matter from
the process starts it always eventually terminates. This is still
an open problem, hence the program may not terminate for some
numbers. It is known that there is no such exception below 2<sup>60</sup>.
### Internals
The source code does not contain either conditional branch or arithmetic operation.
The trick shall be revealed step by step.
First, the code is obfuscated by using `%`-notations,
`*`(String#join), `%`-formatting, restructuring, and so on.
Here is an equivalent readable program:
```ruby
n = ARGV[0].to_i
begin
# do nothing
end while begin
puts n
n = (/(.)...\1=/ =~ eval('[",,,,,"'+ '",'*n + ' ?=].join#"].join("3x+1?")'))
end
```
The line
```ruby
n = (/(.)...\1=/ =~ eval('[",,,,,"'+ '",'*n + ' ?=].join#"].join("3x+1?")'))
```
performs the HOTPO process.
The `eval` expression here returns a string as explained in detail later.
Since *regex*`=~`*str* returns index of first match of *regex* in *str*,
the regular expression `(.)...\1` must match the string
at index `n/2` if `n` is even and
at `3*n+1` if `n` is odd greater than 1.
The match must fail in the case of `n = 1` so that it returns `nil`.
The key of simulating the even-odd conditional branch on `n` in the
HOTPO process is an `n`-length sequence of the incomplete fragments
`",` where the double-quote `"` changes its role of opening/closing
string literals alternately. If `n` is even, the string in the `eval`
expression is evaluated as
```ruby
=> '[",,,,,"'+ '",' + '",' + '",' + ... + '",' + ' ?=].join#...'
=> '[",,,,,"",",",...", ?=].join#...'
```
where the last double-quote `"` is closing hence the code after `#` is
ignored as comments. Note that `"ab""cd"` in Ruby is equivalent to
`"abcd"`. Therefore the `eval` expression is evaluated into
```ruby
",,,,,...,="
```
where the number of commas is `5+n/2`.
As a result, the regular expression `(.)...\1=` matches `,,,,,=`
at the end of string, that is, at index `5+n/2-5 = n/2`.
If `n` is odd, the string in the `eval` expression is evaluated as
```ruby
=> '[",,,,,"'+ '",' + '",' + '",' + '",' + ... + '",' + ' ?=].join#"].join("3x+1?")'
=> '[",,,,,"",",",",...,", ?=].join#"].join("3x+1?")'
```
where the last element in the array is `", ?=].join#"`. Threfore the
`eval` expression is evaluated into
```
",,,,,,3x+1?,3x+1?,...,3x+1?, ?=].join#"
```
where the number of `,3x+1?` is `(n-1)/2`. As a result, the regular
expression `(.)...\1=` matches `?, ?=` at the almost end of string,
that is, at index `5+(n-1)/2*6-1 = 3n+1`, provided that the match
fails in the case of `n = 1` because the symbol `?` occurs only once
in the string.
One may notice that the string `3x+1` in the code could be other
four-character words. I chose it because the Collatz conjecture is
also called the 3x+1 problem.
### Variant
The Collatz conjecture is equivalently stated as,
> no matter from the HOTPO process starts, it always eventually
reaches the cycle of 4, 2, and 1
instead of termination of the process at 1. This alternative
statement makes the program simpler because we do not have to care the
case of n = 1. It can be obtained by replacing the regular expression
is simply `/=/` and removing a padding `",,,,,"`. The program no
longer terminates, though.
### Limination
The implementation requires to manipulate long strings even for some
small starting numbers. For example, starting from 1,819, the number
will reach up to 1,276,936 which causes SystemStackError on Ruby 1.9.3.
The program works on Ruby 2.0.0 and 2.2.3, though.
|
