12345678910111213141516171819202122232425262728293031323334353637383940414243 |
- #!/usr/bin/ruby
- # Daniel "Trizen" Șuteu
- # Date: 30 March 2019
- # https://github.com/trizen
- # Prove if a given number `n` is a Lucas-Carmichael number, using the divisors of `n+1`.
- # See also:
- # https://en.wikipedia.org/wiki/Lucas%E2%80%93Carmichael_number
- # OEIS:
- # https://oeis.org/A322702 -- a(n) is the product of primes p such that p+1 divides n.
- # https://oeis.org/A006972 -- Lucas-Carmichael numbers: squarefree composite numbers n such that p | n => p+1 | n+1.
- func lucas_bernoulli_denominator (n) { # A322702
- n.divisors.grep {|d|
- d-1 -> is_prob_prime
- }.prod {|d|
- d-1
- }
- }
- func is_lucas_carmichael (n) {
- # Make sure `n` is not prime
- return false if (n<=1 || n.is_prime)
- # Is a Lucas-Carmichael number iff `n` divides Product_{d|n+1, d-1 is prime} (d-1).
- n.divides(lucas_bernoulli_denominator(n+1))
- }
- func is_lucas_carmichael_faster (n) {
- var f = n.factor_exp
- f.len >= 3 && f.all { .tail == 1 } && f.all {|p| (n+1) % (p.head+1) == 0 }
- }
- say is_lucas_carmichael.first(5) #=> [399, 935, 2015, 2915, 4991]
- say is_lucas_carmichael_faster.first(5) #=> [399, 935, 2015, 2915, 4991]
- __END__
- 399, 935, 2015, 2915, 4991, 5719, 7055, 8855, 12719, 18095
|