123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990 |
- #!/usr/bin/ruby
- # Generate imprimitive Carmichael numbers with n prime factors.
- func is_imprimitive(n) {
- n.factor.gcd_by { .dec }**2 > lambda(n)
- }
- var denominations = []
- func change(m, pos=0, solution=[]) {
- if (solution.len >= 2) {
- if (solution[-1] / solution[0] > 40) {
- #say '# here'
- return nil
- }
- }
- if (solution.len == m) {
- with (solution.prod) {|C|
- if (C.is_carmichael) {
- say C
- say "# Imprimitive: #{C}" if is_imprimitive(C)
- }
- }
- return nil
- }
- if (solution.len > m) {
- return nil
- }
- if (pos > denominations.end) {
- return nil;
- }
- change(m, pos + 1, solution);
- change(m, pos + 1, [solution..., denominations[pos]]);
- }
- func generate_imprimitive(p, m) {
- for z in (2..100) {
- var arr = []
- for k in (1 .. 2.sqrt**z) {
- k.is_smooth(5) || next
- #next if (2*5 > 40)
- var r = (2*k*p + 1)
- if (r.is_prime && (r.dec.gpf == p)) {
- arr << r
- }
- }
- var t = binomial(arr.len, m)
- t >= m || next
- t < 1e6 || break
- arr = arr.last(19448)
- var count = 0
- say "# Combinations: #{t}"
- denominations = arr
- change(m)
- #~ arr.combinations(m, {|*a|
- #~ with (a.prod) { |C|
- #~ break if (C > 325533792014488126487416882038879701391121)
- #~ #break if (C.gpf / C.lpf > 40)
- #~ if (C.is_carmichael) {
- #~ say C
- #~ say "# Imprimitive with p = #{p}: #{C}" if is_imprimitive(C)
- #~ }
- #~ }
- #~ #break if (++count > 1e5)
- #~ })
- }
- }
- for p in (primes(73..457)) {
- say "# p = #{p}"
- generate_imprimitive(p,10)
- }
|