Debian Codegraph @

sample/trick2015/ksk_1/remarks.markdown

raw
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