sidef-scripts/Math/is_lucas-carmichael_number.sf

#!/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