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