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

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Chernick's Carmichael numbers step by step in the Wren 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 Wren programming language

Source code in the wren programming language

import "./big" for BigInt, BigInts
import "./fmt" for Fmt

var min = 3
var max = 9
var prod = BigInt.zero
var fact = BigInt.zero
var factors = List.filled(max, 0)
var bigFactors = List.filled(max, null)

var init = Fn.new {
    for (i in 0...max) bigFactors[i] = BigInt.zero
}

var isPrimePretest = Fn.new { |k|
    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
    return true
}

var ccFactors = Fn.new { |n, m|
    if (!isPrimePretest.call(6*m + 1)) return false
    if (!isPrimePretest.call(12*m + 1)) return false
    factors[0] = 6*m + 1
    factors[1] = 12*m + 1
    var t = 9 * m
    var i = 1
    while (i <= n-2) {
        var tt = (t << i) + 1
        if (!isPrimePretest.call(tt)) return false
        factors[i+1] = tt
        i = i + 1
    }
    for (i in 0...n) {
        fact = BigInt.new(factors[i])
        if (!fact.isProbablePrime(1)) return false
        bigFactors[i] = fact
    }
    return true
}

var ccNumbers = Fn.new { |start, end|
    for (n in start..end) {
        var mult = 1
        if (n > 4) mult = 1 << (n - 4)
        if (n > 5) mult = mult * 5
        var m = mult
        while (true) {
            if (ccFactors.call(n, m)) {
                var num = BigInts.prod(bigFactors.take(n))
                Fmt.print("a($d) = $i", n, num)
                Fmt.print("m($d) = $d", n, m)
                Fmt.print("Factors: $n\n", factors[0...n])
                break
            }
            m = m + mult
        }
    }
}

init.call()
ccNumbers.call(min, max)


  

You may also check:How to resolve the algorithm Vector products step by step in the PHP programming language
You may also check:How to resolve the algorithm Address of a variable step by step in the Common Lisp programming language
You may also check:How to resolve the algorithm Loops/Do-while step by step in the Vala programming language
You may also check:How to resolve the algorithm Sum multiples of 3 and 5 step by step in the MiniScript programming language
You may also check:How to resolve the algorithm Anagrams step by step in the Pointless programming language