Damian Conway

The first task of last week's Weekly Challenge was to print the
first ten strong and weak primes. A prime p_n is "strong" if it's larger
than the average of its two neighbouring primes (i.e. p_n > (p_n-1+p_n+1)/2).
A prime is "weak" if it's smaller than the average of its two neighbours.

Of course, this challenge would be trivial if we happened to have a list
of all the prime numbers. Then we'd just filter out the first ten that
are strong, and the first ten that are weak. In fact, it would be even
easier if we happened to have a list of all the strong primes, and a
list of all the weak ones. Then we'd just print the first ten of each.

But there are an infinite number of primes and of weak primes (and
possibly of strong primes too, though that's still only conjectured),
so building a complete list of the various subspecies of primes
is impractical in most programming languages.

Yet another of the things I love about Raku is how well it handles
infinite lists and sequences. Not having to worry about finite upper
limits simplifies a large number of tasks...and this is one of them.

The sequence of primes is just the sequence of positive integers,
filtered (with a .grep) to keep only the ones that are prime.
And, of course, Raku already has a prime number tester: the built-in
&is-prime function. The sequence of primes never changes, so we can
declare it as a constant:

constant p = [ (1..∞).grep( &is-prime ) ];

Now we need to extract just the strong and weak primes.
Given the earlier definitions of "strong" and "weak",
we get:

sub strong (\n) { n > 0 && p[n] > p[n-1, n+1].sum/2 }

sub weak (\n) { n > 0 && p[n] < p[n-1, n+1].sum/2 }

Note that p[n-1, n+1] is the list of p[n]'s two neighbours,
which we then add together (.sum) and average (/2).

These two strength tests operate on a prime's index, not its value,
so to generate the full lists of strong and weak primes, we need to
take those indices (p.keys), filter them to keep only the ones that
are strong or weak (another .grep) and then map each index
back to the corresponding prime.

Which gives us:

constant strong-p = [ p.keys.grep(&strong).map(->\n { p[n] }) ];

constant weak-p = [ p.keys.grep(&weak ).map(->\n { p[n] }) ];

That works fine, but it's a little clunky to have to convert all the
primes (p) back to indices (.keys), and then later convert
each index back to the corresponding prime: .map(->\n { p[n] })

So, instead, we could convert each prime in p to a key/value pair,
grep through just the keys, and then map out just the values.
Like so:

constant strong-p = p.pairs.grep(*.key.&strong).map(*.value);

constant weak-p = p.pairs.grep(*.key.&weak ).map(*.value);

...where *.key.&strong is just a shorthand for: -> \pair { strong( pair.key ) }
In other words, filter out the pairs whose keys, when passed to &strong, return True.

Or, even more simply, we could filter and test the indices and values
in a single mapping, using more readable names for the current prime
and its index. Like so:

constant strong-p = p.kv.map: ->\n,\pₙ {pₙ if strong n};

constant weak-p = p.kv.map: ->\n,\pₙ {pₙ if weak n};

That is: take the infinite list of primes (p) and convert it to an infinite list
of alternating key-then-value (p.kv). For each such index-then-prime,
call the index n and the prime pₙ (.map: ->\n,\pₙ),
then keep pₙ only if it is of the appropriate strength
({pₙ if strong n} or {pₙ if weak n}).

Whichever way we generate the infinite strong-p and weak-p lists,
printing the first ten of each is then trivial:

say 'strong primes: ', strong-p[^10];
say 'weak primes: ', weak-p[^10];

Note that in all the code shown above, all the greps and maps work
lazily, on-demand, and just-in-time. Each grep and map only iterates
through as many list elements as are required to produce the value at
the index you actually query (in this case: the values at indices 0
to 9). So it takes no more work to operate on these infinite lists
than it would to use finite lists.

In fact, it generally takes less work.

If we preferred to work with only a finite list of primes, we'd need to
magically know in advance (i.e. guess) how many primes were required to
guarantee that our lists contain at least ten strong and ten weak primes.

For example, we might reasonably assume that the first 1000 integers
would probably contain at least 10 strong and 10 weak primes,
so we could try:

constant p = [ (1..1000).grep(&is-prime) ];

And, indeed, that would work fine. Except that we just did
about ten times as much work as was actually required.

Or we might have guessed a tighter upper limit instead:

constant p = [ (1..100).grep(&is-prime) ];

which would have eliminated all the extra work, but which only works by
a happy accident. The 10^th strong prime is 97, but to test its strong-ness
correctly we'd need the following prime (101) as well. However, as we stopped
generating primes at 100, the &strong subroutine would have received an
undefined value when it requested that n+1^th prime. When used as a number,
that undefined value would convert to zero, so the average of 97's two prime
neighbours would be computed as (89+0)/2, which is certainly less than 97,
which would (erroneously, but correctly!) indicate that 97 is a strong prime.

That's not science; that's voodoo.

If we want to avoid the extra work of using an extremely conservative upper
limit (and the risk of error if our notion of "extremely conservative" isn't
quite conservative enough), then we need another approach. We need
to iterate through successive integers, locating successive primes, and then
testing their strengths, until we're absolutely sure we have enough of each.

Which would look something like:

# The various lists of primes are all initially empty...
my \p = [];
my \strong-p = [];
my \weak-p = [];

# The definitions of "strong" and "weak" (as before)...
sub strong (\n) { n > 0 && p[n] > p[n-1, n+1].sum/2 }
sub weak (\n) { n > 0 && p[n] < p[n-1, n+1].sum/2 }

# Try every integer i as a potential prime...
for 1..* -> \i {

# If it's actually prime...
if is-prime(i) {

# Add it to the list of known primes...
p.push(i);

# If there are enough known primes to test strengths...
if p.elems >= 3 {

# Can now test the second-last prime in the list...
my \n = p.end - 1;

# And add it to the appropriate list (if any)...
if strong(n) { strong-p.push( p[n] ) }
elsif weak(n) { weak-p.push( p[n] ) }
}
}

# Stop when we have at least 10 of each subspecies...
last if strong-p & weak-p >= 10;
}

# Print out the first ten of each...
say 'strong primes: ', strong-p[^10];
say 'weak primes: ', weak-p[^10];

That works correctly, and does no unnecessary calculations.

But it was much harder to write and it will be much harder
to read (and to verify, and to maintain), compared with:

# All the primes...
constant p = [ (1..∞).grep(&is-prime) ];

# The definitions of "strong" and "weak"...
sub strong (\n) { n > 0 && p[n] > p[n-1, n+1].sum/2 }
sub weak (\n) { n > 0 && p[n] < p[n-1, n+1].sum/2 }

# All the strong and weak primes...
constant strong-p = p.kv.map: ->\n,\pₙ {pₙ if strong n};
constant weak-p = p.kv.map: ->\n,\pₙ {pₙ if weak n};

# Print out the first ten...
say 'strong primes: ', strong-p[^10];
say 'weak primes: ', weak-p[^10];

Oh, and this declarative version is also four times faster
than the iterative solution.

Which is why, in Raku, infinite work is often less work.

Damian

PS: Those of you who are already familiar with Perl might have noticed
the complete absence of sigiled variables (such as: $n or @p) in the
examples above. Of course, Raku does have sigiled variables, but you
are not required to use them. You can use sigilless variables instead,
which are declared with a leading backslash:

my \p = [];

for 2..* -> \i {...}

sub strong (\n) {...}

...and then used without any leading punctuation whatsoever:

sub strong (\n) { n > 0 && p[n] >
p[n-1, n+1].sum/2 }

if is-prime(i) {
p.push(i);
}

So if the only thing that's been holding you back from
experimenting with this amazing new language is your
pathological fearutterly rational dislike of punctuated variables,
maybe it's time to give Raku a try after all?