Welcome to coreli’s documentation!

Coreli is the Collatz Research Library.

coreli.Collatz_maps

Collatz maps definitions.

References

[1] The Ultimate Challenge: The 3x+1 Problem, Edited by Jeffrey C. Lagarias. American Mathematical Society, Providence RI 2010, pp. 3–29: https://arxiv.org/abs/2111.02635

coreli.Collatz_maps.C(x: Union[int, Rational, PadicInt]) → Union[int, Rational, PadicInt]

The Collatz map, defined on ints, rational with odd denominator and 2-adic integers.

References

[1] Jeffrey C. Lagarias. “The 3x + 1 Problem and Its Generalizations”. In: The American Mathe-: matical Monthly 92.1 (1985), pp. 3-23. issn: 00029890, 19300972. url: http://www.jstor.org/stable/2322189.

Example

>>> C(2)
1
>>> C(3)
10
>>> C(Rational(-2,23))
-1/23
>>> C(Rational(-1,23))
20/23
>>> from coreli.padic_integers import Padic
>>> Z2 = Padic(2)
>>> minus_one_third = Z2(digit_function = lambda n: (n+1)%2)
>>> C(minus_one_third).to_str()
'...0000000000'
>>> from coreli.utils import iterate
>>> some_2_adic = Z2(digit_function = lambda n: iterate(C,n,n)%2)
>>> C(some_2_adic).to_str(20)
'...00001000100001010000'

coreli.Collatz_maps.T(x: int) → Union[int, Rational, PadicInt]

The Collatz map, slightly accelerated, defined on ints, rational with odd denominator and 2-adic integers.

References

[1] Jeffrey C. Lagarias. “The 3x + 1 Problem and Its Generalizations”. In: The American Mathe-: matical Monthly 92.1 (1985), pp. 3-23. issn: 00029890, 19300972. url: http://www.jstor.org/stable/2322189..

Example

>>> T(2)
1
>>> T(3)
5
>>> T(Rational(-2,23))
-1/23
>>> T(Rational(-1,23))
10/23
>>> from coreli.padic_integers import Padic
>>> Z2 = Padic(2)
>>> minus_one_third = Z2(digit_function = lambda n: (n+1)%2)
>>> T(minus_one_third).to_str()
'...0000000000'
>>> from sympy.ntheory.primetest import is_square
>>> some_2_adic = Z2(digit_function = lambda n: int(is_square(n)))
>>> some_2_adic.to_str(40)
'...0001000000000010000000010000001000010011'
>>> T(some_2_adic).to_str(40)
'...0001100000000011000000011000001100011101'

coreli.parity_vectors

class coreli.parity_vectors.ParityVector(parity_vector)

A parity vector is a list of 0s and 1s which corresponds to the parity of elements of a Collatz sequences (with map T). (i.e. which of the maps x/2 or (3x+1)/2 is taken at each step)

It is known that (see [1,2,4]):

All parity vectors are feasible in N, i.e. for any parity vector

of length n there is a natural number that follows the parities given by the parity vector in its first n T-Collatz steps.

More precisely, for any parity vector of length n, there is a smallest

integer α in N such that the first n T-Collatz steps follow the parities given by the parity vector, and then, all integers of the form a2^n + α also follow the parities given by the parity vector. We say that (α,β) is the first “occurrence” of the parity vector, with β = T^n(α).

There is a bijection between parity vectors of length n and numbers < 2^n,

i.e. two distinct numbers < 2^n have distinct length-n parity vectors.

When considering infinite parity vectors (i.e. associated to infinite

T-Collatz sequences), we get a continuous bijection Q from Z_2 to Z_2, mapping Collatz-inputs in Z_2 to their parity vector, seen as an element of Z_2 (see [2,4]).

It is known that if Q(x) is eventually periodic then x is eventually periodic

i.e. x is rational.

It is conjectured that if x is eventually periodic then Q(x) is eventually

periodic, Lagarias Periodicity Conjecture [2]. If this conjecture is true, then there is no divergent Collatz orbit in N.

cyclic_rational() → Rational

Returns the unique rational x such that T^n(x) = x and the parity vector corresponds to the n first Collatz steps of x.

Explicit formula deducible from 2.13 in [3] (page 41).

This rational also happen to be 2-adic, 3-adic and 6-adic integer since its numerator is of the form 2^n - 3^k (its not a multiple of 2, 3, or 6).

Example

>>> ParityVector([1]).cyclic_rational()
-1
>>> ParityVector([1,1,0]).cyclic_rational()
-5
>>> ParityVector([1,1,1,1,0,1,1,1,0,0,0]).cyclic_rational()
-17
>>> ParityVector([1,1,0,1,0,0]).cyclic_rational()
23/37
>>> ParityVector([0,0,1,0,0]).cyclic_rational()
4/29
>>> ParityVector([1,1,0,1,1]).cyclic_rational()
-85/49
>>> ParityVector([1,0,0,1,1,1]).cyclic_rational()
-179/17

first_occurrence(symbolic=False) → Union[Tuple[int, int], Tuple[str, str]]

Returns the couple (α,β) such that α is the smallest number in N such that its first n T-Collatz steps follow the parities given by the length-n parity vector. And, β = T^n(α).

There are explicit formulae for α and β, seen [4]. But here we use an iterative algorithm described in [5].

If symbolic is true, the function returns α in base 2 and n bits and β in base 3 and k bits with k the number of 1s in the parity vector.

Example

>>> ParityVector([1,1,0,1]).first_occurrence()
(11, 20)
>>> ParityVector([1,1,0,1]).first_occurrence(symbolic=True)
('1011', '202')
>>> ParityVector([1,0,0,0,1]).first_occurrence(symbolic=True)
('00101', '02')

classmethod from_Collatz(x: Union[int, Rational, PadicInt], n: int) → ParityVector

Returns the parity vector corresponding to n application of Collatz map T. The parity vector will be of size n+1.

Example

>>> ParityVector.from_Collatz(23,10)
[1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0]

odd_len(): Returns the number of 1s (odd terms) in the parity vector which is a metric that is often used when working with parity vector.

to_tiling() → Tiling: Builds the Collatz tiling associated to the parity vector.

coreli.padic_integers

Implementing p-adic integers.

References

[1] Computations with p-adic numbers. Xavier Caruso. Preprint, 2017.: https://arxiv.org/abs/1701.06794

class coreli.padic_integers.Padic(p: int)

Wrapper around p-adic integers with p fixed, i.e. it represents the ring Z_p. Note that p does not need to be prime for Z_p(+,x) to be defined but Z_p is a field iff p is prime.

Example

>>> Z2 = Padic(2)
>>> Z2.from_int(25).to_str()
'...0000011001'
>>> x = Z2(digit_function = lambda n: n%2)
>>> x.to_str()
'...1010101010'

from_int(x: int) → PadicInt

Constructs a p-adic integer from an integer x. The n-th digit is f^n(x) mod p, with f the Collatz-like map f(x) = (x-i)/p if x = i mod p.

Example

>>> Z2 = Padic(2)
>>> Z2.from_int(25).to_str()
'...0000011001'
>>> Z2.from_int(-4).to_str(20)
'...11111111111111111100'
>>> Z3 = Padic(3)
>>> Z3.from_int(-10).to_str()
'...2222222122'

from_rational(x: Rational) → PadicInt

Constructs a p-adic integer from a rational x with denominator that is coprime with p. The n-th digit is f^n(x) mod p, with f the Collatz-like map f(x) = (x-i)/p if x = i mod p.

Example

>>> Z2 = Padic(2)
>>> Z2.from_rational(Rational(-1,3)).to_str()
'...0101010101'
>>> Z2.from_rational(Rational(-1,23)).to_str(20)
'...00101100100001011001'
>>> Z3 = Padic(3)
>>> Z3.from_rational(Rational(77,13)).to_str()
'...2002002022'

coreli.padic_integers.least_significant_digit(x: Union[int, Rational, PadicInt], base=2) → int

Returns the least significant digit of an integer in a base or rational p-adic or p-adic.

Example

>>> least_significant_digit(25)
1
>>> least_significant_digit(47,3)
2
>>> from sympy import Rational
>>> least_significant_digit(Rational(2,15))
0

coreli.Collatz_tilings

coreli.Collatz_tilings.base32_diagonal(diagonal: str) → Tiling: Returns Collatz tiling corresponding to south-west-going base 3/2 diagonal.

coreli.Collatz_tilings.base6_diagonal(diagonal: str) → Tiling: Returns Collatz tiling corresponding to north-west-going base 6 diagonal.

coreli.Collatz_tilings.north_east_corner(north: str, east: str) → Tiling: Returns Collatz tiling corresponding to north east corner with ternary word to the east and binary word to the north.

coreli.Collatz_tilings.south_east_corner(south: str, east: str) → Tiling: Returns Collatz tiling corresponding to south east corner with ternary word to the east and binary word to the south.

coreli.Collatz_tilings.south_west_corner(south: str, west: str) → Tiling: Returns Collatz tiling corresponding to south west corner with ternary word to the west and binary word to the south.

coreli.utils

coreli.utils.int_to_base(x: int, base: int, length: Union[None, int] = None, to_str: bool = True) → Union[str, List[int]]

Converts a non-negative integer to its base representation. Note that in the list representation, the least significant digit comes first whereas, in the string representation, the least significant digit comes last.

Parameters

x (int) – the positive integer to convert
base (int) – the target base
to_str (bool) – whether the result is given as a string or a list of digits
length (None or int) – if not None, the output representation will be padded
smaller (with leading 0s so its length is equal to length. If length is) –
size (than the representation's) –
raise (the function will) –

Example

>>> int_to_base(13,2)
'1101'
>>> int_to_base(13,2,9)
'000001101'
>>> int_to_base(13,2,to_str=False)
[1, 0, 1, 1]
>>> int_to_base(313,5)
'2223'
>>> int_to_base(313,5,to_str=False)
[3, 2, 2, 2]
>>> int_to_base(0,87)
'0'

coreli.utils.iterate(f, n, x_0) → int: Returns the nth iterate of f from x_0, i.e., f^n(x_0).

coreli.utils.iterates(f, n, x_0) → List[int]: Returns the list of the n+1 first iterates of f (including x_0): [x_0, f(x_0), …, f^n(x_0)].

coreli.utils.list_int_to_list_str(l: List[int]) → List[str]

Converts each int of a list to a str.

Example

>>> list_int_to_list_str([1,1,0,1])
['1', '1', '0', '1']
>>> list_int_to_list_str([5,12,31,7])
['5', '12', '31', '7']

Welcome to coreli’s documentation!

coreli.Collatz_maps

coreli.parity_vectors

coreli.padic_integers

coreli.Collatz_tilings

coreli.utils

Indices and tables