trial_division_with_primorials.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 05 January 2020
# https://github.com/trizen

# Find all the prime factors of a given number `n` that are below a given bound `B`.

func primorial_trial_factor(n, k) {
    var g = gcd(n, k)

    g > 1 || return []     # no small factors

    g.factor.map {|p|
        [p, n.valuation(p)]
    }
}

var k = 1e7.primorial

for n in (100..126) {
    say ("2^#{n} + 1 = ", primorial_trial_factor(2**n + 1, k).map_2d {|p,e|
        (e == 1) ? p : "#{p}^#{e}"
    }.join(' * '), ' * ...')
}

__END__
2^100 + 1 = 17 * 401 * 61681 * 340801 * 2787601 * ...
2^101 + 1 = 3 * ...
2^102 + 1 = 5 * 13 * 137 * 409 * 953 * 3061 * 13669 * 26317 * ...
2^103 + 1 = 3 * ...
2^104 + 1 = 257 * ...
2^105 + 1 = 3^2 * 11 * 43 * 211 * 281 * 331 * 5419 * 86171 * 664441 * 1564921 * ...
2^106 + 1 = 5 * ...
2^107 + 1 = 3 * 643 * ...
2^108 + 1 = 17 * 241 * 433 * 38737 * ...
2^109 + 1 = 3 * ...
2^110 + 1 = 5^2 * 41 * 397 * 2113 * ...
2^111 + 1 = 3^2 * 1777 * 3331 * 17539 * ...
2^112 + 1 = 449 * 2689 * 65537 * ...
2^113 + 1 = 3 * 227 * 48817 * ...
2^114 + 1 = 5 * 13 * 229 * 457 * 131101 * 160969 * 525313 * ...
2^115 + 1 = 3 * 11 * 691 * 2796203 * ...
2^116 + 1 = 17 * 59393 * ...
2^117 + 1 = 3^3 * 19 * 2731 * ...
2^118 + 1 = 5 * 1181 * 3541 * 157649 * 174877 * 5521693 * ...
2^119 + 1 = 3 * 43 * 43691 * ...
2^120 + 1 = 97 * 257 * 673 * ...
2^121 + 1 = 3 * 683 * 117371 * ...
2^122 + 1 = 5 * 733 * 1709 * 3456749 * ...
2^123 + 1 = 3^2 * 83 * 739 * 165313 * ...
2^124 + 1 = 17 * 290657 * ...
2^125 + 1 = 3 * 11 * 251 * 4051 * ...
2^126 + 1 = 5 * 13 * 29 * 37 * 109 * 113 * 1429 * 14449 * ...