Weekly Challenge #085 Task #2 :: (Raku)
Published: 2020-11-02 10:36:39

## [**TASK #2 › Power of Two Integers**](https://perlweeklychallenge.org/blog/perl-weekly-challenge-085/#TASK2)
Submitted by: Mohammad S Anwar

You are given a positive integer $N.

Write a script to find if it can be expressed as a ^ b where a > 0 and b > 1. Print 1 if you succeed otherwise 0.
```
Example 1:

Input: 8
Output: 1 as 8 = 2 ^ 3

Example 2:

Input: 15


Output: 0

Example 3:

Input: 125
Output: 1 as 125 = 5 ^ 3
```

### **Staring Point**
Where should I start? one thing I know is that when "1" is given, answer is 1 as 1 always remain 1 no matter how many times we multiply. and answer is always "0" when a prime number given. so wrote down like below.
```perl
multi sub MAIN (1) { say "1 as 1²" }

multi sub MAIN ( Int \N where * > 0 ) {
    if N.is-prime {
        say "0 as {N} is a prime number.";
    }
    else {
        die "not implemented";
    }
}
```
And we needs factor k¹, k², k³ to compare given number but what *k* value can be? Starting point would be square root of N!!

```perl
> 144.sqrt
12
> 145.sqrt
12.041594578792296
```
So if we started from 12 to 1 and comparing 12², 12³ ..., we could find the given N can be expressed with two integers. Code below will find the largest *maybe* factor of N as mentioned above.
```perl
sub largest-factor ( Int \n --> Int ) { n.sqrt.Int }
```

### **One More Thing about Lazy**
There is a function called "repeat" in Haskell
```haskell
λ= take 4 (repeat 3)
[3,3,3,3]
```
Code below will do similar thing in Raku
```perl
> [3,3 ... Inf].head(4)
(3 3 3 3)
```
because
```perl
> [3,3 ... Inf].is-lazy
True
```
It is handy when actually have no idea how long the list will be.
So If we are interested in making a¹, a², a³, we could code like
```perl
> gather { loop ( my $i = 1; $i <=3 ; $i++ ) { take 2**$i } }
(2 4 8)
```
But also 
```perl
> [2,2...Inf].produce( { $^a * $^b } ).head(3)
# or
> [2,2...Inf].produce( &[*] ).head(3)
# or
> [2,2...Inf].produce( * * * ).head(3)
# or 
> ([\*] [2,2...Inf]).head(3)
(2 4 8)
```
The difference between two ways is lying on *imperative programming vs functional programming*. In former way we can break the loop sometimes or somewhere. but latter one shows that control is handled by outer function(head()). I'm not saying that which one is better. but functional programming generally show the progress better, IMHO. 
It was good chance for me to see how the Raku is lazily evaluate the code. So I wrote a solution like below.

### **A Solution Using*** [*produce()*](https://docs.raku.org/routine/produce)
```perl
multi sub MAIN ( Int \N where * > 0 ) {
    if N.is-prime {
        say "0 as {N} is a prime number.";
    }
    else {
        my $lf = largest-factor(N);
        ( $lf ... 2 ).
        lazy.
        map(
            -> $a {
                ([\×] ($a,$a ... ∞)). # produce a¹, a², a³
                lazy.                   # in lazy way
                skip(1).                # but we don't need first one (a¹)
                kv.
                map(
                    -> \β, \κ {
                        if    N == κ { ($a => β + 2) }  # as `b' value
                        elsif N <= κ { last  }
                        else          { Empty }
                    } ).Slip
            } ).first
        andthen say "1 as {.key}{pow-utf8(.value)}"
        orelse  say "0"
    }

}
```
exp-utf8 function looks like below
```perl
sub pow-utf8 ( Int $n ) {
    state @pow = <⁰ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹>;
    @pow[ $n.comb ].join;
}
```

### **Log**
BTW, we have log() function. so we don't actually need to produce a^b values.
```perl
> log( 8, 2 )
3 # a: 2, b: 3
> log( 8, 2 ).Rat.denominator # there is no floating point value
1
```
Of course everything is first class in Raku, so we can write like below as well!

```perl
> 144.log(12)
2
```

### **UPDATE** *(5th Nov)*
Rat has smaller precision than I expect, so N is bigger, solution is less accurate. so we need to increase the precision like below.
```perl
> log( 33429368569, 182837 ).Rat( 1e-32 );
2
> log ( log( 334293685691, 578181 ).Rat
2 # (wrong) because ...
> 578181², 334293685691.sqrt
(334293268761 578181.3605530708)
```

### **Final Code.appended()**
```perl
multi sub MAIN ( Int \N where * > 0, Bool:D :$log ) {
    $*ERR.say( "alternative solution using log() ..." );
    if N.is-prime {
        say "0 as {N} is a prime number.";
    }
    else {
        my $lf = largest-factor(N);
        ( $lf ... 2 ).
        lazy.map(
            { my $pow = log( N, $_ ).Rat( 1e-32 );
              ($_ => $pow.Int) if $pow.denominator == 1;
            }
        ).first
        andthen say "1 as {.key}{pow-utf8(.value)}"
        orelse  say "0"
    }
}
```

Happy Coding !!!
If you have a time, please visit at  [🐪PWC🦋](https://perlweeklychallenge.org).