Pernicious Perfidy

Wherein we weigh the balance and seek a worthy opponent for all that is good in the world…

THE WEEKLY CHALLENGE – PERL & RAKU #156 Task 1

---

“Who knows what evil lurks in the hearts of men? The Shadow knows!”

---

Pernicious Numbers

Submitted by: Mohammad S Anwar

Write a script to permute first 10 Pernicious Numbers.

A pernicious number is a positive integer which has prime number of ones in its binary representation.

The first pernicious number is 3 since binary representation of 3 = (11) and 1 + 1 = 2, which is a prime.

Expected Output

3, 5, 6, 7, 9, 10, 11, 12, 13, 14

ANALYSIS

Pernicious numbers are a product of the dark side of number theory, or as I call it, dark number theory. And yes that is a totally real thing I didn’t just make up.

In dark number theory half the numbers are plain evil. And the numbers that are not evil are mearly odious. Numbers are wicked, and in groups — angry mobs set in action, descending on the castle — they can be monsterous.

The evil numbers are said to have an even population count, or Hamming weight, and the odious ones share the complementary odd fraction. Therefore, between the hammer and the anvil, all positive numbers are either evil or odious. The pernicious numbers, the topic of our task today, span the gap — they have the distinction of a prime Hamming weight, which makes them generally, but not exclusively, odious. However as 2 is prime, some can still be said to be outright evil.

The relative distribution amongst the numbers between evil and odiousness, dependent on parity, is quantified by their perfidy.

Some numbers, it seems, cannot be trusted. 13, for example, is obviously on the dark side, and perniciously odious; this is so obvious that 1313 Mockingbird Place was the fictional address of Herman Munster‘s home, patriarch of a television family of literal monsters. “13.13” is also the name of a record release by the musician Lydia Lunch. This recording is a fine record, full of wailing, dismal lyrics laid atop a psychedelic, even Beatlesque sonic backdrop, but apparently the animosity between Lunch and her backing band, members the Los Angeles punk group the Weirdos, was so great that she chose to allow the work to languish and refused to press more copies past the first run for literally decades.

Whole lot of evil going on there — wheels within wheels. Hail Satan, Lydia.

Oh, and now that we’ve finally brought up that particularly famous being, the OEIS sequence A051003, numbers containing the digit-sequence 666, are sometimes known as the hateful numbers, and viewed structurally, numbers with six-hundred and sixty-six digits represent the apocalypse numbers.

There is seemingly evil everywhere you look.

I will now make a conjecture:

For every person who has existed and will exist throughout history, somewhere there is a unique apocalypse number with their name on it.

Right then. How’s that for representing the dark side?

METHOD

To find the pernicious numbers we will need some sort of function to count the population of 1s in a binary representation. We first visited this idea in PWC 114, Integer Set Bits. We’ll also need a few prime numbers to compare the values to, but I wouldn’t stress to much about it as the primes to make 10 values will presumably be low values. However to avoid making any assumptions we’ll include an iterator to make additional primes as needed. Which, by the way, is three. Three primes. But hey, maybe we’ll want to compute more Pernicious Numbers someday, and we’ll be ready for the insidious onslaught.

Lets’s see: pop count function and a lookup hash of primes. That should do it.

PERL 5 SOLUTION

For a popcount() function we’ll first represent our candidate in binary using a sprintf format, then dice the string into individual digits, then sum them.

For the prime lookup, we can simultaneously build up an array, to keep track of the largest prime created so far, and a hash with the primes as keys for easy reference. Whenever the result of our popcount function is too large, new primes are generated until the look-up range encompasses it.

my $request = shift || 30;

my @perns;
my $candidate = 0;
my $p = prime_generator();
my @primes = $p->();
my %primes = ( $primes[-1] => 1 );

while (@perns <= $request) {
    my $pop = popcount( $candidate );
    push @primes, $p->() and $primes{$primes[-1]}++ until $primes[-1] > $pop;
    push @perns, $candidate if $primes{$pop};
    $candidate++;
}

say "@perns";

sub popcount ( $num, $sum = 0 ) {
    $sum += $_ for split '', sprintf "%b", $num;
    return $sum;
}

sub prime_generator {
## returns an iterator closure that once started 
## always delivers the next prime
    state @primes;
    
    return sub {
        if ( @primes < 2 ) {
            push @primes, @primes == 0 ? 2 : 3;
            return $primes[-1];
        }
    
        my $candidate = $primes[-1] ;
        CANDIDATE: while ( $candidate += 2 ) {
            my $sqrt_candidate = sqrt( $candidate );
            for my $test ( @primes ) {
                next CANDIDATE if $candidate % $test == 0;
                last if $test > $sqrt_candidate;
            }
            push @primes, $candidate;
            return $candidate;
        }
    }
}

And the results:

====================================================================
Mar 17, 2022 at 10:54:49 PM
~/Code/PWC/156-1-pernicious-perfidy.pl
--------------------------------------------------------------------
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 37 38 40 41 42 44

Raku Solution

The Raku is conspicuously more compact, which is an absurd understatement: chained built-in operators can manage the whole process in one line.

Reading left to right, we print the result of the following sequence of steps:

• Start with an iterator that generates an unlimited list of numbers.
• Then filter this list to allow only those values that:
  • when converted to base 2
  • and have their digits separated into an array of values
  • which is then summed
  • are prime

Got that? Good.

• Now we need as many as we initially requested. Search through as many candidates as you need.

unit sub MAIN ( $request = 30 ) ;

say ((1..*).grep({.base(2)
                  .comb
                  .sum
                  .is-prime}))[^$request];