# ETOOBUSY ðŸš€ minimal blogging for the impatient

# PWC175 - Perfect Totient Numbers

**TL;DR**

On with TASK #2 from The Weekly Challenge #175. Enjoy!

# The challenge

Write a script to generate first

`20 Perfect Totient Numbers`

. Please checkout wikipedia page for more informations.

Output`3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571`

# The questions

I guess the reference to the Wikipedia page says it all. Althoughâ€¦ I canâ€™t help noting that both $0$ and $1$ might somehow qualify. Anyway.

# The solution

This is finally the time that I complicate bread. The gist of this
challenge is to code some `is_perfect_totient_number`

, which in turn
begs for implementing some `totient_supersum`

that calculates the
iterative sum of totient values.

```
use ntheory 'euler_phi';
sub is_perfect_totient_number ($n) { $n == totient_supersum($n) }
sub totient_supersum ($n) {
state $cache = {0 => 0, 1 => 1, 2 => 1};
# first "recurse" up to the point where we have something
# in cache
my @stack = $n;
push @stack, $n = euler_phi($n) while ! exists $cache->{$n};
# then go back down to calculate all new needed values
$n = pop @stack;
my $pred = $cache->{$n};
while (@stack) {
($n, my $phi) = (pop(@stack), $n);
$pred = $cache->{$n} = $phi + $pred;
}
# whatever is left is what we were after in the first place
return $pred;
}
```

And now we have our usual brute forcing the way up to the needed number of items.

Well, this is it. This must end *now*.

So, instead of this:

```
# WARNING: UNTESTED CODE
my $n = shift // 20;
my $candidate = 2;
while ($n > 0) {
if (is_perfect_totient_number($candidate)) {
say $candidate;
--$n;
}
++$candidate;
}
```

I decided to go for this:

```
my $n_items = shift // 20;
say
for BruteCheck::brutechecker(
iterator => BruteCheck::int_iterator('2..'),
ender => BruteCheck::max_size($n_items),
checker => sub ($n) { return totient_supersum($n) == $n },
);
# ...
package BruteCheck;
sub max_size ($n) { sub ($aref) { $aref->@* >= $n } }
sub int_iterator ($spec) {
my ($start, $stop, $step) = $spec =~ m{
\A
([1-9]\d*|0|)
\.\.
([1-9]\d*|0|)
(?: / (-?[1-9]\d*))?
\z
}mxs;
$start ||= 0;
$step ||= 1;
my $i = $start;
return sub {
return
if length($stop)
&& (($step > 0 && $i > $stop) || ($step < 0 && $i < $stop));
my $retval = $i;
$i += $step;
return $retval;
};
} ## end sub int_iterator ($spec)
sub brutechecker (%args) {
my ($checker, $iterator, $ender) = @args{qw< checker iterator ender >};
$iterator //= int_iterator('..');
$ender //= sub { 0 };
my @retval;
while (!$ender->(\@retval) && defined(my $candidate = $iterator->())) {
push @retval, $candidate if $checker->($candidate);
}
return @retval;
} ## end sub brutechecker (%args)
```

So we get:

- a wonderfully overkill iterator generator which parses strings like
`..`

(from 0 to infinity),`2..`

(from 2 up to infinity),`2..10`

(from 2 to 10),`2..10/2`

(two by two), â€¦ - a definitely overkill wrapper for checking when an array has a specific size, or more;
- a brute force generalization that will surely fail me the next time I need it.

Anyway, the Raku alternative made me come to compromises. I gave up on the parsing of a string and went for an explicit expression for the start/stop/step values.

```
#!/usr/bin/env raku
use v6;
class IntIterator { ... }
class BruteCheck { ... }
sub MAIN (Int:D $n where * > 0 = 20) {
$*OUT.out-buffer = False;
.put for BruteCheck.new(
iterator => IntIterator.new(start => 2),
ender => -> @x { @x.elems == $n },
checker => sub ($n) { $n == totient-supersum($n) },
).run();
}
sub totient-supersum ($n is copy) {
state %cache = <0 0 1 1 2 1>;
my @stack = $n,;
@stack.push($n = euler-phi($n)) while %cache{$n}:!exists;
$n = @stack.pop;
my $pred = %cache{$n};
while @stack {
($n, my $phi) = @stack.pop, $n;
$pred = %cache{$n} = $phi + $pred;
}
return $pred;
}
sub euler-phi ($n) {
state %cache = <0 0 1 1 2 1>;
return %cache{$n} //= (1 ..^ $n).grep({($_ gcd $n) == 1}).elems;
}
class IntIterator {
has $.start is readonly is built = 0;
has $.stop is readonly is built = Inf;
has $.step is readonly is built = 1;
has $!current;
submethod TWEAK() {
$!current = $!start;
$!stop = -Inf if $!stop == Inf && $!step < 0;
}
method pull-one {
return Nil
if ($!step > 0 && $!current > $!stop)
|| ($!step < 0 && $!current < $!stop);
my $retval = $!current;
$!current += $!step;
return $retval;
}
};
class BruteCheck {
has &.checker;
has &.ender is built = sub (@r) { False };
has $.iterator is built = IntIterator.new();
method run {
my @rval;
while (! &!ender(@rval) && defined(my $c = $!iterator.pull-one())) {
@rval.push: $c if &!checker($c);
}
return @rval;
}
}
```

And with all these unneeded lines of codeâ€¦ itâ€™s time to say goodbye until next time!

*Comments? Octodon, Twitter, GitHub, Reddit, or drop me a line!*