TASK #2 › Power of Two Integers
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.
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!!
> 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.
sub largest-factor ( Int \n --> Int ) { n.sqrt.Int }
One More Thing about Lazy
There is a function called "repeat" in Haskell
λ= take 4 (repeat 3)
[3,3,3,3]
Code below will do similar thing in Raku
> [3,3 ... Inf].head(4)
(3 3 3 3)
because
> [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
> gather { loop ( my $i = 1; $i <=3 ; $i++ ) { take 2**$i } }
(2 4 8)
But also
> [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()
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
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.
> 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!
> 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.
> log( 33429368569, 182837 ).Rat( 1e-32 );
2
> log ( log( 334293685691, 578181 ).Rat
2 # (wrong) because ...
> 578181², 334293685691.sqrt
(334293268761 578181.3605530708)
Final Code.appended()
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🦋.
Top comments (0)