collatz

package module
v0.0.0-...-fef24fa Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 20, 2025 License: Apache-2.0 Imports: 3 Imported by: 0

README

Collatz: Go 🔷🐀🔷

Banner Image, Collatz Coral

Colourised Collatz Coral; derived from this original by Edmund Harriss

Functions related to the Collatz/Syracuse/3N+1 problem, implemented in Go.

Getting Started

To install the latest from pkg.go.dev;

go get -u github.com/Skenvy/Collatz/go

Usage

Provides the basic functionality to interact with the Collatz conjecture. The parameterisation uses the same (P,a,b) notation as Conway's generalisations. Besides the function and reverse function, there is also functionality to retrieve the hailstone sequence, the "stopping time"/"total stopping time", or tree-graph. The only restriction placed on parameters is that both P and a can't be 0.

GoDoc generated docs

Generated Coverage

Developing

Install go. The latest version should be fine, because you can download other versions once you have installed whatever the latest is. See the list of releases that can be downloaded here. See the release history.

The first time setup
git clone https://github.com/Skenvy/Collatz.git && cd Collatz/go && make godoc
Iterative development
  • make docs_local to start a local server to browse the files taken from, and generated by, godoc.

Open Source Insights

Documentation

Overview

Provides the basic functionality to interact with the Collatz conjecture. The parameterisation uses the same (P,a,b) notation as Conway's generalisations. Besides the function and reverse function, there is also functionality to retrieve the hailstone sequence, the "stopping time"/"total stopping time", or tree-graph. 

import collatz "github.com/Skenvy/Collatz/go"

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func DEFAULT_A 

func DEFAULT_A() (DEFAULT_A *big.Int)

Returns DEFAULT_A, the default value for a, the input's multiplicand.

func DEFAULT_B 

func DEFAULT_B() (DEFAULT_B *big.Int)

Returns DEFAULT_B, the default value for b, the value added to the multiplied value.

func DEFAULT_P 

func DEFAULT_P() (DEFAULT_P *big.Int)

Returns DEFAULT_P, the default value for P, the modulus condition.

func Function 

func Function(n *big.Int) (result *big.Int)

Returns the result of a single application of the Collatz function.

  • n: The value on which to perform the Collatz-esque function

func KNOWN_CYCLES 

func KNOWN_CYCLES() (KNOWN_CYCLES [4]*[]*big.Int)

The four KNOWN_CYCLES for the standard parameterisation.

func ONE 

func ONE() (ONE *big.Int)

Return a big.Int with a value of 1.

func ParameterisedFunction 

func ParameterisedFunction(n *big.Int, P *big.Int, a *big.Int, b *big.Int) (result *big.Int, sanity error)

Returns the result of a single application of a Collatz-esque function.

  • n: The value on which to perform the Collatz-esque function
  • P: Modulus used to divide n, iff n is equivalent to (0 mod P).
  • a: Factor by which to multiply n.
  • b: Value to add to the scaled value of n.

func ParameterisedReverseFunction 

func ParameterisedReverseFunction(n *big.Int, P *big.Int, a *big.Int, b *big.Int) (preNDivP *big.Int, preANplusB *big.Int, sanity error)

Returns the output of a single application of a Collatz-esque reverse function. If there is no error in the parameters, then the value of preNDivP will always be an actual result, while preANplusB may either be a result, or nil.

  • n: The value on which to perform the reverse Collatz function
  • P: Modulus used to divide n, iff n is equivalent to (0 mod P)
  • a: Factor by which to multiply n.
  • b: Value to add to the scaled value of n.

func ParameterisedStoppingTime 

func ParameterisedStoppingTime(initialValue *big.Int, P *big.Int, a *big.Int, b *big.Int, maxStoppingTime int, totalStoppingTime bool) (float64, error)

Returns the stopping time, the amount of iterations required to reach a value less than the initial value, or -Inf if maxStoppingTime is exceeded. Alternatively, if totalStoppingTime is True, then it will instead count the amount of iterations to reach 1. If the sequence does not stop, but instead ends in a cycle, the result will be +Inf. If (P,a,b) are such that it is possible to get stuck on zero, the result will be the negative of what would otherwise be the "total stopping time" to reach 1, where 0 is considered a "total stop" that should not occur as it does form a cycle of length 1.

  • initialValue: The value for which to find the stopping time.
  • P: Modulus used to divide n, iff n is equivalent to (0 mod P).
  • a: Factor by which to multiply n.
  • b: Value to add to the scaled value of n.
  • maxStoppingTime: Maximum amount of times to iterate the function, if the stopping time is not reached. IF the maxStoppingTime is reached, the function will return null.
  • totalStoppingTime: Whether or not to execute until the "total" stopping time (number of iterations to obtain 1) rather than the regular stopping time (number of iterations to reach a value less than the initial value).

return (float64): The stopping time, or, in a special case, infinity, null or a negative.

func ReverseFunction 

func ReverseFunction(n *big.Int) (preNDivP *big.Int, preANplusB *big.Int)

Returns the output of a single application of the Collatz reverse function. The value of preNDivP will always be an actual result, while preANplusB may either be a result, or nil.

  • n: The value on which to perform the reverse Collatz function

func StoppingTime 

func StoppingTime(initialValue *big.Int) float64

Returns the stopping time, the amount of iterations required to reach a value less than the initial value, or -Inf if maxStoppingTime is exceeded.

  • initialValue: The value for which to find the stopping time.

return float64: The stopping time, or, in a cycle case, infinity.

func TreeGraphEquals 

func TreeGraphEquals(t1 *TreeGraph, t2 *TreeGraph) bool

The equality between TreeGraphs is determined by the equality check on subtrees. A subtree check will be done on both TreeGraph's root nodes.

func VERIFIED_MAXIMUM 

func VERIFIED_MAXIMUM() (VERIFIED_MAXIMUM *big.Int)

The current value up to which the standard parameterisation has been verified.

func VERIFIED_MINIMUM 

func VERIFIED_MINIMUM() (VERIFIED_MINIMUM *big.Int)

The current value down to which the standard parameterisation has been verified.

func ZERO 

func ZERO() (ZERO *big.Int)

Return a big.Int with a value of 0.

Types

type FailedSaneParameterCheck 

type FailedSaneParameterCheck SaneParameterErrMsg

Thrown when either P, the modulus, or a, the multiplicand, are zero. Create as either or; 

FailedSaneParameterCheck(SANE_PARAMS_P)
FailedSaneParameterCheck(SANE_PARAMS_A)

func (FailedSaneParameterCheck) Error 

func (fspc FailedSaneParameterCheck) Error() string

Construct a FailedSaneParameterCheck with a message associated with the provided enum.

type HailstoneSequence 

type HailstoneSequence struct {
	// contains filtered or unexported fields
}

Contains the results of computing a hailstone sequence. Can be created via; 

ParameterisedHailstoneSequence(~)
NewHailstoneSequence(~)

func NewHailstoneSequence 

func NewHailstoneSequence(initialValue *big.Int, maxTotalStoppingTime int) *HailstoneSequence

Initialise and compute a new Hailstone Sequence.

  • initialValue: The value to begin the hailstone sequence from.
  • P: Modulus used to divide n, iff n is equivalent to (0 mod P).
  • a: Factor by which to multiply n.
  • b: Value to add to the scaled value of n.
  • maxTotalStoppingTime: Maximum amount of times to iterate the function, if 1 is not reached.
  • totalStoppingTime: Whether or not to execute until the "total" stopping time (number of iterations to obtain 1) rather than the regular stopping time (number of iterations to reach a value less than the initial value).

func ParameterisedHailstoneSequence 

func ParameterisedHailstoneSequence(initialValue *big.Int, P *big.Int, a *big.Int, b *big.Int, maxTotalStoppingTime int, totalStoppingTime bool) (*HailstoneSequence, error)

Initialise and compute a new Hailstone Sequence.

  • initialValue: The value to begin the hailstone sequence from.
  • P: Modulus used to divide n, iff n is equivalent to (0 mod P).
  • a: Factor by which to multiply n.
  • b: Value to add to the scaled value of n.
  • maxTotalStoppingTime: Maximum amount of times to iterate the function, if 1 is not reached.
  • totalStoppingTime: Whether or not to execute until the "total" stopping time (number of iterations to obtain 1) rather than the regular stopping time (number of iterations to reach a value less than the initial value).

type SaneParameterErrMsg 

type SaneParameterErrMsg int64

Error message constants, to be used as input to the FailedSaneParameterCheck 

const (
	// Message to print in the FailedSaneParameterCheck if P, the modulus, is zero.
	SANE_PARAMS_P SaneParameterErrMsg = iota
	// Message to print in the FailedSaneParameterCheck if a, the multiplicand, is zero.
	SANE_PARAMS_A
)

func (SaneParameterErrMsg) String 

func (spem SaneParameterErrMsg) String() (ErrorMessage string)

Get the string associated with the SaneParameterErrMsg

type SequenceState 

type SequenceState int64

SequenceState for Cycle Control: Descriptive flags to indicate when some event occurs in the hailstone sequences or tree graph reversal, when set to verbose, or stopping time check. 

const (
	// A TreeGraph sequence state that indicates the lack
	// of another state, as this state can't be nil
	NO_STATE SequenceState = iota
	// A Hailstone sequence state that indicates the stopping
	// time, a value less than the initial, has been reached.
	STOPPING_TIME
	// A Hailstone sequence state that indicates the total
	// stopping time, a value of 1, has been reached.
	TOTAL_STOPPING_TIME
	// A Hailstone and TreeGraph sequence state that indicates the
	// first occurence of a value that subsequently forms a cycle.
	CYCLE_INIT
	// A Hailstone and TreeGraph sequence state that indicates the
	// last occurence of a value that has already formed a cycle.
	CYCLE_LENGTH
	// A Hailstone and TreeGraph sequence state that indicates the sequence
	// or traversal has executed some imposed 'maximum' amount of times.
	MAX_STOP_OUT_OF_BOUNDS
	// A Hailstone sequence state that indicates the sequence terminated
	// by reaching "0", a special type of "stopping time".
	ZERO_STOP
)

func (SequenceState) String 

func (ss SequenceState) String() (StateString string)

Get the string associated with the SequenceState

type TreeGraph 

type TreeGraph struct {
	// contains filtered or unexported fields
}

Contains the results, in a "root node" of computing the Tree Graph via; 

ParameterisedTreeGraph(~)
NewTreeGraph(~)

func NewTreeGraph 

func NewTreeGraph(initialValue *big.Int, maxOrbitDistance int) (*TreeGraph, error)

Create a new TreeGraph with the root node defined by the inputs. Returns a directed tree graph of the reverse function values up to a maximum nesting of maxOrbitDistance, with the initialValue as the root.

  • initialValue: The root value of the directed tree graph.
  • maxOrbitDistance: Maximum amount of times to iterate the reverse function. There is no natural termination to populating the tree graph, equivalent to the termination of hailstone sequences or stopping time attempts, so this is not an optional argument like maxStoppingTime / maxTotalStoppingTime, as it is the intended target of orbits to obtain, rather than a limit to avoid uncapped computation.

func ParameterisedTreeGraph 

func ParameterisedTreeGraph(initialValue *big.Int, maxOrbitDistance int, P *big.Int, a *big.Int, b *big.Int) (*TreeGraph, error)

Create a new TreeGraph with the root node defined by the inputs. Returns a directed tree graph of the reverse function values up to a maximum nesting of maxOrbitDistance, with the initialValue as the root.

  • initialValue: The root value of the directed tree graph.
  • maxOrbitDistance: Maximum amount of times to iterate the reverse function. There is no natural termination to populating the tree graph, equivalent to the termination of hailstone sequences or stopping time attempts, so this is not an optional argument like maxStoppingTime / maxTotalStoppingTime, as it is the intended target of orbits to obtain, rather than a limit to avoid uncapped computation.
  • P: Modulus used to divide n, iff n is equivalent to (0 mod P).
  • a: Factor by which to multiply n.
  • b: Value to add to the scaled value of n.

type TreeGraphNode 

type TreeGraphNode struct {
	// contains filtered or unexported fields
}

Nodes that form a "tree graph", structured as a tree, with their own node's value, as well as references to either possible child node, where a node can only ever have two children, as there are only ever two reverse values. Also records any possible "terminal sequence state", whether that be that the "orbit distance" has been reached, as an "out of bounds" stop, which is the regularly expected terminal state. Other terminal states possible however include the cycle state and cycle length (end) states.

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.