Pernicious and weird ...

Pernicious numbers

... are positive integers which have a prime number of ones in their binary representation, and they can presumably have any number of zeroes as well.

Perl conveniently has the $binary = sprintf('%b', $n) construct which quickly gives us the binary representation of $n, and we can then count the 1s like this:

@ones = $binary =~ m|1|g;

This rather counterintuitive statement works because the m|| returns a list of matches which can then be assigned to an array, and the number of elements in the array thus gives the number of matches, or in our case, the number of 1s.

And as we've dealt with the generation of primes often in the last few weeks I took the lazy way out and used  Math::Prime::Util 'is_prime' to determine whether the count is prime.

Weird numbers

... are defined as those where the sum of the proper divisors (divisors including 1 but not the number itself) is greater than the number, but no subset of those divisors sums to the number.

So this breaks down to three steps:

• Find the proper divisors of n
• Check that their sum is greater than n
• Check that no combination of the divisors sums to n

For any modest value of n, step 1 is easy (just try every integer up to n/2) and step 2 is pretty trivial.  And fortunately step 2 eliminates the majority of values of n.

Step 3, though, is trickier, because if n has d divisors, there are 2^d - 1 subsets of these divisors, which can amount to quite a large number.  For example, n = 720 has 29 proper divisors, so 2^29 - about a billion - subsets of those divisors to check.

I optimised somewhat by ordering the subsets of divisors large to small, so that when I was adding them up I could stop once the sum exceeded n.  However, my algorithm was still defeated (ie took a very long time) by 720, though it could quickly determine that 836 was the second (after 70) weird number.

Probably someone will have come up with a weird algorithm to eliminate 720 more quickly, but my solution does at least meet the requirements of the challenge.