Perl Weekly Challenge 133.
My solutions (task 1, and task 2 ) to the The Weekly Challenge - 133.
TASK 1: Integer Square Root
Submitted by: Mohammad S Anwar
You are given a positive integer $N.
Write a script to calculate the integer square root of the
given number.
Please avoid using built-in function. Find out more about it
[[https://en.wikipedia.org/wiki/Integer_square_root][here.]]
Examples
Input: $N = 10
Output: 3
Input: $N = 27
Output: 5
Input: $N = 85
Output: 9
Input: $N = 101
Output: 10
Making a first order Taylor expansion of a function f(x) around a point x0, we can approximate f(x)≅f(x0)+(x-x0)f’(x0), where f’ is the derivative of f. If we want x to be a zero of the function, f(x)=0, we obtain an approximation to x as x≅x0-f(x0)/f’(x0). To get a better approximation we can iterate the procedure above, provided the iteration converges. The square root x=√y is the zero of the function f(x)=y-x2, with derivative f’(x)=-2x. Thus, the square root may be found through the iteration x→x+(y-x²)/2x=(x+y/x)/2, which yields a decreasing suquence if the starting guess lies above the square root and converges rapidly. It turns out that this procedure also works for integer arithmetic yielding the integer square root after a finite number of iterations when either the sequence repeats itself or increases. Thus the task may be solved with the following one-liner:
perl -Minteger -E '
foreach my $N(@ARGV){$y=($x=$N)/2||1; ($x,$y)=($y,($N/$y+$y)/2) while($y<$x);
say "√$N=$x"}' 10 27 85 101
Results:
√10=3
√27=5
√85=9
√101=10
The full version is
# Perl weekly challenge 133
# Task 1: integer square root
#
# See https://wlmb.github.io/2021/10/06/PWC133/#task-1-integer-square-root
use v5.12;
use warnings;
use integer;
say "√$_=", int_sqrt($_) foreach(@ARGV);
sub int_sqrt{
my $x0=my $N=shift;
return "Come on, let's get real" if $N<0;
return $N if $x0==0;
my $x1=(($N/$x0+$x0)/2); # initial guess
($x0,$x1)=($x1, (($N/$x1+$x1)/2)) while($x1<$x0);
return $x0;
}
Example:
./ch-1.pl 10 27 85 101
Results:
√10=3
√27=5
√85=9
√101=10
Another example:
./ch-1.pl -1 0 `seq 10`
Results:
√-1=Come on, let's get real
√0=0
√1=1
√2=1
√3=1
√4=2
√5=2
√6=2
√7=2
√8=2
√9=3
√10=3
Task 2: Smith Numbers
Submitted by: Mohammad S Anwar
Write a script to generate first 10 Smith Numbers in base 10.
According to Wikipedia:
In number theory, a Smith number is a composite number for
which, in a given number base, the sum of its digits is equal
to the sum of the digits in its prime factorization in the
given number base.
I will assume the amount of desired Smith numbers base are
given in @ARGV.
As the first ten Smith numbers are quite small, I check
all numbers sequentially testing them for Smith-ness. I use
the Math::Prime::Util package to find all factors, obtain and
sum all the digits of the number and of all its factors in the
given base, where the digits are identified using modulo and
integer division. I output the results in decimal though.
# Perl weekly challenge 133
# Task 2: Smith numbers
#
# See https://wlmb.github.io/2021/10/06/PWC133/#task-2-smith-numbers
use v5.12;
use warnings;
use POSIX qw(floor);
use Math::Prime::Util qw(is_prime factor);
use List::Util qw(sum0);
use integer;
my ($desired, $base)=map {floor $_} (@ARGV);
$desired//=10;
$base//=10;
die "Usage: './ch-2.pl desired base' with desired>=0 and base >=2"
unless $base>=2 and $desired>0;
my @smith=();
my $N=4; # First non-prime
while(@smith<$desired){
push @smith, $N if is_smith($N, $base);
++$N;
}
say join " ", "First $desired Smith numbers in base $base:", @smith;
sub is_smith {
my ($N, $base)=@_;
return 0 if is_prime($N);
my $sum_digits=sum0 digits($N, $base);
my $sum_factors=sum0 map {digits($_, $base)} factor($N);
return $sum_digits==$sum_factors;
}
sub digits {
my ($N,$base)=@_;
my @digits;
while($N){
push @digits, $N%$base;
$N/=$base;
}
@digits;
}
Example: The first ten Smith numbers in base ten.
./ch-2.pl
Results:
First 10 Smith numbers in base 10: 4 22 27 58 85 94 121 166 202 265
Other examples:
./ch-2.pl 7 11
./ch-2.pl 5 3
Results:
First 7 Smith numbers in base 11: 4 18 30 42 63 66 72
First 5 Smith numbers in base 3: 78 186 222 231 399