ZeroPattern

Describes the zero pattern of a sequence comprised of a finite set together with finitely many arithmetic progressions. Such a zero pattern is represented by a sequence of boolean values where False represents a zero and True a different value.

EXAMPLES:

sage: from rec_sequences.ZeroPattern import *

sage: progressions = set([ArithmeticProgression(3, 3), \
....:                     ArithmeticProgression(5, 2)])
sage: pattern = ZeroPattern(set([0]), progressions)
sage: pattern[0] # check that 0-th term is zero
False
sage: pattern[1] # check that 1-st term is non-zero
True
sage: pattern.get_cycle_start(), pattern.get_cycle_length()
(3, 15)
sage: print(pattern.pattern()) # first terms of pattern
0*00**00*0**0**0*00*

class rec_sequences.ZeroPattern.ZeroPattern(finite_set={}, progressions={})

Bases: sage.structure.sage_object.SageObject

The class describes the zero pattern of a sequence which does not violate the Skolem-Mahler-Lech-Theorem. I.e., the class describes a finite set of zeros and some finitely many arithmetic progessions where the sequence is zero as well.

This zero pattern might not be unique, i.e. there might be several different objects describing the same pattern.

__eq__(pattern)

Checks whether two zero patterns are equal.

INPUT:

• pattern – a zero pattern

OUTPUT:

True if the two patterns are equal and False otherwise.

__getitem__(n)

INPUT:

• n – a natural number or a slice object (specifying only finitely many values)

OUTPUT:

Returns True if the n-th term is non-zero and False if it is zero provided that n is a natural number. If n is a slice object, a list with these boolean values is returned.

EXAMPLES:

sage: from rec_sequences.ZeroPattern import *

sage: progressions = set([ArithmeticProgression(3, 3), \
....:                     ArithmeticProgression(5, 2)])
sage: pattern = ZeroPattern(set([0]), progressions)
sage: pattern[:5] 
[False, True, False, False, True]

__init__(finite_set={}, progressions={})

Creates a zero pattern with the given set finite_set and the given arithmetic progressions.

INPUT:

• finite_set – a set of exceptional zeros not covered by the arithmetic progressions.

• progressions – a set of arithmetic progressions of the type rec_sequences.ArithmeticProgression.

OUTPUT:

The described zero pattern.

EXAMPLES:

sage: from rec_sequences.ZeroPattern import *

sage: progressions = set([ArithmeticProgression(3, 3), \
....:                     ArithmeticProgression(5, 2)])
sage: pattern = ZeroPattern(set([0]), progressions)
sage: print(pattern) # random
Zero pattern with finite set {0} and arithmetic progressions: 
- Arithmetic progression (3*n+3)_n
- Arithmetic progression (5*n+2)_n

_latex_()

OUTPUT:

A latex representation of the zero pattern.

EXAMPLES:

sage: from rec_sequences.ZeroPattern import *

sage: progressions = set([ArithmeticProgression(3, 3)])
sage: print(latex(ZeroPattern(set([0]), progressions))) 
\{0\}\cup\{3 \cdot n + 3 : n \in \mathbb{N}\}

_repr_()

OUTPUT:

A string representation of the zero pattern.

EXAMPLES:

sage: from rec_sequences.ZeroPattern import *

sage: progressions = set([ArithmeticProgression(3, 3), \
....:                     ArithmeticProgression(5, 2)])
sage: print(latex(ZeroPattern(set([0]), progressions))) # random
Zero pattern with finite set {0} and arithmetic progressions: 
- Arithmetic progression (3*n+3)_n
- Arithmetic progression (5*n+2)_n
sage: print(ZeroPattern(set([0,2]), set()))
Zero pattern with finite set {0, 2} and no arithmetic progressions

eventually_non_zero()

OUTPUT:

Returns True if the pattern is eventually non-zero, i.e., the pattern only consists of finitely many zeros and no arithmetic progressions.

EXAMPLES:

sage: from rec_sequences.ZeroPattern import *

sage: progressions = set([ArithmeticProgression(3, 3)])
sage: ZeroPattern(set([0]), progressions).eventually_non_zero()
False
sage: ZeroPattern(set([3])).eventually_non_zero()
True
sage: ZeroPattern().eventually_non_zero()
True

classmethod from_zero_pattern(finite_set={}, cycle_start=0, cycle=[])

Creates a zero pattern with the given set finite_set and the given arithmetic cycle.

INPUT:

• finite_set – a set of exceptional zeros not covered by the arithmetic progressions.

• cycle_start – a natural number indicating where the periodic behavior of the zeros start.

• cycle – the zero-cycle which holds from cycle_start on. It should be given as list of boolean values where False indicates a zero value and True a non-zero value (or use any values that can be casted like this).

OUTPUT:

The described zero pattern.

EXAMPLES:

sage: from rec_sequences.ZeroPattern import *

sage: pattern = ZeroPattern.from_zero_pattern([0], 3, [0,1,1,0,1])
sage: print(pattern) # random
Zero pattern with finite set [0] and arithmetic progressions: 
- Arithmetic progression (5*n+3)_n
- Arithmetic progression (5*n+6)_n
sage: print(pattern.pattern())
00*0**0*0**0*0**0*0*

get_cycle_length()

OUTPUT:

Returns the length of the cycle.

EXAMPLES:

sage: from rec_sequences.ZeroPattern import *

sage: progressions = set([ArithmeticProgression(3, 3), \
....:                     ArithmeticProgression(5, 2)])
sage: pattern = ZeroPattern(set([0]), progressions)
sage: print(pattern.get_cycle_length())
15

get_cycle_start()

OUTPUT:

Returns the index from which the zero-pattern is guaranteed to be cyclic. This index might not be minimal.

EXAMPLES:

sage: from rec_sequences.ZeroPattern import *

sage: progressions = set([ArithmeticProgression(3, 3), \
....:                     ArithmeticProgression(5, 2)])
sage: pattern = ZeroPattern(set([0]), progressions)
sage: print(pattern.get_cycle_start())
3

get_finite_set()

OUTPUT:

Returns the finite zero-set of the pattern.

EXAMPLES:

sage: from rec_sequences.ZeroPattern import *

sage: progressions = set([ArithmeticProgression(3, 3), \
....:                     ArithmeticProgression(5, 2)])
sage: pattern = ZeroPattern(set([0]), progressions)
sage: print(pattern.get_finite_set())
{0}

get_progressions()

OUTPUT:

Returns the arithmetic progressions of the pattern.

EXAMPLES:

sage: from rec_sequences.ZeroPattern import *

sage: progressions = set([ArithmeticProgression(3, 3), \
....:                     ArithmeticProgression(5, 2)])
sage: pattern = ZeroPattern(set([0]), progressions)
sage: print(pattern.get_progressions()) # random
{Arithmetic progression (3*n+3)_n, Arithmetic progression (5*n+2)_n}

classmethod guess(data, cycles=3, *args, **kwds)

Computes the zero pattern of the given data.

INPUT:

• data – a list of numbers

• cycles – the number of cycles that need to be detected to conclude whether we indeed have a period. Assume cycles>1.

OUTPUT:

The zero-pattern satisfied by data. If no pattern could be found, a ValueError is raised.

ALGORITHM:

We assume that the periodic behavior starts at least at the half-point of the given data. The algorithm is not particularly efficient and runs in O(len(data)^3) in the worst case. However, in the usual case, if data is cyclic almost from the beginning it is essentially O(len(data))

EXAMPLES:

sage: from rec_sequences.ZeroPattern import *

sage: ZeroPattern.guess([1,0,0,1,0,2,0,3,0,4,0,5])
Zero pattern with finite set [1] and arithmetic progressions: 
- Arithmetic progression (2*n+2)_n
sage: ZeroPattern.guess(10*[1,0,0,1]) # random
Zero pattern with finite set {} and arithmetic progressions: 
- Arithmetic progression (4*n+1)_n
- Arithmetic progression (4*n+2)_n

is_zero()

OUTPUT:

Returns True if the pattern is constantly zero.

EXAMPLES:

sage: from rec_sequences.ZeroPattern import *

sage: progressions = set([ArithmeticProgression(3, 3)])
sage: ZeroPattern(set([0]), progressions).is_zero()
False
sage: ZeroPattern(set([3])).is_zero()
False
sage: ZeroPattern().is_zero()
False
sage: progressions2 = set([ArithmeticProgression(1, 1)])
sage: ZeroPattern([0], progressions2).is_zero()
True
sage: ZeroPattern([], progressions2).is_zero()
True

non_zero()

OUTPUT:

Returns True if the pattern has no zeros at all and False otherwise.

EXAMPLES:

sage: from rec_sequences.ZeroPattern import *

sage: progressions = set([ArithmeticProgression(3, 3)])
sage: ZeroPattern(set([0]), progressions).non_zero()
False
sage: ZeroPattern(set([3])).non_zero()
False
sage: ZeroPattern().non_zero()
True

non_zero_start()

OUTPUT:

Returns the index from which on the pattern has no zeros at all. If such an index does not exist, a ValueError is raised.

EXAMPLES:

sage: from rec_sequences.ZeroPattern import *

sage: progressions = set([ArithmeticProgression(3, 3)])
sage: ZeroPattern(set([0]), progressions).non_zero_start()
Traceback (most recent call last):
...
ValueError: Pattern contains infinitely many zeros
sage: ZeroPattern(set([3])).non_zero_start()
4
sage: ZeroPattern().non_zero_start()
0

pattern(n=20)

INPUT:

• n – a natural number

OUTPUT:

Returns a string s of length n with characters 0 (representing a zero at the corresponding position) and * (representing a non-zero at the corresponding position).

EXAMPLES:

sage: from rec_sequences.ZeroPattern import *

sage: progressions = set([ArithmeticProgression(3, 3), \
....:                     ArithmeticProgression(5, 2)])
sage: pattern = ZeroPattern(set([0]), progressions)
sage: print(pattern.pattern(5))
0*00*