<jupyter_start><jupyter_text>Let us test the above codes for small $p$ and random $p$.<jupyter_code>#irreducibility test
p=11
n=100000
q=irreducible(p,n)
print(f"f is irreducible at q= ", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
#two_cycle_search
p=11
n=100000
q=two_cycle(p,n)
print(f"f has a 2-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
#(2n-2)_cycle_search
p=11
n=100000
q=almost_cycle(p,n)
print(f"f has a (2n-2)-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
#four_cycle_search
p=11
n=100000
q=four_cycle(p,n)
print(f"f has a 4-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
p=11
n=100000
print(f"The prime we are considering is p=", p)
q=irreducible(p,n)
print(f"f is irreducible at q= ", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))


#full_search
p=11
n=100000
q=irreducible(p,n)
f=fekete(p)
print(f"The degree of f is deg=", f.degree())
print(f"f is irreducible at q= ", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
n=100000
q=almost_cycle(p,n)
print(f"f has a (2n-2)-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))

q=four_cycle(p,n)
print(f"f has a 4-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
q=two_cycle(p,n)
print(f"f has a 2-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
#full_search
p=13
n=100000
q=irreducible(p,n)
f=fekete(p)
print(f"The degree of f is deg=", f.degree())
print(f"f is irreducible at q= ", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
n=100000
q=almost_cycle(p,n)
print(f"f has a (2n-2)-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))

q=four_cycle(p,n)
print(f"f has a 4-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
q=two_cycle(p,n)
print(f"f has a 2-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))

#full_search
p=17
n=100000
q=irreducible(p,n)
f=fekete(p)
print(f"The degree of f is deg=", f.degree())
print(f"f is irreducible at q= ", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
n=100000
q=almost_cycle(p,n)
print(f"f has a (2n-2)-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))

q=four_cycle(p,n)
print(f"f has a 4-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
q=two_cycle(p,n)
print(f"f has a 2-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
#full_search
p=19
n=100000
q=irreducible(p,n)
f=fekete(p)
print(f"The degree of f is deg=", f.degree())
print(f"f is irreducible at q= ", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
n=100000
q=almost_cycle(p,n)
print(f"f has a (2n-2)-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))

q=four_cycle(p,n)
print(f"f has a 4-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
q=two_cycle(p,n)
print(f"f has a 2-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
#full_search
P=Primes()
p=19
n=100000
p=P.next(p)
q=irreducible(p,n)
f=fekete(p)
print(f"The prime we are considering is p=", p)
print(f"The degree of f is deg=", f.degree())
print(f"f is irreducible at q= ", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
n=100000
q=almost_cycle(p,n)
print(f"f has a (2n-2)-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))

q=four_cycle(p,n)
print(f"f has a 4-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
q=two_cycle(p,n)
print(f"f has a 2-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
#full_search
P=Primes()
n=100000
p=P.next(p)
q=irreducible(p,n)
f=fekete(p)
print(f"The prime we are considering is p=", p)
print(f"The degree of f is deg=", f.degree())
print(f"f is irreducible at q= ", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
n=100000
q=almost_cycle(p,n)
print(f"f has a (2n-2)-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))

q=four_cycle(p,n)
print(f"f has a 4-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
q=two_cycle(p,n)
print(f"f has a 2-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
#full_search
P=Primes()
n=100000
p=P.next(p)
q=irreducible(p,n)
f=fekete(p)
print(f"The prime we are considering is p=", p)
print(f"The degree of f is deg=", f.degree())
print(f"f is irreducible at q= ", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
n=100000
q=almost_cycle(p,n)
print(f"f has a (2n-2)-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))

q=four_cycle(p,n)
print(f"f has a 4-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
q=two_cycle(p,n)
print(f"f has a 2-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
#full_search
P=Primes()
n=100000
p=P.next(p)
q=irreducible(p,n)
f=fekete(p)
print(f"The prime we are considering is p=", p)
print(f"The degree of f is deg=", f.degree())
print(f"f is irreducible at q= ", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
n=100000
q=almost_cycle(p,n)
print(f"f has a (2n-2)-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))

q=four_cycle(p,n)
print(f"f has a 4-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
q=two_cycle(p,n)
print(f"f has a 2-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
#full_search
P=Primes()
n=100000
p=P.next(p)
q=irreducible(p,n)
f=fekete(p)
print(f"The prime we are considering is p=", p)
print(f"The degree of f is deg=", f.degree())
print(f"f is irreducible at q= ", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
n=100000
q=almost_cycle(p,n)
print(f"f has a (2n-2)-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))

q=four_cycle(p,n)
print(f"f has a 4-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
q=two_cycle(p,n)
print(f"f has a 2-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
#full_search
P=Primes()
n=100000
p=P.next(p)
q=irreducible(p,n)
f=fekete(p)
print(f"The prime we are considering is p=", p)
print(f"The degree of f is deg=", f.degree())
print(f"f is irreducible at q= ", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
n=100000
q=almost_cycle(p,n)
print(f"f has a (2n-2)-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))

q=four_cycle(p,n)
print(f"f has a 4-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
q=two_cycle(p,n)
print(f"f has a 2-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
#full_search
P=Primes()
n=100000
p=P.next(p)
q=irreducible(p,n)
f=fekete(p)
print(f"The prime we are considering is p=", p)
print(f"The degree of f is deg=", f.degree())
print(f"f is irreducible at q= ", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
n=100000
q=almost_cycle(p,n)
print(f"f has a (2n-2)-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))

q=four_cycle(p,n)
print(f"f has a 4-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))
q=two_cycle(p,n)
print(f"f has a 2-cycle at q", q)
print(f"The factorization of f at q: \n", fekete_reduction(p,q))<jupyter_output>The prime we are considering is p= 47
The degree of f is deg= 44
f is irreducible at q=  107
The factorization of f at q: 
 x^44 + 2*x^43 + 3*x^42 + 4*x^41 + 3*x^40 + 4*x^39 + 5*x^38 + 6*x^37 + 7*x^36 + 6*x^35 + 5*x^34 + 6*x^33 + 5*x^32 + 6*x^31 + 5*x^30 + 6*x^29 + 7*x^28 + 8*x^27 + 7*x^26 + 6*x^25 + 7*x^24 + 6*x^23 + 5*x^22 + 6*x^21 + 7*x^20 + 6*x^19 + 7*x^18 + 8*x^17 + 7*x^16 + 6*x^15 + 5*x^14 + 6*x^13 + 5*x^12 + 6*x^11 + 5*x^10 + 6*x^9 + 7*x^8 + 6*x^7 + 5*x^6 + 4*x^5 + 3*x^4 + 4*x^3 + 3*x^2 + 2*x + 1
f has a (2n-2)-cycle at q 419
The factorization of f at q: 
 (x + 57) * (x + 272) * (x^42 + 92*x^41 + 321*x^40 + 310*x^39 + 347*x^38 + 337*x^37 + 239*x^36 + 229*x^35 + 266*x^34 + 253*x^33 + 302*x^32 + 117*x^31 + 177*x^30 + 316*x^29 + 195*x^28 + 61*x^27 + 274*x^26 + 305*x^25 + 367*x^24 + 49*x^23 + 279*x^22 + 346*x^21 + 279*x^20 + 49*x^19 + 367*x^18 + 305*x^17 + 274*x^16 + 61*x^15 + 195*x^14 + 316*x^13 + 177*x^12 + 117*x^11 + 302*x^10 + 253*x^9 + 266*x^8 + 229*x^7 + 239*x^6 + 337*x^5 + 34[...]<jupyter_text>Next, we will find the smallest tuples $(q_1, q_2, q_3, q_4)$ for $p<200$.<jupyter_code>p=7
n=10**6
P=Primes()
res=[]
while p<200:
    q_irr=irreducible(p,n)
    q_cycle=almost_cycle(p,n)
    q_tranposition=two_cycle(p,n)
    q_four_cycle=four_cycle(p,n)
    res.append([p, [q_irr, q_cycle, q_tranposition, q_four_cycle]])
    p=P.next(p)
res<jupyter_output><empty_output><jupyter_text>Next, we find smallest tuples $(q_1, q_2, q_3, q_4)$ for 200<p<400.<jupyter_code>p=199
n=10**6
P=Primes()
res=[]
while p<400:
    q_irr=irreducible(p,n)
    q_cycle=almost_cycle(p,n)
    q_tranposition=two_cycle(p,n)
    q_four_cycle=four_cycle(p,n)
    res.append([p, [q_irr, q_cycle, q_tranposition, q_four_cycle]])
    p=P.next(p)
res<jupyter_output><empty_output><jupyter_text>Next, we find smallest tuples $(q_1, q_2, q_3, q_4)$ for 400<p<600.<jupyter_code>p=397
n=10**6
P=Primes()
res=[]
while p<500:
    q_irr=irreducible(p,n)
    q_cycle=almost_cycle(p,n)
    q_tranposition=two_cycle(p,n)
    q_four_cycle=four_cycle(p,n)
    res.append([p, [q_irr, q_cycle, q_tranposition, q_four_cycle]])
    p=P.next(p)
res   
%%time
p=499
n=10**6
P=Primes()
res=[]
while p<600:
    q_irr=irreducible(p,n)
    q_cycle=almost_cycle(p,n)
    q_tranposition=two_cycle(p,n)
    q_four_cycle=four_cycle(p,n)
    res.append([p, [q_irr, q_cycle, q_tranposition, q_four_cycle]])
    p=P.next(p)
res<jupyter_output>CPU times: user 2h 12min 29s, sys: 8.25 s, total: 2h 12min 37s
Wall time: 2h 21min 25s<jupyter_text>Next we compute the running time for larger $p$.<jupyter_code>%%time
p=599
P=Primes()
p=P.next(p)
n=10**6
P=Primes()
res=[]
q_irr=irreducible(p,n)
q_cycle=almost_cycle(p,n)
q_tranposition=two_cycle(p,n)
q_four_cycle=four_cycle(p,n)
res.append([p, [q_irr, q_cycle, q_tranposition, q_four_cycle]])
res  
%%time
p=601
P=Primes()
p=P.next(p)
n=10**6
P=Primes()
res=[]
q_irr=irreducible(p,n)
q_cycle=almost_cycle(p,n)
q_tranposition=two_cycle(p,n)
q_four_cycle=four_cycle(p,n)
res.append([p, [q_irr, q_cycle, q_tranposition, q_four_cycle]])
res  
%%time
p=607
P=Primes()
p=P.next(p)
n=10**6
P=Primes()
res=[]
q_irr=irreducible(p,n)
q_cycle=almost_cycle(p,n)
q_tranposition=two_cycle(p,n)
q_four_cycle=four_cycle(p,n)
res.append([p, [q_irr, q_cycle, q_tranposition, q_four_cycle]])
res  
%%time
p=613
P=Primes()
p=P.next(p)
n=10**6
P=Primes()
res=[]
q_irr=irreducible(p,n)
q_cycle=almost_cycle(p,n)
q_tranposition=two_cycle(p,n)
q_four_cycle=four_cycle(p,n)
res.append([p, [q_irr, q_cycle, q_tranposition, q_four_cycle]])
res  
%%time
p=617
P=Primes()
p=P.next(p)
n=10**6
P=Primes()
res=[]
q_irr=irreducible(p,n)
q_cycle=almost_cycle(p,n)
q_tranposition=two_cycle(p,n)
q_four_cycle=four_cycle(p,n)
res.append([p, [q_irr, q_cycle, q_tranposition, q_four_cycle]])
res 
%%time
p=619
P=Primes()
p=P.next(p)
n=10**6
P=Primes()
res=[]
q_irr=irreducible(p,n)
q_cycle=almost_cycle(p,n)
q_tranposition=two_cycle(p,n)
q_four_cycle=four_cycle(p,n)
res.append([p, [q_irr, q_cycle, q_tranposition, q_four_cycle]])
res 
%%time
p=631
P=Primes()
p=P.next(p)
n=10**6
P=Primes()
res=[]
q_irr=irreducible(p,n)
q_cycle=almost_cycle(p,n)
q_tranposition=two_cycle(p,n)
q_four_cycle=four_cycle(p,n)
res.append([p, [q_irr, q_cycle, q_tranposition, q_four_cycle]])
res 
%%time
p=641
P=Primes()
p=P.next(p)
n=10**6
P=Primes()
res=[]
q_irr=irreducible(p,n)
q_cycle=almost_cycle(p,n)
q_tranposition=two_cycle(p,n)
q_four_cycle=four_cycle(p,n)
res.append([p, [q_irr, q_cycle, q_tranposition, q_four_cycle]])
res<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.179977041653001, 'fraction_numerical': 0.05551000327976386, 'mean_word_length': 5.910481586402266, 'pattern_counts': {'":': 0, '<': 28, '<?xml version=': 0, '>': 19, 'https://': 0, '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': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '145378', 'license': 'MIT', 'n_tokens_mistral': 6376, 'n_tokens_neox': 5709, 'n_words': 1386, 'path': 'computations_with_f.ipynb', 'repo_name': 'tungprime/Fekete-polynomials-Calculations', 'size': '12196'}