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

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



The full version is

# Perl weekly challenge 133
# Task 1:  integer square root
# See

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;


./ 10 27 85 101



Another example:

./ -1 0 `seq 10`


√-1=Come on, let's get real

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
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);
die "Usage: './ desired base' with desired>=0 and base >=2"
     unless $base>=2 and $desired>0;
my @smith=();
my $N=4; # First non-prime
    push @smith, $N if is_smith($N, $base);
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;
	push @digits, $N%$base;

Example: The first ten Smith numbers in base ten.



First 10 Smith numbers in base 10: 4 22 27 58 85 94 121 166 202 265

Other examples:

./ 7 11
./ 5 3


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