Anonymous user
Cyclotomic polynomial: Difference between revisions
→{{header|Python}}: re-nested code; stealing Perl 6's better looking superscripts
(→{{header|Python}}: re-nested code; stealing Perl 6's better looking superscripts) |
|||
Line 1,482:
=={{header|Python}}==
<lang python>from itertools import count, chain
from collections import deque
Line 1,501:
def factors(n):
for p in primes():
# prime factoring is such a non-issue for small numbers that, for
# this example, we might even just say
if p*p > n:
if n > 1:
Line 1,512 ⟶ 1,515:
if n%p != 0: break
yield p, cnt, n
# ^^ not the most
# two polimoials. A list p of integers means the product
def cyclotomic(n):
def poly_div(num, den):▼
▲ # Returns (list1, list2) representing the division between
▲ # (x^p[0] - 1) * (x^p[1] - 1) * ...
def elevate(poly, n): # replace poly p(x) with p(x**n)▼
powerup = lambda p, n: [a*n for a in p]
return poly if n == 1 else (powerup(poly[0], n), powerup(poly[1], n))▼
if n == 0:
return ([], [])
Line 1,526 ⟶ 1,537:
poly = cyclotomic(r)
return elevate(poly_div(elevate(poly, p), poly), p**(m-1))
▲def poly_div(num, den):
def to_text(poly):
def getx(c, e):
if e == 0:
return '1'
elif e == 1:
return 'x'
return 'x' + (''.join('⁰¹²³⁴⁵⁶⁷⁸⁹'[i] for i in map(int, str(e))))
parts = []
▲def elevate(poly, n): # replace poly p(x) with p(x**n)
coef = ' - ' if c == -1 else f' - {-c} '
else:
▲ return poly if n == 1 else (powerup(poly[0], n), powerup(poly[1], n))
coef = (parts and ' + ' or '') if c == 1 else f' + {c}'
parts.append(coef + getx(c,e))
return ''.join(parts)
def terms(poly):
# convert above representation of
def merge(a, b):
Line 1,572 ⟶ 1,588:
p = [(1, 0)] # 1*x^0, i.e. 1
for x in poly[0]: # numerator
p = mul(p, x)
Line 1,578 ⟶ 1,595:
return p
for n in chain(range(11), [2]):
▲for n in range(11):
print(f'{n}: {to_text(terms(cyclotomic(n)))}')
Line 1,590 ⟶ 1,606:
{{out}}
Only showing first 10 polynomials to avoid clutter.
<pre>0: 1
8: x⁴ + 1
105: x⁴⁸ + x⁴⁷ + x⁴⁶ - x⁴³ - x⁴² - 2 x⁴¹ - x⁴⁰ - x³⁹ + x³⁶ + x³⁵ + x³⁴ + x³³ + x³² + x³¹ - x²⁸ - x²⁶ - x²⁴ - x²² - x²⁰ + x¹⁷ + x¹⁶ + x¹⁵ + x¹⁴ + x¹³ + x¹² - x⁹ - x⁸ - 2 x⁷ - x⁶ - x⁵ + x² + x + 1
C[1]: 0
C[2]: 105
Line 1,625 ⟶ 1,641:
C[22]: 15015
C[23]: 15015
</pre>
=={{header|Sidef}}==
Solution based on polynomial interpolation (slow).
| |||