CY's Take on The Weekly Challenge #149

CY's Take on The Weekly Challenge #149 Task 2

If you want to challenge yourself on programming, especially on Perl and/or Raku, go to https://theweeklychallenge.org, code the latest challenges, submit codes on-time (by GitHub or email).

Do tell me, if I am wrong or you strongly oppose my statements!

It's time for challenges in Week #149 !

Task 2: Largest Square

image info

Firstly I wrote a prototype of code; I quite like the idea of divmod in Ruby, and I was surprised to find that bdiv in Math::BigInt has similar features IN LIST CONTEXT!

# ch-2-prototype.pl

sub divmod {
    my $dividend = $_[0];
    my $divisor = $_[1];
    my $q = int($dividend / $divisor);
    my $r = $dividend % $divisor;
    return [ $q , $r ];
}

my $N = $ARGV[0] || 3;

my $upper_sqrt;
$upper_sqrt = $N**($N/2) if $N % 2 == 0;
$upper_sqrt = $N**(($N+1)/2) if $N % 2 == 1;


my $bool = undef;
do {
    $upper_sqrt--;
    my $sq = $upper_sqrt**2;
    my @digit = (0) x $N;
    my $c;
    do {
        $c = divmod($sq, $N);
        $sq = $c->[0];
        $digit[$c->[1]]++;
        $bool = $digit[$c->[1]] < 2;
    } while ($bool && ($sq > 0));
} while (!$bool);

say $upper_sqrt**2;

Then it came the first version of "benchmarked" code:

# ch-2.pl

my $bool = undef ;

do {
    $upper_sqrt->bdec();
    my $sq = Math::BigInt->new($upper_sqrt)->bpow(2);
    my %digit;
    do {
        $bool = ++$digit{($sq->bdiv($N))[1]} < 2;
    } while ($bool && $sq->is_pos());
} while (!$bool);

my $sq = Math::BigInt->new($upper_sqrt)->bpow(2);
say "in decimal base: ", $sq;

say "in base-$N: ", $sq->to_base($N);

I found that it is quite slow on $N = 13. So I tried some methods to improve the code.

# ch-2-new.pl

do {
    $upper_sqrt->bdec();
    my $sq = Math::BigInt->new($upper_sqrt)->bpow(2);    ###
    my $sq_baseN = $sq->to_base($N);
    my @arr = split "", $sq_baseN;
    my $uniq_num = uniq @arr;
    $bool = 1 if scalar @arr == $uniq_num;
} while (!$bool);

The below runs a bit faster, and it has been my final attempt:

# ch-2-newest.pl

do {
    $upper_sqrt->bdec();
    $sq->bsub($upper_sqrt)->bsub($upper_sqrt)->bdec(); ###
    my $sq_baseN = $sq->to_base($N);
    my @arr = split "", $sq_baseN;
    my $uniq_num = uniq @arr;
    $bool = 1 if scalar @arr == $uniq_num;
} while (!$bool);

Here are the test data:

$ time perl ch-2.pl 12
in decimal base: 8706730814089
in base-12: B8750A649321

real	0m7.422s
user	0m7.402s
sys	0m0.016s

$ time perl ch-2-prototype.pl 12
8706730814089

real	0m0.167s
user	0m0.163s
sys	0m0.004s

$ time perl ch-2-new.pl 12
in decimal base: 8706730814089
in base-N: B8750A649321

real	0m7.968s
user	0m7.948s
sys	0m0.016s

$ time perl ch-2-newest.pl 12
in decimal base: 8706730814089
in base-N: B8750A649321

real	0m6.615s
user	0m6.608s
sys	0m0.004s



$ time perl ch-2-new.pl 14
in decimal base: 11027486960232964
in base-N: DC71B30685A924

real	1m30.475s
user	1m30.353s
sys	0m0.004s


$ time perl ch-2-newest.pl 14
in decimal base: 11027486960232964
in base-N: DC71B30685A924

real	1m15.650s
user	1m15.525s
sys	0m0.012s



$ time perl ch-2-newest.pl 13
in decimal base: 23132511879129
in base-N: CBA504216873

real	162m20.686s
user	161m54.913s
sys	0m2.674s

My patience was tested again.

Look for explanations or quicker ways to obtain the case for $N=13.

Stay alert and healthy! □

Curse of 13

Part added on 30th January

The On-Line Encyclopedia of Integer Sequences entry A287298 gives an explanation that why 13 is tricky.

a(n) does not always have n digits in base n.
If n is 5 mod 8 then a number which contains all the digits
in base n is congruent to (n-1)n/2 mod (n-1). It will be
then divisible by a single power of 2 and not a square.

by John L. Drost, May 22 2017

It is quite concise. Allow me write a lengthened explanation here.

Let A be a positive integer having n different digits in base-n.

We can write:

A = [sum_from k = 0 to n-1] c_k × n^k, where {c₀, ... , c_n-1} is a permutation of {0, ..., n-1}.

And this implies:

A ≡ [sum_from k = 0 to n-1] c_k × 1^k (mod n-1) .

A ≡ [sum_from k = 0 to n-1] c_k ≡ (n-1)(n)/2 (mod n-1) .

Since for every n ≡ 5 (mod 8), n is odd; let n = 8m+5, we have

A ≡ (8m+5)(4m+2) (mod 8m+4) .

8m+4 is obviously a multiple of 4. Hence,

A ≡ (8m+5)(4m+2) ≡ 10 ≡ 2 (mod 4) .

Every odd square is congruent to 1 modulo 4, and every even square is congruent to 0 modulo 4. Therefore, we come up to a conclusion that a_n cannot have n digits in base-n when n is congruent to 5 modulo 8. □

The image is self-made by the package Luxor.jl in Julia.

using Luxor

@png begin
    circle(Point(0,0), 200, :stroke)
    circle(Point(0,0), 2, :fill)
    fontsize(30)
    line(Point(0,0), Point(150*sin(13*π/6),-150*cos(13*π/6)), :stroke)
    for i = 2:13
        text(string(i), 
             Point(170*sin(i*π/6),170*cos(i*π/6)), 
             halign = :center
        )
    end
end

Except from images and codes from other personnels, the content of this blogpost is released under a copyleft spirit. One may share (full or partial) content of this blogpost on other platform if you share it under the free and open content spirit.

link for CY's full codes: ch-2.pl

Contact on twitter: @e7_87.

Discuss via GitHub issues: here.

Email: fungcheokyin at gmail.com

Created Date: 26th January, 2022.

Created Date of the part "Curse of 13": 30th January, 2022.

The Weekly Challenge ‐ Perl and Raku