Analyzing Collatz-like sequences - Code Golf Stack Exchange most recent 30 from codegolf.stackexchange.com 2019-07-22T23:40:58Z https://codegolf.stackexchange.com/feeds/question/47221 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://codegolf.stackexchange.com/q/47221 13 Analyzing Collatz-like sequences randomra https://codegolf.stackexchange.com/users/7311 2015-03-01T20:06:31Z 2015-03-02T09:07:52Z <p>We define a <a href="http://en.wikipedia.org/wiki/Collatz_conjecture">Collatz</a>-like sequence <code>s</code> with 4 positive integers:</p> <ul> <li><code>n</code> starting value</li> <li><code>d &gt; 1</code> divisor</li> <li><code>m &gt; 1</code> multiplier</li> <li><code>i</code> increment</li> </ul> <p>(In the original Collatz sequence <code>d = 2</code> <code>m = 3</code> and <code>i = 1</code>.)</p> <p>Given these integers <code>s</code> will be created in the following manner:</p> <ul> <li><code>s(0) = n</code></li> <li>if <code>k &gt; 0</code> and <code>s(k-1) mod d = 0</code> then <code>s(k) = s(k-1) / d</code></li> <li>if <code>k &gt; 0</code> and <code>s(k-1) mod d != 0</code> then <code>s(k) = s(k-1) * m + i</code></li> </ul> <p>An example sequence with <code>d = 2, m = 3, i = 5</code> and <code>n = 80</code> will be <code>s = 80, 40, 20, 10, 5, 20, 10, 5, 20, ...</code>.</p> <p>Every sequence will either reach higher values than any given bound (i.e. the sequence is divergent) or get into an infinite loop if for some <code>t</code> and <code>u</code> (<code>t!=u</code>) the <code>s(t) = s(u)</code> equality will be true.</p> <p>In our problem if the value of a sequence element is larger than <code>10^9</code> or there is no element repetition before the <code>1000</code>th element the sequence is considered divergent.</p> <h2>The task</h2> <p>You should write a program or function which takes the positive integers <code>d</code> <code>m</code> and <code>i</code> as inputs and outputs all the different ending types of the sequences (infinite loops and divergence) which the starting values <code>n = 1, 2, 3, ... 999, 1000</code> can produce.</p> <h2>Input details</h2> <ul> <li>The input is a string or list (or closest equivalent in your language) representing (in the common way) three positive integers <code>d</code>, <code>m</code> and <code>i</code> in that order. <code>d</code> and <code>m</code> are at least <code>2</code>. Neither number is larger than <code>100</code>. </li> </ul> <h2>Output details</h2> <p><em>The output specification is a bit wordy. Might worth to check out the examples first.</em></p> <ul> <li>You should output to the standard output (or closest alternative) or return a string.</li> <li>If divergent sequence is possible the first line should be <code>DIVERGENT</code>.</li> <li>A unique representation of a sequence's loop is it's rotation where the smallest number is the last separated by spaces. E.g. if <code>s = 2 1 4 2 1 4 2 1</code> the loop is <code>4 2 1</code>.</li> <li>In every following line you should output every unique loop exactly once preceded by the word <code>LOOP</code>. E.g. <code>LOOP 4 2 1</code></li> <li>The loops should be in ascending order in regard of their last element.</li> <li>Trailing newline is optional.</li> </ul> <h2>Examples:</h2> <p>The first lines are the inputs and the following ones until a blank line are the outputs.</p> <pre><code>2 3 1 LOOP 4 2 1 2 2 6 LOOP 8 4 2 1 LOOP 12 6 3 3 7 8 DIVERGENT LOOP 15 5 43 309 103 729 243 81 27 9 3 1 LOOP 22 162 54 18 6 2 LOOP 36 12 4 3 9 1 DIVERGENT 6 9 9 DIVERGENT LOOP 18 3 36 6 1 LOOP 27 252 42 7 72 12 2 LOOP 45 414 69 630 105 954 159 1440 240 40 369 3330 555 5004 834 139 1260 210 35 324 54 9 90 15 144 24 4 LOOP 81 738 123 1116 186 31 288 48 8 LOOP 99 900 150 25 234 39 360 60 10 LOOP 126 21 198 33 306 51 468 78 13 10 10 10 LOOP 20 2 30 3 40 4 50 5 60 6 70 7 80 8 90 9 100 10 1 93 91 92 DIVERGENT LOOP 2185 198927 2139 23 LOOP 4278 46 </code></pre> <p><a href="http://ideone.com/OMl6aK">Reference implementation in Python 3 on Ideone.</a></p> <p>This is code-golf so shortest entry wins.</p> https://codegolf.stackexchange.com/questions/47221/-/47227#47227 5 Answer by Sp3000 for Analyzing Collatz-like sequences Sp3000 https://codegolf.stackexchange.com/users/21487 2015-03-02T04:52:08Z 2015-03-02T09:07:52Z <h1>Python 3, <s>269</s> <s>254</s> <s>252</s> 246 bytes</h1> <pre class="lang-py prettyprint-override"><code>d,m,i=eval(input()) S=set() for n in range(1,1001): T=X=() while len(T)**3&lt;1e9&gt;=n: T=(n,)+T;n=[n//d,n*m+i][n%d&gt;0] if n in T:I=T.index;L=T[:I(n)+1];M=I(min(L));X=L[M:]+L[:M] S|={X} for x in sorted(S):print(x and"LOOP"or"DIVERGENT",*x[::-1]) </code></pre> <p><em>(Now 10 times slower to save a few bytes. Typical code golf.)</em></p> <p>Input a list via STDIN (e.g. <code>[2, 3, 1]</code>). I'm thinking that there's got to be a better way of standardising the cycles...</p> <p>The approach is quite straightforward — test all 1000 numbers and take only the unique outputs. However, there are two little tricks in there:</p> <ul> <li><p>Loops are represented by nonempty tuples, but more importantly divergence is represented by an <em>empty</em> tuple. This is good because:</p> <ul> <li>It doesn't break <code>sorted</code>, and will even appear <em>before</em> all the loop tuples</li> <li>It allows us to select a string via <code>x and"LOOP"or"DIVERGENT"</code></li> <li><code>*()[::-1]</code> doesn't affect <code>print</code></li> </ul></li> <li>The loops are built backwards to turn "sort ascending by last element" into "sort ascending by first element", which removes the need to pass a lambda into <code>sorted</code>.</li> </ul> <h2>Previous submission, 252 bytes</h2> <pre class="lang-py prettyprint-override"><code>d,m,i=eval(input()) def f(n,T=()): x=[n//d,n*m+i][n%d&gt;0];I=T.index if x in T:L=T[:I(x)+1];M=I(min(L));return L[M:]+L[:M] return()if(T[1000:]or x&gt;1e9)else f(x,(x,)+T) for x in sorted(set(map(f,range(1,1001)))):print(x and"LOOP"or"DIVERGENT",*x[::-1]) </code></pre> <p>This one's a lot faster.</p>