An Improved Bound for Nontrivial Cycle Lengths in the 3n+1 Problem

Wednesday, March 18, 2015 - 15:30 to 16:30
703 Thackeray
Speaker Information
Ian Martiny
Graduate Student
University of Pittsburgh

Abstract or Additional Information

An easy to understand, yet open and very difficult Number Theory problem is the 3n+1 Problem.  This conjecture has many names including the Collatz Conjecture and the Syracuse Problem and is interesting in that many different techniques have been used to tackle it including dynamical systems, ergodic theory, and stochastic modelling.  The conjecture is based upon the following iteration: for any positive integer n, T(n) = n/2 if n is even or (3n+1)/2 if n is odd.  A sequence is formed by reapplying T, e.g. 7, 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1,2, 1,...(forming these sequences is a homework excerise in Stewart's Calculus text).  The conjecture states that for all positive integers n the sequence formed by interating by T [ viz. n, T(n), T(T(n)), ...] always reaches the trivial cycle 2,1.  The conjecture has been verified by computer for n < 5 * 2^60.  A partial result on the conjecture is showing the minimal size of any non-trivial cycle is the 1993 paper of Shalom Eliahou which establishes any non trivial cycle has length at least 17,087,915.  In this talk this lower bound is improved to 10,439,860,591 using an argument dependent upon continued fractions.