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