How to resolve the algorithm Chernick's Carmichael numbers step by step in the Julia programming language

Published on 22 June 2024 08:30 PM
#Julia

How to resolve the algorithm Chernick's Carmichael numbers step by step in the Julia programming language

Table of Contents

Problem Statement

In 1939, Jack Chernick proved that, for n ≥ 3 and m ≥ 1: is a Carmichael number if all the factors are primes and, for n > 4, m is a multiple of 2^(n-4).

For n = 5, the smallest number m that satisfy Chernick's conditions, is m = 380, therefore U(5, 380) is the smallest Chernick's Carmichael number with 5 prime factors. U(5, 380) is a Chernick's Carmichael number because m = 380 is a multiple of 2^(n-4), where n = 5, and the factors { (6380 + 1), (12380 + 1), (18380 + 1), (36380 + 1), (72*380 + 1) } are all prime numbers.

For n ≥ 3, let a(n) be the smallest Chernick's Carmichael number with n prime factors.

Note: it's perfectly acceptable to show the terms in factorized form:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Chernick's Carmichael numbers step by step in the Julia programming language

This code implements the algorithm to find the Chernick-Carmichael numbers for a given range of natural numbers. A Chernick-Carmichael number is a number that is simultaneously a Carmichael number and a Chernick number.

  • A Carmichael number is a number n for which there exists a number a such that a^n - 1 is divisible by n for all a coprime to n.
  • A Chernick number is a number n such that all the factors of n - 1 are prime numbers.

The program first defines two functions, trial_pretest and gcd_pretest, which perform some preliminary checks on the input number k to determine if it is likely to be a Chernick-Carmichael number.

The is_chernick function then checks if the given numbers n and m satisfy the properties of a Chernick-Carmichael number. It does this by performing a series of trial divisions and gcd calculations.

The chernick_carmichael function computes the Carmichael number corresponding to the given n and m.

Finally, the cc_numbers function iterates over the range of numbers from from to to and finds and prints the Chernick-Carmichael numbers in that range.

The output of the program is a list of the Chernick-Carmichael numbers in the given range.

Source code in the julia programming language

using Primes

function trial_pretest(k::UInt64)

    if ((k %  3)==0 || (k %  5)==0 || (k %  7)==0 || (k % 11)==0 ||
        (k % 13)==0 || (k % 17)==0 || (k % 19)==0 || (k % 23)==0)
        return (k <= 23)
    end

    return true
end

function gcd_pretest(k::UInt64)

    if (k <= 107)
        return true
    end

    gcd(29*31*37*41*43*47*53*59*61*67, k) == 1 &&
    gcd(71*73*79*83*89*97*101*103*107, k) == 1
end

function is_chernick(n::Int64, m::UInt64)

    t = 9*m

    if (!trial_pretest(6*m + 1))
        return false
    end

    if (!trial_pretest(12*m + 1))
        return false
    end

    for i in 1:n-2
        if (!trial_pretest((t << i) + 1))
            return false
        end
    end

    if (!gcd_pretest(6*m + 1))
        return false
    end

    if (!gcd_pretest(12*m + 1))
        return false
    end

    for i in 1:n-2
        if (!gcd_pretest((t << i) + 1))
            return false
        end
    end

    if (!isprime(6*m + 1))
        return false
    end

    if (!isprime(12*m + 1))
        return false
    end

    for i in 1:n-2
        if (!isprime((t << i) + 1))
            return false
        end
    end

    return true
end

function chernick_carmichael(n::Int64, m::UInt64)
    prod = big(1)

    prod *= 6*m + 1
    prod *= 12*m + 1

    for i in 1:n-2
        prod *= ((big(9)*m)<<i) + 1
    end

    prod
end

function cc_numbers(from, to)

    for n in from:to

        multiplier = 1

        if (n > 4) multiplier = 1 << (n-4) end
        if (n > 5) multiplier *= 5 end

        m = UInt64(multiplier)

        while true

            if (is_chernick(n, m))
                println("a(", n, ") = ", chernick_carmichael(n, m))
                break
            end

            m += multiplier
        end
    end
end

cc_numbers(3, 10)

You may also check:How to resolve the algorithm Increment a numerical string step by step in the i programming language
You may also check:How to resolve the algorithm Detect division by zero step by step in the Clojure programming language
You may also check:How to resolve the algorithm Ramer-Douglas-Peucker line simplification step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Integer sequence step by step in the Scheme programming language
You may also check:How to resolve the algorithm Munching squares step by step in the Mathematica/Wolfram Language programming language