Prime, ePrim, mePri, imePr, rimeP ... and Gamma

Circular primes

Task 1 asks us to identify the first 10 circular primes: that is, prime numbers which when permuted by repeatedly moving the last digit to the start are still prime.

Although not stated, but implied by the supplied answer, the answers are all the lowest value permutation of the given string of digits - so for example 197 is an answer but not 719 or 971.

My simple solution uses good old Eratosthenes's sieve to generate the primes. Then for each prime we can permute the digits, immediately moving on the next candidate if:

• the permuted value is not prime, or
• the permuted value matches an already-identified circular prime (for the reason stated in the second paragraph above)

Since Mohammad was kind enough to share the answer, we know that the 10th circular prime is a 6-digit number - 199 933 - and we might be tempted to limit the size of our sieve to that number.  However, some of its permutations considerably exceed the number itself, for example 999 331, so I ran the sieve up to 1 000 000.

I debated how to permute the digits of a multidigit number and settled on:

$c =~ m|(.*)(.)|;

$c = $2 . $1;

It's been stated in previous reviews that substr() is faster:

$c = substr($c, 1, 99) . substr($c, 0, 1);

but I couldn't measure the difference - if any.

Gamma functions

It's just about 50 years since I completed my PhD and I don't recall using a gamma function since then. I do, though, remember that for an integer j, gamma(j) is (j-1)! But that doesn't help much.

Fortunately the kind people at Wikipedia have provided some Python code to implement the required approximation, and I was able to translate that easily into Perl, handling the complex numbers with Math::Complex. I'd never used Math::Complex before, and I must say it's very easy to use - compared, for example, to BigInt.

Now you could complain that I haven't really answered the question because I didn't compute the parameters, but at least I've produced working code, and in the real world, that's what counts.

D00DlE5

We are asked for a list of 2-8 letter words comprising which can be spelled with the symbols ABCDEF0157 with 0 read as O, 1 as either I or L, 5 as S and 7 as T.

The operations required on any word are:

• discard if not 2-8 letters long
• discard if contain anything not in ABCDEFOLIST
• anything left is a solution

From the supplied dictionary there are 1464 such words.

I found that having 1 represent I or L made for some hard to read solutions such as 1111C17 (illicit), so eliminating 1 -> L reduced the number to 693.

For the first optional extra I limited the number of 'special' substitutions to 3, which reduced the number to 559, losing such words as DE5I57ED (desisted).

The second optional extra, requiring us to make 8-letter phrases from these words is a little trickier. Given that the words vary from 2-8 letters long, they could be combined as follows:

2 + 6, 3 + 5, 4 + 4, 2 + 2 + 4, 2 + 3 + 3, 2 + 2 + 2 + 2

Of the 559 words from optional extra 1, 15 have 2 letters, 69 have three letters, 139 have 4 letters, 125 have 5 letters and 109 have 6 letters.

So:

2 + 6 combinations total 1635

3 + 5 -> 8625

4 + 4 -> 19321

2 + 2 + 4 -> 31275

2 + 3 + 3 -> 71415

2 + 2 + 2 + 2 -> 50625

So there are 182896 possible phrases, of which most are probably not 'phrases' that one would use, and while it would be easy enough to generate them all, I didn't.

Directory compare

The logic of this is:

• Loop over directories and files
• Find the longest file name (to determine column width)
• Create %files with key = file name and value = a list of the containing directories
• Create a string ($all) that indicates the file is in all directories

Print the heading lines using the longest file name (above) to determine column width and then:

• Loop over directories and files
• Skip file if $files{$file} eq $all
• Print the file name in every column that appears in $files{$file}

Getting the columns to line up is a little messy, made slightly worse by the example have one fewer vertical line than columns. The %-s format in sprintf comes in useful for padding the file names to the right width.

Dots, lines and whatever fits best

Scalable Vector Graphics

SVG has always been a popular technology with me. Amongst other things, I've used it for making scale drawings for alterations to my house, and for making easily scalable or re-colourable logos for websites. For images which don't contain photographic material SVG files are often tiny in size when compared to compressed bitmaps like JPEG or PNG. But although many (most?) web browsers can render them, it's quite unusual to find them in use.

In my experience, Inkscape is the best GUI editor for SVG graphics, though its output is rather more verbose than that from the Perl SVG module.

Both tasks this week require us to draw lines and points in a 2-dimensional space. Once you've mastered the syntax required, the task is fairly simple, although there is one catch to be surmounted, which is that SVG's geometry is 'left-handed'. The normal convention for Cartesian (ie x and y) coordinates is that the positive direction of the y axis is 90 degrees anti-clockwise from the positive x axis. So in a rectangular container, if you place the origin (x = y = 0) at the bottom left, every point within the container has a positive x and y.

SVG uses the convention that the positive direction of the y axis is 90 degrees clockwise from that of the x axis. That means that in order to get the positive x and y valued points within a rectangle, the origin has to be at the top left, which is upside down to the normal convention.

So, I chose to write my code so that, in SVG terms, it transforms every (x, y) to (x, height - y) where 'height' is the height of the container, which draws the diagram in the way we were all taught at school.

Task 1 simply asks that we plot a number of points and lines, so I chose to draw a house, comprised of 5 points and six lines:

Sadly, Blogger doesn't accept embedded SVG so this is a PNG representation.

Task 2 also asks us to plot points, but asks for a least-squares best fit line. There are several ways to derive such a line, but I used the one most-commonly used experimentally, which is to assume that the errors - that is, the amount by which the points deviate from the line - are in y and not x. So if you draw a vertical line from each point to the least-squares line, we are looking for the line that minimises the sum of the squares of the lengths of these lines.

If the equation of that line is y = a + bx, it can be shown that:

     n * sum(x[i] * y[i]) - sum(x[i]) * sum(y[i])

b =  --------------------------------------------

           (sum(x[i]^2) - sum(x[i])^2) / n

a = (sum(y[i] - b * sum(x[i]) / n

where n is the number of points, and the points have coordinates x[i], y[i].

Again I chose to draw with y increasing in the upward direction and I have shown a rectangle which just encloses the supplied points - ie the bottom is not y = 0 and the left side is not x = 0:

The least squares line is y = 200.1 - 0.3000 x.

 

Palindromic primes and moody numbers

Palindromic primes

As this is a simple task it seems fairer to generate the primes rather than using an imported module.

So let's loop over 2 to 1000, discarding anything that's divisible by a prime we've already found, which leaves us with a new found prime.

And now we have to reverse its digits and see whether the forward and reverse versions are the same. There are various ways to reverse the digits, but a simple one-liner like

$reverse = $reverse . $1 while $j =~ m|(.)|g;

seems to do the trick quickly enough.

It's interesting that the last of the 20 primes < 1000 is 929 and then there isn't another one until 10301. So there are no 4-digit palindromic primes, and I'm sure some clever person will tell us why.

Moody numbers

1 Take a positive integer p. 
2 Set q = p
3 Compute s, the sum of the squares of the digits of q.
4 If s is 1 then p is happy. Stop.
5 If s is a previously seen value of s then p is sad. Stop.
6 Set  q = s and go back to step 3.

This isn't too hard to code, and the required 8 happy numbers are easily within the ambit of Perl integers.

The harder bit, though, is generating the output in the format specified by Mohammad. I got all the '=>' lining up as required, but lost the will to live before lining up the squares under the corresponding digits.

Lot of ands and a strange grid

Sum of the ands

We are given a list of positive integers and asked to add together the results of and-ing all possible pairs.

The obvious (to me) way of doing this is two nested loops to generate the number pairs, 'and' them together and add the result to a successive sum.

The slightly trickier part is to output the result in the format Mohammad asks, but if we just add to the eventual output within the inner loop we can get a single 'say' for the output.

A strange grid

We are again given a list of positive numbers and asked to generate a triangular array according to certain rules. These rules don't seem quite to match the examples, so I took the examples as being definitive.

The first row of the output is just the input.

The nth row then has n - 1 blank columns, and subsequent columns contain the sum of the cell to the left and the cell above.

Again, there is the issue of producing pretty output, and I chose to output all the cells one character wider than the final cell, which is always going to be the largest number.