This is my response to the Perl Weekly Challenge #156.
10 Pernicious Numbers.
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...
$n > 0.
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.
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.
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.