OKlibrary  0.2.1.6
Collatz.mac
Go to the documentation of this file.
```00001 /* Oliver Kullmann, 9.12.2012 (Swansea) */
00002 /* Copyright 2012, 2013 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007
00022 oklib_include("OKlib/ComputerAlgebra/Trees/Lisp/Basics.mac")\$
00023 oklib_include("OKlib/ComputerAlgebra/Trees/Lisp/Visualisation.mac")\$
00024
00025
00026 /* For n > 1: */
00027 collatz_reduction(n) := if evenp(n) then n/2 else 3*n+1\$
00028 /* For n >= 1: */
00029 collatz_redseq(n) := if n=1 then [1] else
00030  cons(n, collatz_redseq(collatz_reduction(n)))\$
00031 /* The number of reductions and the maximal number reached: */
00032 collatz_basics(n) := block([R : collatz_redseq(n)],
00033  [length(R)-1, lmax(R)])\$
00034
00035
00036 /* Condensing the "Collatz graph"
00037    http://en.wikipedia.org/wiki/Collatz_conjecture#In_reverse :
00038 */
00039
00040
00041 /* Those n >= 1 for which there are possibly two different m with
00042    collatz_reduction(m) = n:
00043 */
00044 collatz_switch_p(n) := is(n >= 0 and evenp(n) and mod(n,3)=1)\$
00045 /* For a switch-number n (with collatz_switch_p(n) = true) the list
00046    of immediatly previous switches, with 4*n first:
00047 */
00048 collatz_prevswitch(n) := if n=4 then [4*n] else
00049  block([p1 : 4*n, d : (n-1)/3, m],
00050   m : mod(d,3),
00051   if m=0 then [p1]
00052   elseif m=1 then [p1, 4*d]
00053   else [p1, 2*d])\$
00054
00055 /* For a switch-number n, the rooted tree of previous switches up to
00056    height k >= 0:
00057 */
00058 collatz_prevswitch_lrt_g(k, n) :=
00059  if k=0 then [n]
00060  else cons(n, map(lambda([m], collatz_prevswitch_lrt_g(k-1, m)),
00061                   collatz_prevswitch(n)))\$
00062 /* The full tree: */
00063 collatz_prevswitch_lrt(k) := collatz_prevswitch_lrt_g(k, 4)\$
00064 /* Drawing that tree: */
00065 draw_collatz_prevswitch_lrt(k) :=
00066  draw_lrt_dbl(collatz_prevswitch_lrt(k+1), d:k+1, fc:white)\$
00067
00068 /* The respective listing of the nodes, level-wise: */
00069 collatz_prevswitch_l(k) := levelorderl_lrt(collatz_prevswitch_lrt(k))\$
00070
00071 /* Instead of considering the switches 4,10,16,22 etc., one can reduce them
00072    to 1,2,3,4 etc.:
00073 */
00074 collatz_redswitch(n) := (n+2)/6\$
00075 collatz_prevswitchred_lrt(k) :=
00076  lmap_lrt(collatz_prevswitch_lrt(k), collatz_redswitch)\$
00077 draw_collatz_prevswitchred_lrt(k) :=
00078  draw_lrt_dbl(collatz_prevswitchred_lrt(k+1), d:k+1, fc:white)\$
00079
00080 collatz_prevswitchred_l(k) := levelorderl_lrt(collatz_prevswitchred_lrt(k))\$
00081
00082
00083 /* Remark:
00084    Let T be the infinite rooted tree obtained as union of all
00085    collatz_prevswitchred_lrt(k) for k >= 0.
00086    By definition, only natural numbers >= 1 occur in T, and no number
00087    occurs more than once.
00088    The "Collatz Conjecture" http://en.wikipedia.org/wiki/Collatz_conjecture
00089    is equivalent to the statement, that all natural numbers actually occur.
00090 */
00091
00092 /* The rightmost branch in collatz_prevswitch_lrt(k): */
00093 collatz_prevswitch_rm(k) := block([n:4, res],
00094  res : [n],
00095  while k>0 do (
00096    n : last(collatz_prevswitch(n)),
00097    res : cons(n, res),
00098    k : k-1
00099  ),
00100  reverse(res))\$
00101 /* The rightmost branch in collatz_prevswitchred_lrt(k): */
00102 collatz_prevswitchred_rm(k) :=
00103  map(collatz_redswitch, collatz_prevswitch_rm(k))\$
00104
```