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