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!

Being Random

We humans are interested in many things. We like to make generalisations of what we observe. Later we frame hypotheses and come up with theories. We go on to conclude that things happen the way they happen because of a reason and that's how they always happen.

At the other extreme, we are also fascinated by things that we can't systematically generalise. Those are the things that happen at random. Simply put, something is random if it can't be predicted. It is funny that many things that we really care about in our lives are random: occurrence of rain, the gender of a baby to be born, prices of shares in the share market, choosing the winner of a lottery  prize(if it is done honestly of course) etc.

Sometimes these random events bring sorrow to us. That grief increases because of the fact that we can't control them. But when they bring us good news, then our joy knows no bounds. A good thing happening is one thing whereas the same thing happening when it is least expected is totally another.

But one thing is true. Life will be very bland without this randomness. Just imagining that everything is systematic and can be predicted before it happens is very boring. In fact, life is all about uncertainty. We wake up everyday without knowledge of what life has in store for us for that day. We experience a thrill in exploring the unknown. We enjoy listening songs in shuffle mode. We watch anxiously to see which team wins the toss before a cricket match. All this is the beauty of randomness.

So when life gets boring, try something out of the ordinary, be unpredictable everyday. Surprise everyone. Join the madness, join me in... being random.