123456789101112131415161718192021222324252627282930313233343536373839404142434445 |
- #!/usr/bin/ruby
- # Simple method for finding the smallest Carmichael number divisible by n.
- # See also:
- # https://oeis.org/A135721
- # https://oeis.org/A253595
- func carmichael_divisible_by(n) {
- n.is_even && return nil
- gcd(n, phi(n)) == 1 || return nil
- n >= 3 || return nil
- var c = n
- var t = n
- if (c.is_prime) {
- c = (c**2 - c)
- }
- c.is_carmichael && return c
- loop {
- t.is_carmichael && return t
- t += c
- }
- }
- assert_eq(carmichael_divisible_by(3), 561)
- assert_eq(carmichael_divisible_by(3*5), 62745)
- assert_eq(carmichael_divisible_by(7*19), 1729)
- assert_eq(carmichael_divisible_by(47*89), 62745)
- assert_eq(carmichael_divisible_by(5*47*89), 62745)
- assert_eq(carmichael_divisible_by(3*47*89), 62745)
- assert_eq(carmichael_divisible_by(3*89), 62745)
- say carmichael_divisible_by.map(primes(3..50))
- say 40.of(carmichael_divisible_by).grep
- __END__
- [561, 1105, 1729, 561, 1105, 561, 1729, 6601, 2465, 2821, 29341, 6601, 334153, 62745]
- [561, 1105, 1729, 561, 1105, 62745, 561, 1729, 6601, 2465, 2821, 561, 825265, 29341]
|