Euler #52

I was looking at the problems in Project Euler for things to do in Perl 6 and a few of them piqued my interest. The following is a minor adventure in implementing the solution to problem #52.

The problem is to find an integer such that twice the integer contains the same digits (obviously, in a different order) as three times the integer and the same digits as four times the integer and so on up to six times the integer. Here's the naive approach:

use v6;

my $n = 1;
loop {
   my $s = (2*$n).comb.sort;
   last if
       $s eq (3*$n).comb.sort &&
       $s eq (4*$n).comb.sort &&
       $s eq (5*$n).comb.sort &&
       $s eq (6*$n).comb.sort;
   $n++;
}

say $n;

Some interesting things to note if you're not familiar with Perl 6:

• there's a loop-forever construct
  
• method call syntax uses a dot
• everything is an object that you can call methods upon
  

See the official Perl 6 documentation for more information.

In order to check that the numbers have the same digits I needed to come up with some way to make a "signature" for each number such that numbers with the same digits have the same signature. I chose to do this by treating the numbers as a string of characters (a natural shift in thinking for Perl people), chopping up the string into a list of characters and sorting this list. For example, applying this process to the numbers "26321" and "62321" would both yield "12236", thus they have the same signature and the same digits.

To split the number into individual characters, you'd think that you would use the split subroutine and in Perl 5, you probably would. But Perl 6 has a shiny new routine called comb that acts as a counterpoint to split. In previous Perls, if you knew what you wanted to throw away from a string you would use split and if you knew what you wanted to keep, you'd use a regular expression capture (my @keep = $string =~ /\d/g). In Perl 6, split is the same, but comb is the routine of choice when you know the parts you want to keep. Given a regex, comb returns all parts of the string that match the regex. The default is to match single characters.

Like many things in Perl 6, there are both subroutine and object method forms. In the above code I use the method form of both .comb and .sort. (2*$n) gives me an integer that I then apply the .comb method to in order to turn the integer into a list of characters which I then apply the .sort method. Thus yielding an ordered list of the digits that comprise the integer in question.

But wait a second ... how can this work? If the result of using the .comb method is a list of characters and the .sort method sorts that list of characters, how can I use a string equality check on two lists? The answer is: Perl 6 magic! Because the lists are used as operands to the eq operator (a string operator), they get evaluated in string context. So, a number such as 26321 turns into the list ( '1', '2', '2', '3', '6') by .comb.sort which gets turns into "1 2 2 3 6" when evaluated as a string.

Neat, huh?

After I had coded this solution, it occurred to me that this approach could be improved. I think it was right around the time I got tired of waiting for an answer and hit Control-C to abort the run.

At some point 6*$n will be big enough that it will have more digits than 2*$n, thus making the probability that they have the same signature drop to 0. We can optimize a little by only examining those numbers where 2*$n and 6*$n have the same number of digits. How do I know how many digits they have? I could have just checked the length of each number, but I chose to use the logarithm function because I'm bent in a mathy sort of way.

The logarithm base 10 tells you how many digits are in a number. However, Perl 6's log function uses 2.718281828 (e) as its base, so I had to write a little routine that converts from base e to base 10.

Here's the improved code:

use v6;

sub log10($n) { return log($n) / log(10) }

my $mag = 1;        # current power of 10
my $n = $mag;       # number to start searching from
loop {
   my $s = (2*$n).comb.sort;
   last if
       $s eq (3*$n).comb.sort &&
       $s eq (4*$n).comb.sort &&
       $s eq (5*$n).comb.sort &&
       $s eq (6*$n).comb.sort;
   $n++;
   if log10(6*$n).int > log10(2*$n).int {
       $mag *= 10;
       $n = $mag;
   }
}
say $n;

I call the .int method on the return value of my log10 routine to get the integer portion of the logarithm. If the logarithm of 6*$n is greater than the logarithm of 2*$n, then I need to skip to the next power of 10. The variable $mag keeps track of the current power of ten that I am examining.

For the curious, here's the optimized code that checks the length of each number:

use v6;

my $mag = 1;        # current power of 10
my $n = $mag;       # number to start searching from
loop {
   my $s = (2*$n).comb.sort;
   last if
       $s eq (3*$n).comb.sort &&
       $s eq (4*$n).comb.sort &&
       $s eq (5*$n).comb.sort &&
       $s eq (6*$n).comb.sort;
   $n++;
   if (6*$n).chars > (2*$n).chars {
       $mag *= 10;
       $n = $mag;
   }
}
say $n;

Yes, it's simpler because I didn't need the log10 routine. But I did tell you I was bent. In Perl 6 the word "length" is outlawed because it isn't specific enough. It doesn't tell you what units you're getting. To ask, "what's the length of a string" you need to specify if you want the length in characters or bytes or graphemes or codepoints or whatever. To that end, there's now a .chars method that gives you the number of characters in a string.

Anyway ... that's a quick look at implementing problem #52 in Project Euler