Divisibility, Sieves and Masks - PWC 141

Here is my first attempt at solving the tasks in Perl Weekly Challenge (Week 141)

TASK #1 › Number Divisors

Submitted by: Mohammad S Anwar

Write a script to find lowest 10 positive integers having exactly 8 divisors.

Analysis:

At the heart of this task lies the subtask of finding number of divisors to a given number. Based on the input, there is no pressing need to optimise the performance. So, here is the brute force approach:

The Code:

number_divisors_task(10, 8);

sub number_divisors_task {
	my ($number_count, $divisor_count) = @_;
	
	my @desired_numbers;
	my $i = $divisor_count;
	while (@desired_numbers < $number_count) {
		if (number_of_divisors($i) == $divisor_count) {
			push @desired_numbers, $i;
		}
		$i++;
	}
	print "Lowest 10 positive integers having exactly 8 divisors\n";
	print join("\n", @desired_numbers);
}

sub number_of_divisors {
	my ($num) = @_;
	my $count = 0;
	foreach my $divisor (1 .. $num) {
		if ($num % $divisor == 0) {
			$count++;
		}
	}
	return $count;
}

Output:

$ perl pwc_141_1.pl
Lowest 10 positive integers having exactly 8 divisors
24	30	40	42	54	56	66	70	78	88

Optimisation:

The brute force method works in this scenario because we only need to find the first 10 numbers, but the time taken increases very rapidly when the first 100 numbers or first 1000 such numbers need to be found. That's because the above method has O(n^2) complexity.

Optimisation can be done by improving the number_of_divisors function. It can be modified to find the prime factors and number of divisors can be derived from that using the simple mathematical formula:

Suppose a number can be written as N = p1^c1 * p2^c2 * ... * pn^cn 

where p1, p2 etc are prime numbers then the total number of divisors = (c1 + 1) * (c2 + 1) * ... * (cn + 1)

But how to find the list of prime numbers less than a given number? Based on the definition, a number is prime if the total number of its divisors is equal to 2. So, here we are faced with a classic chicken egg problem. To find out divisors you need to know primes and to find out the primes, you need to know its divisors. Fortunately, there exists a more efficient way to find out all prime numbers less than a given number. Drumroll!!! "The Sieve of Eratosthenes".

This is how it works: Starting from the smallest prime, for each prime number, all it's multiples are filtered out except that number itself. The next smallest number remaining is prime and all its multiples are filtered out. This process is continued and all composite numbers are filtered out from the set one by one.

sub number_of_divisors {
	my ($num) = @_;
	
	# Find all primes below $num using Sieve of Eratosthenes
	# $primes is an arrayref with 1 at prime indices and 0 at composite indices
	my $primes = find_primes($num);
	my $count = 1;
	foreach my $prime (2 .. $num) {
		if ($primes->[$prime]) {
			if ($num % $prime == 0){
				$power = 0;		
				while ($num % $prime == 0) {
					$num = $num / $prime;
					$power++;
				}
				
				$count *= ($power+1);
			}			
		}
	}
	return $count;
}

sub find_primes {
	my ($num) = @_;
	
	my @primes = (1) x ($num+1);

	my $p = 2;
	while ($p * $p < $num) {
		if ($primes[$p]) {
			$i=2;
			while ($p * $i < $num) {
				$primes[$p * $i] = 0;
				$i++;
			}
		}
		$p++;
	}
	return \@primes;
}

TASK #2 › Like Numbers

Submitted by: Mohammad S Anwar

You are given positive integers, $m and $n.

Write a script to find total count of integers created using the digits of $m which is also divisible by $n.

Repeating of digits are not allowed. Order/Sequence of digits can’t be altered. You are only allowed to use (n-1) digits at the most. For example, 432 is not acceptable integer created using the digits of 1234. Also for 1234, you can only have integers having no more than three digits.

Analysis:

Breaking down the problem into two parts, we have:

• find the possible ministrings of $m satisfying the given conditions
• find how many of those are divisible by $n

The second part is trivial but the first part involves a bit of logic as discussed below.

The sequence of the digits should not be changed and repititions are not allowed, so the desired set of ministrings consists of 

• ministrings of length 1 (1, 2, 3, 4 in given example)
• ministrings of length 2 (12, 23, 34, 13, 14, 24 ) and so on....

The total number of such combinations can be proved to be 2^n where n is the number of digits. It also consists of ministring of length 0 (empty string '') and length n (the full string '1234') which we would like to ignore in our task.

Each one of these ministrings has a one to one correspondence with a binary code. Example the ministrings of length 1 (1, 2, 3, 4) correspond to binary codes 1000, 0100, 0010, 0001. So, the task boils down to finding the list of binary codes and using them as masks to derive the ministrings from the original number.

Solution:

$m = 1234;
$n = 2;
likenumbers_divisible($m, $n);

sub likenumbers_divisible {
	my ($m, $n) = @_;

	my $length = length($m);
	my @likenumbers;
	my $divisible_count = 0;
	# Get all binary masks of length $length excluding all zeroes and all ones.
	foreach my $i (1 .. (2 ** $length)-2) {
		my $mask = sprintf("%.${length}b", $i);
		my $ministring = '';
		#perform the masking operation to generate 23 from 1234 if mask is 0110.
		foreach my $i (0 .. $length-1) {
			$ministring .= substr($m, $i, 1) if substr($mask, $i, 1);
		}
		if ($ministring % $n == 0) {
			$divisible_count++;
		}
	}
	print "divisible_count: [$divisible_count]\n";
}

Output:

$ perl pwc_141_2.pl
divisible_count: [9]

Happy Coding everyone!