Step by Step solution about How to resolve the algorithm Composite numbers k with no single digit factors whose factors are all substrings of k step by step in the Java programming language

The Java program CompositeNumbersK finds the first 20 composite numbers k which satisfy the following conditions:

• k is divisible by 11^2, but not by 3, 5, or 7.
• The prime factors of k are all digits of k.

The program uses the Pollard's rho algorithm to find the prime factors of k. The algorithm starts with a random number x and iterates the following formula:

x = (x^2 + c) mod n

where c is a constant and n is the number to be factored. The algorithm stops when x and 2x have a common factor. This factor is then used to find the prime factors of n.

Here's a breakdown of the Java program:

1. The main method initializes a list result to store the first 20 composite numbers that satisfy the given conditions. It sets the initial value of k to 11^2 and initializes a loop that continues until 20 numbers have been added to the list.

2. Inside the loop, the program checks if k is divisible by 3, 5, or 7. If it is, k is incremented by 2 and the loop continues.

3. If k is not divisible by 3, 5, or 7, the program calls the primeFactors method to find the prime factors of k. If k has more than one prime factor and all of its prime factors are digits of k, k is added to the result list.

4. After finding the composite numbers that satisfy the given conditions, the program prints them to the console.

5. The primeFactors method takes an integer aK as input and returns a list of its prime factors. The method first checks if aK is less than or equal to 1. If it is, the method returns an empty list.

6. If aK is greater than 1, the method converts aK to a BigInteger and checks if it is a probable prime number. If it is, the method adds aK to the list of prime factors and returns the list.

7. If aK is not a probable prime number, the method calls the pollardsRho method to find a factor of aK. The method then recursively calls itself to find the prime factors of the factor and aK divided by the factor. The prime factors are then added to the list and returned.

8. The pollardsRho method takes a BigInteger aN as input and returns a factor of aN. The method first initializes a constant constant and a random BigInteger x. The method then enters a loop that continues until the greatest common divisor (GCD) of x and 2x is greater than 1.

9. Inside the loop, x is updated using the Pollard's rho algorithm formula. The GCD of x and 2x is then calculated and checked. If the GCD is greater than 1, the method returns the GCD.

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;

public final class CompositeNumbersK {

	public static void main(String[] aArgs) {
		int k = 11 * 11;
		List<Integer> result = new ArrayList<Integer>();
		while ( result.size() < 20 ) {
		    while ( k % 3 == 0 || k % 5 == 0 || k % 7 == 0 ) {
		        k += 2;
		    }
		    
		    List<Integer> factors = primeFactors(k);
    	    if ( factors.size() > 1 ) {
    	        String stringK = String.valueOf(k);
    	        if ( factors.stream().allMatch( factor -> stringK.indexOf(String.valueOf(factor)) >= 0 ) ) {
    	            result.add(k);
    	        }
    	    }
    	    k += 2;		    
		}
		
		for ( int i = 0; i < result.size(); i++ ) {
			System.out.print(String.format("%10d%s", result.get(i), ( i == 9 || i == 19 ? "\n" : "" )));
		}
	}
	
	private static List<Integer> primeFactors(int aK) {		
		List<Integer> result = new ArrayList<Integer>(); 
		if ( aK <= 1 ) { 
			return result;
		}
		
		BigInteger bigK = BigInteger.valueOf(aK);
		if ( bigK.isProbablePrime(CERTAINTY_LEVEL) ) {
			result.add(aK);
			return result;
		}
		
		final int divisor = pollardsRho(bigK).intValueExact();
		result.addAll(primeFactors(divisor));
		result.addAll(primeFactors(aK / divisor));
		Collections.sort(result);
		return result;
	}		
	
	private static BigInteger pollardsRho(BigInteger aN) {
		final BigInteger constant  = new BigInteger(aN.bitLength(), RANDOM);
		BigInteger x  = new BigInteger(aN.bitLength(), RANDOM);
		BigInteger xx = x;
		BigInteger divisor = null;
		
		if ( aN.mod(BigInteger.TWO).signum() == 0 ) {
			return BigInteger.TWO;
		}
		
		do {
			x = x.multiply(x).mod(aN).add(constant).mod(aN);
			xx = xx.multiply(xx).mod(aN).add(constant).mod(aN);
			xx = xx.multiply(xx).mod(aN).add(constant).mod(aN);
			divisor = x.subtract(xx).gcd(aN);
		} while ( divisor.compareTo(BigInteger.ONE) == 0 );
		
		return divisor;
	}	
	
	private static final ThreadLocalRandom RANDOM = ThreadLocalRandom.current();
	private static final int CERTAINTY_LEVEL = 10;

}