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

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 subdivmod{ 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;

# 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);

$ 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 real162m20.686suser161m54.913ssys 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*_{0}, ... , *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* = 8*m*+5, we have

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

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

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

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