All about primes

Additive primes

... are prime numbers whose digits sum to a prime.  Given that I've resorted to using is_prime from Math::Prime::Util, there isn't much left to do.

One could try a number of ways of summing the digits.  Perhaps the neatest (version 1) is:

$sd = 0;

$sd += $1 while $n =~ m|(\d)|g;

- a single line and reasonably comprehensible, and works for a bigint.  

Another thought (version 2) was:

$n =~ s|(\d)|$1+|g;

$sd = eval($n . '0');

This inserts a plus after each digit of $n, appends a zero and evals the resulting sum.

And the arithmetic way (version 3):

while ($n > 0) {

    $sd += $n % 10;

    $n = int($n / 10);

}

So which is the most efficient?  I tested them each on a 20-digit number, running the sum a million times, and the results were:

Version 1 - 23 seconds

Version 2 - 89 seconds

Version 3 - 15 seconds.

So version 2 loses out, probably because the eval means invoking the compiler and probably also prevents any optimisation.  But probably they would all be fine for any real-world task.

Cuban primes

The first series of Cuban primes are the values of 3y^2 + 3y + 1 for y = 1, 2, ... which are prime. 

There seems little benefit in optimising the calculation, but given that we have to test for all values of y, it's worth noting that:

candidate[y]     = 3y^2       + 3y       + 1

candidate[y + 1] = 3(y + 1)^2 + 3(y + 1) + 1

   = 3y^2 + 9y + 7

   = candidate[y] + 6(y + 1)

So we can zip through the candidate values by simply adding 6(y + 1) to the previous one, and then is_prime is your friend.

Mean Brazilians

Task 1 - Pythagorean means

I'm never quite sure what is wanted or considered good in these tasks.  The options seem to be:

1. There's a module to do this
2. I can do this in one somewhat inscrutable line
3. I can do this in a readable way with lots of comments

If we're aiming to save coder time and not reinventing the wheel, then option 1 is clearly correct. I would almost always use that in a production environment.

Option 2 gives people a chance to demonstrate how compact - and maybe fast - Perl can be, which is a valid aim.  If the code is never going to be changed then it's fine, but I suspect that whoever has to come along later and maintain it - even if that's you - is going to scratch their heads for a while.

Option 3 is the way to go if you're trying to write easily maintainable code. It may not be the fastest solution - although often it is easily fast enough.

So for this task I went squarely for option 3: code it just as it's explained in Wikipedia, ie take the list elements one at a time and produce a running sum, product and sum of reciprocals.

And as always, I try to produce output just as Mohammad specifies.

Task 2 - Brazilian numbers

I've never been to Brazil, but maybe that's not necessary.  I have to say I didn't find the statement of the task very easy to understand, but as always Wikipedia came to my aid.

My solution simply checks $n in every base up to $n/2. You can stop there, because any higher base will give representations between 1x (where x is the representation of (base - 1), eg 9 in decimal) down to 11. That means that I don't quite replicate Mohammad's example output because, for example, I don't check 6 base 4 because I know it won't be a repeating number.

And another reason for not going beyond base $n/2 is that for base $n you need $n symbols to represent a number. I used 0-9, A-Z, a-z and then 10 punctuation symbols, giving 72 symbols and - using my algorithm - the ability to check $n up to about 200.

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.

Bigint week

Both our tasks this week require us to use integers greater than 2^64. I used the Math::Bigint module to handle those.

Task 1:  Fortunate numbers

The definition of Fortunate numbers leads to the following basic algorithm for finding them:

• Loop over n = 1 to something big
• Calculate the product of the first n primes (pn)
• Loop over m = 2 to something else big
• Calculate pn + m and check if it's prime

People cleverer than me will have thought (or known) of a better way, but mine works and is easy to understand.

However, pn increases very steeply and pn(17) is the largest that will fit into 64 bits, so Bigint is needed to represent pn for larger ones.  And also, pn + m will be bigint-ish which makes it hard to determine its primality, but fortunately Math::Prime::Util can do that, though for very large numbers it's guessing a bit.

My algorithm finds the first 20 Fortunate numbers - confirmed by the OEIS - in a couple of seconds even on a slow processor.

However, it is not immediately obvious that there isn't example of, say m = 11, for some huge n that I didn't explore.

Task 2: Fibonacci related patterns

It is asserted that if you create a sequence where each term is the corresponding member of the Fibonacci series modulo n, for any n, the sequence is a repeating pattern.

Perl is really good at patterns, so I approached this as follows:

• Create the Fibonacci series up to a big number (big)
• Create a string by concatenating the members of the series, modulo n
• Loop over 2 to a medium-sized number - this is the length of the repeat, pp
• So the unit that (maybe) repeats comprises chars 0 to pp-1 of the string
• Make another string containing enough copies of the unit to be longer than big, and then truncate it to big characters
• We have a result if 'another string' is the same as 'string'.

In order to cope with n being more than 10, all the moduli are represented as a single character, eg for n=16 the usual 0-9A-F but then running through to Z and then a-z, so that the algorithm can cope with n up to 62.  Again, the larger members of the series (beyond the 94th) exceed the capacity of 64 bits, so Bigint is needed again.

And just to show that it works,  I set big to be 1000, pp to go up to 40, and it runs in a few seconds up to p(62), which is 30 as per the OEIS.

And there's always a however.  If the modulo sequence for some number, say, goes 01234012340123401234 ... 44 with the 5 character sequence repeating 200 times followed by 44, my algorithm will not catch that.  It could be that the repeat is 1001 characters long. But perhaps someone has proved that that won't happen - ie that there is an upper bound for the length of the repeat?