<jupyter_start><jupyter_text>What is this notebook ?This notebook illustrates the construction of the main result (Theorem 4.16) of the paper "First Occurrence of Parity Vectors and The Regular Structure of $k$-span Predecessor Sets in the Collatz graph", [arxiv:1907.00775](https://arxiv.org/abs/1907.00775). This algorithm computes the regular expression associated to the $k$-span predecessor set of $x$. You can also find the construction in Appendix E (Algorithm 2).This result is also known as Theorem 1 and Algorithm 1 in the paper 'Collatz Predecessor Sets Partition into Regular Languages'.   Some Regular expressions<jupyter_code>get_reg_k(4,2)
get_reg_k(3,2)
get_reg_k(13,3)<jupyter_output><empty_output><jupyter_text>Exponential GrowthThe length of `reg_k(x,k)` grows exponentially with $k$ when $x$ is not a multiple of 3.<jupyter_code>for k in range(6):
    print(len(get_reg_k(1,k)), end=" ")<jupyter_output>7 21 75 586 11308 616144<jupyter_text>Automatic TestingWe use the package 'redone' (https://github.com/cyphar/redone/) in order to automatically test our Regular Expressions.<jupyter_code>import redone 
def check_match(reg,s):
    pat = redone.compile(reg.replace('()',''))
    return not(pat.fullmatch(s) is None)<jupyter_output><empty_output><jupyter_text>By Theorem 4.16, the following test should be positive for any value of $n$. However, the size of the regex is growing exponentially with the span hence the regex testing can be long for parity vectors with long span (>4).<jupyter_code>n = 4
for p in get_parvec_with_constraints(parvec_norm=n):
    Collatz_encoding = get_Collatz_encoding(p)
    occurrence = get_first_occurrence(p)
    
    span = l_of(p)
    reg = get_reg_k(occurrence[-1],span)
    
    if not check_match(reg,Collatz_encoding):
        print(p, "NOT OK!")
        break
    else:
        print(p, "OK")
print("OK!")<jupyter_output>[0, 0, 0, 0] OK
[0, 0, 0, 1] OK
[0, 0, 1, 0] OK
[0, 0, 1, 1] OK
[0, 1, 0, 0] OK
[0, 1, 0, 1] OK
[0, 1, 1, 0] OK
[0, 1, 1, 1] OK
[1, 0, 0, 0] OK
[1, 0, 0, 1] OK
[1, 0, 1, 0] OK
[1, 0, 1, 1] OK
[1, 1, 0, 0] OK
[1, 1, 0, 1] OK
[1, 1, 1, 0] OK
[1, 1, 1, 1] OK
OK!
{'fraction_non_alphanumeric': 0.12464985994397759, 'fraction_numerical': 0.05742296918767507, 'mean_word_length': 4.537467700258398, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 16, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '434465', 'license': 'MIT', 'n_tokens_mistral': 889, 'n_tokens_neox': 782, 'n_words': 279, 'path': 'RegularExpressions.ipynb', 'repo_name': 'tcosmo/CollatzRegular', 'size': '2142'}