Skip to content

Latest commit

 

History

History
35 lines (28 loc) · 1.67 KB

README.md

File metadata and controls

35 lines (28 loc) · 1.67 KB
Raw

collatz-tree

Python class to examine lists of numbers generated by the Collatz conjecture algorithm.

A tree of numbers is stored such that the parents are the previous and children are the next terms in the sequence. Children and parents are not guaranteed to be in numerical order. Terms are calulated as follows:

  1. If a_n is 1, stop.
  2. If a_n is even, then a_(n+1) = (a_n)/2
  3. If a_n is odd, then a_(n+1) = 3(a_n) + 1

The Collatz conjecture states that all sequences will eventually lead to 1.

Public methods:

  • add -- add n and its sequence to 1 to the tree
  • fill -- add all numbers up to n and their paths to 1 to the tree
  • fill_sequences -- calculates (if needed) and stores all sequences of numbers in the tree to 1
  • get_sequence -- returns the list of numbers in the sequence from n to 1
  • longest_sequence -- returns longest sequence to 1 for numbers in the tree
  • stopping_time -- returns the stopping time of n (length of the sequence from n to 1)
  • save_list -- save the current tree and path structure to file (pickle)
  • load_list -- load a tree and path structure from file (pickle)

Non-public mehtods:

  • _calc_sequence -- calculate and store the sequence from n to 1
  • _info -- print debugging information to the console (if verbose == True)

Instance variables:

  • collatz_tree -- dict; each pair represents {parent: child} such that collatz(parent) = child
  • seqs -- dict; each pair represents {number: sequence}, where sequence is a list
  • verbose -- turns on debugging information printed to console

Static function:

  • collatz_sequence -- generate the Collatz sequence from n to 1; return list

See https://en.wikipedia.org/wiki/Collatz_conjecture for more details.