123456789101112131415161718192021222324252627282930313233343536373839404142434445464748 |
- #!/usr/bin/ruby
- # Daniel "Trizen" Șuteu
- # Date: 10 February 2020
- # https://github.com/trizen
- # Find factors of a number of special form, using the cyclotomic
- # polynomials C(n, b), for n = 1..floor(1+log_b(n)) and b fixed.
- # See also:
- # https://en.wikipedia.org/wiki/Cyclotomic_polynomial
- func cyclotomic_factorization(n, base=10) {
- var lim = n.ilog(base)+1
- gather {
- for k in (1..lim) {
- var t = cyclotomicmod(k, base, n)
- var g = gcd(n, t)
- g.is_between(2, n-1) || next
- while (g.divides(n)) {
- n /= g
- take([k, g])
- }
- }
- }
- }
- var n = ((10**258 - 1)/9 - 10**(258/2) - 1)
- cyclotomic_factorization(n).each { .say }
- __END__
- [2, 11]
- [2, 11]
- [4, 101]
- [6, 91]
- [8, 10001]
- [16, 100000001]
- [32, 10000000000000001]
- [64, 100000000000000000000000000000001]
- [86, 909090909090909090909090909090909090909091]
- [128, 10000000000000000000000000000000000000000000000000000000000000001]
- [258, 1098901098901098901098901098901098901098900989010989010989010989010989010989010989011]
|