Carmichael Numbers

Ruby

A Carmichael number is an odd composite number n which satisfies Fermat's little theorem

            a^(n-1)-1=0 (mod n)

for every choice of a satisfying (a,n)==1 (i.e., a and n are relatively prime) with 1 < a < n. Hence as known as Fermat liars.

r = (2..101)
primes = r.inject(r){|p, i| p.select{|n| n==i || n%i!=0}}

def tri xs, ys, zs
  xs.each {|x| 
  ys.each {|y| next y if y <= x
  zs.each {|z| next z if z <= y
    yield(x, y, z)
  }}}
end

tri(primes, primes, primes) {|x,y,z| n=x*y*z - 1
  if n%(x-1)==0 && n%(y-1)==0 && n%(z-1)==0
    print "#{n+1} = #{x} * #{y} * #{z}\n"
  end
}

def quad xs, ys, zs, ws
  xs.each {|x| 
  ys.each {|y| next y if y <= x
  zs.each {|z| next z if z <= y
  ws.each {|w| next w if w <= z
    yield(x, y, z, w)
  }}}}
end

quad(primes, primes, primes, primes) {|x,y,z,w| n=x*y*z*w - 1
  if n%(x-1)==0 && n%(y-1)==0 && n%(z-1)==0 && n%(w-1)==0
    print "#{n+1} = #{x} * #{y} * #{z} * #{w}\n"
  end
}

561 = 3 * 11 * 17
1105 = 5 * 13 * 17
2465 = 5 * 17 * 29
10585 = 5 * 29 * 73
1729 = 7 * 13 * 19
2821 = 7 * 13 * 31
8911 = 7 * 19 * 67
6601 = 7 * 23 * 41
15841 = 7 * 31 * 73
29341 = 13 * 37 * 61
46657 = 13 * 37 * 97
252601 = 41 * 61 * 101
62745 = 3 * 5 * 47 * 89
41041 = 7 * 11 * 13 * 41
101101 = 7 * 11 * 13 * 101
63973 = 7 * 13 * 19 * 37
126217 = 7 * 13 * 19 * 73
172081 = 7 * 13 * 31 * 61
75361 = 11 * 13 * 17 * 31
852841 = 11 * 31 * 41 * 61
2100901 = 11 * 31 * 61 * 101
340561 = 13 * 17 * 23 * 67
552721 = 13 * 17 * 41 * 61
2433601 = 17 * 37 * 53 * 73
2113921 = 19 * 31 * 37 * 97
9494101 = 23 * 61 * 67 * 101