# 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.

[[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
#

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
``````

``````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
#
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
``````
Written on October 6, 2021