Step by Step solution about How to resolve the algorithm Chernick's Carmichael numbers step by step in the Mathematica / Wolfram Language programming language

Description

This Wolfram code implements the algorithm for finding the first Chernick-Carmichael number of a given order, i.e., the smallest number with a specified number of distinct prime factors.

Functions

• PrimeFactorCounts[n] calculates the total number of distinct prime factors of the integer n.

• U[n, m] is a polynomial formula used to generate candidate numbers.

• FindFirstChernickCarmichaelNumber[n] is the main function for finding the first Chernick-Carmichael number of a specified order n.

Algorithm (Inside FindFirstChernickCarmichaelNumber Function)

1. Initialization:

   • Set step to an initial search increment.
   • Set i to the starting value for the search.
   • Set formula to the U polynomial with m as the variable.
   • Print a progress indicator dynamically.

2. Search Loop:

   • While True:
     • Calculate value by substituting i for m in formula.
     • Check if value has the correct number of distinct prime factors (PrimeFactorCounts[value] == n).
       • If yes, break out of the loop.
       • If no, increment i by step.

3. Return Result:

   • Return the pair {i, value}, where i is the first m value that produces a number with the correct number of prime factors, and value is that number.

Example Usage

The code is used to find the first Chernick-Carmichael number for orders 3 to 9:

FindFirstChernickCarmichaelNumber[3]
FindFirstChernickCarmichaelNumber[4]
FindFirstChernickCarmichaelNumber[5]
FindFirstChernickCarmichaelNumber[6]
FindFirstChernickCarmichaelNumber[7]
FindFirstChernickCarmichaelNumber[8]
FindFirstChernickCarmichaelNumber[9]

Output

The output for the examples above will be pairs of the form {m, value}, where m is the first m value that produces a number with the specified number of prime factors, and value is that number.

ClearAll[PrimeFactorCounts, U]
PrimeFactorCounts[n_Integer] := Total[FactorInteger[n][[All, 2]]]
U[n_, m_] := (6 m + 1) (12 m + 1) Product[2^i 9 m + 1, {i, 1, n - 2}]
FindFirstChernickCarmichaelNumber[n_Integer?Positive] := 
 Module[{step, i, m, formula, value},
  step = Ceiling[2^(n - 4)];
  If[n > 5, step *= 5];
  i = step;
  formula = U[n, m];
  PrintTemporary[Dynamic[i]];
  While[True,
   value = formula /. m -> i;
   If[PrimeFactorCounts[value] == n,
    Break[];
    ];
   i += step
   ];
  {i, value}
  ]
FindFirstChernickCarmichaelNumber[3]
FindFirstChernickCarmichaelNumber[4]
FindFirstChernickCarmichaelNumber[5]
FindFirstChernickCarmichaelNumber[6]
FindFirstChernickCarmichaelNumber[7]
FindFirstChernickCarmichaelNumber[8]
FindFirstChernickCarmichaelNumber[9]