Perl tricks by NEIL KANDALGAONKAR

Author: Neil Kandalgaonkar
Formatting: Laurent CAPRANI

Look here for a nicer version of this page that Neil made.

Contents

• Primality regex

  • How it works

  • Example

  • This vs. mine

Primality regex

I found the actual one-liner Abigail originally used from http://www.mit.edu:8008/bloom-picayune.mit.edu/perl/10138:

perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' [number]

How it works

STATEMENT if COND

Cool perl syntax, a statement may have 'modifiers' at the end like this. See man perlsyn.

shift

shift normally removes the first element of an array and returns that element, like popping from the beginning. Since we are in file scope, shift without array is magically interpreted to mean "shift @ARGV", which means the number we fed in as an argument. (see perldoc -tf shift).

1 x shift

x is the repetition operator. In this context, 1 is treated as a string "1". If the number was 9, "1" x 9 yields "111111111". (see man perlop, grep for 'repetition operator'.)

!~

The logical negation of =~, will succeed if the regex does NOT match. Since we are looking for primes, the regex will should match all NON-primes.

The regular expression

/

  ^1?$   # matches beginning, optional 1, ending.
         # thus matches the empty string and "1".
         # this matches the cases where N was 0 and 1
         # and since it matches, will not flag those as prime.

|   # or...

  ^                # match beginning of string
    (              # begin first stored group
     1             # match a one
      1+?          # then match one or more ones, minimally.
    )              # end storing first group
    \1+            # match the first group, repeated one or more times.
  $                # match end of string.

/x

Example

To see how it works let's consider the case of N = 9.

      1 1 1 1 1 1 1 1 1
START (\1)

      1 1 1 1 1 1 1 1 1
START (\1)[  ][  ][  ]

      1 1 1 1 1 1 1 1 1
START (\1)[  ][  ][  ]END

      1 1 1 1 1 1 1 1 1
START (\1)[  ][  ]END

      1 1 1 1 1 1 1 1 1
START (\1)[  ]END

      1 1 1 1 1 1 1 1 1
START ( \1 )

      1 1 1 1 1 1 1 1 1
START ( \1 )[    ][    ]      \1+

      1 1 1 1 1 1 1 1 1
START ( \1 )[    ][    ] END

So, you can see how this process is analogous to trying to divide a number by successively larger divisors, leaving no remainder. In the case of a prime number, this is never going to succeed.

This vs. mine

BTW: this also is much more efficient than the one I showed the group, with the addition of a single character!

My regex always had to backtrack from the maximal match; since Abigail made the 11+? match minimal it will start by trying to "divide" the number by 2, then 3, etc. It will reject 32000 instantly, and take somewhat longer to determine that 32003 is prime. A good reminder that backtracking doesn't always reduce the size of a matched portion; with minimal matches it will backtrack and try matching more.

Given the new no-backtrack grouping (?>) the useless attempts to match fewer amounts of \1+ could be eliminated. Benchmarking shows it is slightly faster that way.