with Raku

This is my response to the Perl Weekly Challenge #156.

Write a script to permute first

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

`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

This is quite easy, in a rather unpernicious way:

File: pernicious-numbers#! /usr/bin/env raku
unit sub MAIN (Int $length where $length > 0 = 10); # [1]
my $pn := (1..Inf).grep({ $_.fmt('%b').comb.sum.is-prime }); # [2]
$pn.head($length).join(", ").say; # [3]

[1] A positive number, with 10 as default value.

[2]
We start with the positive integers (`1..Inf`

),
convert them to binary representation (with `fmt`

, which is the
method form of `sprintf`

). Then we add the digits togeter
(`comb`

gets the inidivual digits, and `sum`

adds them
togeter - to get the number of ones in the string). And finally we apply
`is-prime`

to decde if that number (of ones) is a prime. All this is
inside a `grep`

, so that we get rid of non-matching values.

See
docs.raku.org/routine/fmt
more information about `fmt`

.

See
docs.raku.org/routine/is-prime
for more information about `is-prime`

.

[3] Print the specified number of elements (from the start of
«$pn»), with the `head`

metod.

See
docs.raku.org/routine/head
for more information about `head`

.

Running it:

$ ./pernicious-numbers
3, 5, 6, 7, 9, 10, 11, 12, 13, 14
./pernicious-numbers 100
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, 47, 48, 49, 50, 52, 55, 56, 59,\
61, 62, 65, 66, 67, 68, 69, 70, 72, 73, 74, 76, 79, 80, 81, 82, 84, 87, 88,\
91, 93, 94, 96, 97, 98, 100, 103, 104, 107, 109, 110, 112, 115, 117, 118,\
121, 122, 124, 127, 129, 130, 131, 132, 133, 134, 136, 137, 138, 140, 143,\
144, 145, 146, 148, 151, 152, 155, 157, 158, 160, 161

Looking good.

What about the Unpernicius Numbers, you may ask?

File: unpernicious-numbers```
#! /usr/bin/env raku
unit sub MAIN (Int $length where $length > 0 = 10);
my $pn := (1..Inf).grep({ $_.fmt('%b').comb.sum.is-prime.not });
$pn.head($length).join(", ").say;
```

[1] We simply invert the selection criteria with a postfix
`not`

.

See
docs.raku.org/routine/not
for more information about `not`

.

$ ./unpernicious-numbers
1, 2, 4, 8, 15, 16, 23, 27, 29, 30
$ ./unpernicious-numbers 25
1, 2, 4, 8, 15, 16, 23, 27, 29, 30, 32, 39, 43, 45, 46, 51, 53, 54, 57,\
58, 60, 63, 64, 71, 75

That was fun. Or perhaps not...

You are given number,

Write a script to find out if the given number is a

Example 1:

`$n > 0`

.
Write a script to find out if the given number is a

`Weird Number`

.
According to Wikipedia, it is defined as:

The sum of the proper divisors (divisors including 1 but not itself) of the number is greater than the number, but no subset of those divisors sums to the number itself.Example 1:

Input: $n = 12
Output: 0
Since the proper divisors of 12 are 1, 2, 3, 4, and 6, which sum to 16;
but 2 + 4 + 6 = 12.

Example 2:
Input: $n = 70
Output: 1
As the proper divisors of 70 are 1, 2, 5, 7, 10, 14, and 35; these sum
to 74, but no subset of these sums to 70.

We can get the divisors, proper or not, with my «divisors» procedure, presented in the program with same name in my Centenary Sequences with Raku - Part 5: Divisors and Factors article.

File: weird-number-exits#! /usr/bin/env raku
unit sub MAIN (Int $n where $n > 0); # [1]
my @proper-divisors = divisors($n, :not-self); # [2]
if (@proper-divisors.sum > $n) # [3]
{
for @proper-divisors.combinations -> @combination # [4]
{
if @combination.sum == $n # [4a]
{
say 0; # [4b]
exit;
}
}
say 1; # [5]
exit;
}
say 0; # [3a]
sub divisors ($number, :$not-self, :$not-one)
{
my @divisors;
for ($not-one ?? 2 !! 1) .. $number/2 -> $candidate
{
@divisors.push: $candidate if $number %% $candidate;
}
@divisors.push: $number unless $not-self;
return @divisors;
}

[1] We start with a positive integer.

[2] Get the proper divisors, which is all the divisors but the number itself.

[3] If the sum of the proper divisors is greater than than the number itself, we have a chance of succes. If not, we fail (print zero) [3a].

[4] For all the combinations (subsets) of divisors, is the sum equal to the number itself [4a]? If it is, we fail [4b].

[5] We have checked all the permutations without failing. Then we have succeeded. Say so.

Running it gives the expected result:

$ ./weird-number-exits 12
0
$ ./weird-number-exits 70
1

It is possible to make it shorter (getting rid of 2 exits):

File: weird-number-exit#! /usr/bin/env raku
unit sub MAIN (Int $n where $n > 0, :v(:$verbose));
my @proper-divisors = divisors($n, :not-self);
(say 0; exit) if @proper-divisors.sum <= $n; # [1]
say + ! so any(@proper-divisors.combinations>>.sum) == $n; # [2]
sub divisors ($number, :$not-self, :$not-one)
{
my @divisors;
for ($not-one ?? 2 !! 1) .. $number/2 -> $candidate
{
@divisors.push: $candidate if $number %% $candidate;
}
@divisors.push: $number unless $not-self;
return @divisors;
}

[1] A prefix block to `if`

instead of a single statement is ok. Parens, as
used here, are ok. As are curly brackets.

[2]
We use an `any`

Junction to decide
if any of the values match. Then we collapse the Junction to a single Boolean value with
the *Boolean Context Operator* `so`

. We got the opposite of what we
want, so negate the Boolean value with `!`

. And finally we convert the Boolean
value to an integer with the *Numeric Coercion Prefix Operator* `+`

.

Note that a Junction is a piece of code that could be evaluated in parallel. Raku does not seem to do that currently, though. (I am using Rakudo™ v2022.02.)

See
docs.raku.org/routine/any
for more information about the `any`

Junction.

See
docs.raku.org/routine/so for more
for more information about the *Boolean Context Operator* `so`

.

See
docs.raku.org/routine/+ for
more information about the Numeric Coercion Prefix Operator `+`

.

Running it gives the same result as before:

$ ./weird-number-exit 12
0
$ ./weird-number-exit 70
1

It is possible to make it even shorter (by getting rid of the final exit):

File: weird-number#! /usr/bin/env raku
unit sub MAIN (Int $n where $n > 0, :v(:$verbose));
my @proper-divisors = divisors($n, :not-self);
say @proper-divisors.sum <= $n # [1]
?? 0 # [1a]
!! + ! so any(@proper-divisors.combinations>>.sum) == $n; # [1b]
sub divisors ($number, :$not-self, :$not-one)
{
my @divisors;
for ($not-one ?? 2 !! 1) .. $number/2 -> $candidate
{
@divisors.push: $candidate if $number %% $candidate;
}
@divisors.push: $number unless $not-self;
return @divisors;
}

[1] Note the use of a ternernary if. It is shorter, but not necessarily readable.

See
docs.raku.org/language/operators#index-entry-operator_ternary for more
information about the *ternary operator* `??`

/ `!!`

.

Running it gives the same result as before:

$ ./weird-number 12
0
$ ./weird-number 70
1

We can set it up as a sequence:

File: weird-number-seq#! /usr/bin/env raku
unit sub MAIN (Int $limit where $limit > 0 = 10, :v(:$verbose));
my $wns := (1..Inf).grep( *.&is-weird );
say $wns.head($limit).join(", ");
sub is-weird (Int $number)
{
my @proper-divisors = divisors($number, :not-self);
return @proper-divisors.sum <= $number
?? False
!! ! so any(@proper-divisors.combinations>>.sum) == $number;
}
sub divisors ($number, :$not-self, :$not-one)
{
my @divisors;
for ($not-one ?? 2 !! 1) .. $number/2 -> $candidate
{
@divisors.push: $candidate if $number %% $candidate;
}
@divisors.push: $number unless $not-self;
say ": $number has divisors: { @divisors.join(", ") }" if $verbose;
return @divisors;
}

Running it:

$ ./weird-number-seq 1
70

This is quick. About 1/3 second on my pc.

But higher number of values result in a slow program. That is caused by the number of combinations, which increases exponentially with the number of divisors. Verbose mode will show you the problem:

$ ./weird-number-seq -v 2
: 1 has divisors:
: 2 has divisors: 1
: 3 has divisors: 1
: 4 has divisors: 1, 2
: 5 has divisors: 1
: 6 has divisors: 1, 2, 3
: 7 has divisors: 1
...
: 715 has divisors: 1, 5, 11, 13, 55, 65, 143
: 716 has divisors: 1, 2, 4, 179, 358
: 717 has divisors: 1, 3, 239
: 718 has divisors: 1, 2, 359
: 719 has divisors: 1
: 720 has divisors: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30,\
36, 40, 45, 48, 60, 72, 80, 90, 120, 144, 180, 240, 360

The last one (the divisors of 720) will take forever (at least it will seem so) when passed
to `combinations`

.

So this is not a very good candidate for a sequence.

And that's it.