First perfect square in base n with n unique digits: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎{{header|Perl 6}}: Updated with better analytics)
(→‎{{header|Perl 6}}: Add some timing/monitoring code, tweaks & twiddles, add bases 21 & 22)
Line 563: Line 563:
As long as you have the patience, this will work for bases 2 through 36.
As long as you have the patience, this will work for bases 2 through 36.


2 through 19 finish in about 10 seconds (on my system), 20 takes several minutes.
Bases 2 through 19 finish quickly, (about 10 seconds on my system), 20 takes a while, 21 is pretty fast, 22 is glacial.


Use analytical start value filtering based on observations by [[User:Hout|Hout]]++
Use analytical start value filtering based on observations by [[User:Hout|Hout]]++
Line 577: Line 577:


]
]

unit sub MAIN ($timer = False);


sub first-square (Int $n) {
sub first-square (Int $n) {
Line 590: Line 592:
}
}


my $start = @start.join.parse-base($n).sqrt.floor;
my $start = @start.join.parse-base($n).sqrt.ceiling;
my @digits = reverse @start;
my @digits = reverse (^$n)».base($n);
my $sq;
my $sq;
my $now = now;
my $time = 0;
for $start .. * {
for $start .. * {
$sq = $_ * $_;
$sq = $_ * $_;
Line 598: Line 602:
my $f;
my $f;
$f = 1 and last unless $s.contains: $_ for @digits;
$f = 1 and last unless $s.contains: $_ for @digits;
if $timer && $n > 19 && $_ %% 1_000_000 {
$time += now - $now;
say "N $n: {$_}² = $sq <$s> : {(now - $now).round(.001)}s" ~
" : {$time.round(.001)} elapsed";
$now = now;
}
next if $f;
next if $f;
last
last
}
}
sprintf "Base %2d: %10s² == %s", $n, $sq.sqrt.base($n), $sq.base($n);
sprintf "Base %2d: %12s² == %s", $n, $sq.sqrt.base($n), $sq.base($n);
}
}


sub digital-root ($root is copy, :$base = 10) {
sub digital-root ($root is copy, :$base = 10) {
$root = [+]($root.comb.map({:36($_)})).base($base) while $root.chars > 1;
$root = $root.comb.map({:36($_)}).sum.base($base) while $root.chars > 1;
$root.parse-base($base);
$root.parse-base($base);
}
}
Line 613: Line 623:
2 .. 12, # required
2 .. 12, # required
13 .. 16, # optional
13 .. 16, # optional
17 .. 20, # stretch goal
17 .. 19, # stretch
20, # slow
21, # pretty fast
22, # very slow
;</lang>
;</lang>
{{out}}
{{out}}
<pre>First perfect square with N unique digits in base N:
<pre>First perfect square with N unique digits in base N:
Base 2: 10² == 100
Base 2: 10² == 100
Base 3: 22² == 2101
Base 3: 22² == 2101
Base 4: 33² == 3201
Base 4: 33² == 3201
Base 5: 243² == 132304
Base 5: 243² == 132304
Base 6: 523² == 452013
Base 6: 523² == 452013
Base 7: 1431² == 2450361
Base 7: 1431² == 2450361
Base 8: 3344² == 13675420
Base 8: 3344² == 13675420
Base 9: 11642² == 136802574
Base 9: 11642² == 136802574
Base 10: 32043² == 1026753849
Base 10: 32043² == 1026753849
Base 11: 111453² == 1240A536789
Base 11: 111453² == 1240A536789
Base 12: 3966B9² == 124A7B538609
Base 12: 3966B9² == 124A7B538609
Base 13: 3828943² == 10254773CA86B9
Base 13: 3828943² == 10254773CA86B9
Base 14: 3A9DB7C² == 10269B8C57D3A4
Base 14: 3A9DB7C² == 10269B8C57D3A4
Base 15: 1012B857² == 102597BACE836D4
Base 15: 1012B857² == 102597BACE836D4
Base 16: 404A9D9B² == 1025648CFEA37BD9
Base 16: 404A9D9B² == 1025648CFEA37BD9
Base 17: 423F82GA9² == 101246A89CGFB357ED
Base 17: 423F82GA9² == 101246A89CGFB357ED
Base 18: 44B482CAD² == 10236B5F8EG4AD9CH7
Base 18: 44B482CAD² == 10236B5F8EG4AD9CH7
Base 19: 1011B55E9A² == 10234DHBG7CI8F6A9E5
Base 19: 1011B55E9A² == 10234DHBG7CI8F6A9E5
Base 20: 49DGIH5D3G² == 1024E7CDI3HB695FJA8G</pre>
Base 20: 49DGIH5D3G² == 1024E7CDI3HB695FJA8G
Base 21: 4C9HE8175DA² == 1023467JKAIEHB5DF9A8CG
Base 22: 4F94788GJ0F² == 102369FBGDEJ48CHI7LKA5</pre>


=={{header|Python}}==
=={{header|Python}}==

Revision as of 18:52, 24 May 2019

First perfect square in base n with n unique digits is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Find the first perfect square in a given base N that has at least N digits and exactly N significant unique digits when expressed in base N.

E.G. In base 10, the first perfect square with at least 10 unique digits is 1026753849 (32043²).

You may use analytical methods to reduce the search space, but the code must do a search. Do not use magic numbers or just feed the code the answer to verify it is correct.

Task
  • Find and display here, on this page, the first perfect square in base N, with N significant unique digits when expressed in base N, for each of base 2 through 12. Display each number in the base N for which it was calculated.
  • (optional) Do the same for bases 13 through 16.
  • (stretch goal) Continue on for bases 17 - ?? (Big Integer math)


See also

F#

<lang fsharp> // Nigel Galloway: May 21st., 2019 let fN g=let g=int64(sqrt(float(pown g (int(g-1L)))))+1L in (Seq.unfold(fun(n,g)->Some(n,(n+g,g+2L))))(g*g,g*2L+1L) let fG n g=Array.unfold(fun n->if n=0L then None else let n,g=System.Math.DivRem(n,g) in Some(g,n)) n let fL g=let n=set[0L..g-1L] in Seq.find(fun x->set(fG x g)=n) (fN g) let toS n g=let a=Array.concat [[|'0'..'9'|];[|'a'..'f'|]] in System.String(Array.rev(fG n g)|>Array.map(fun n->a.[(int n)])) [2L..16L]|>List.iter(fun n->let g=fL n in printfn "Base %d: %s² -> %s" n (toS (int64(sqrt(float g))) n) (toS g n)) </lang>

Output:
Base 2: 10² -> 100
Base 3: 22² -> 2101
Base 4: 33² -> 3201
Base 5: 243² -> 132304
Base 6: 523² -> 452013
Base 7: 1431² -> 2450361
Base 8: 3344² -> 13675420
Base 9: 11642² -> 136802574
Base 10: 32043² -> 1026753849
Base 11: 111453² -> 1240a536789
Base 12: 3966b9² -> 124a7b538609
Base 13: 3828943² -> 10254773ca86b9
Base 14: 3a9db7c² -> 10269b8c57d3a4
Base 15: 1012b857² -> 102597bace836d4
Base 16: 404a9d9b² -> 1025648cfea37bd9

Go

Basic plus optional

<lang go>package main

import ( 

   "fmt"
   "math"
   "strconv"

)

const maxBase = 16 const minSq16 = "1023456789abcdef"

func containsAll(sq string, base int) bool { 

   var found [maxBase]bool
   for _, r := range sq {
       if r < 58 {
           found[r-48] = true
       } else {
           found[r-87] = true
       }
   }

   for i := 0; i < base; i++ {
       if !found[i] {
          return false
       }
   }
   return true

}

func main() { 

   for n, base := uint64(2), 2; ; n++ {
       sq := strconv.FormatUint(n*n, base)
       if !containsAll(sq, base) {
           continue
       }
       ns := strconv.FormatUint(n, base)
       fmt.Printf("Base %2d:%10s² = %s\n", base, ns, sq)
       if base == maxBase {
           return
       }
       base++
       minNN, _ := strconv.ParseUint(minSq16[:base], base, 64)
       if minNN > (n+1)*(n+1) {
           n = uint64(math.Sqrt(float64(minNN))) - 1
       }
   }

}</lang>

Output:
Base  2:        10² = 100
Base  3:        22² = 2101
Base  4:        33² = 3201
Base  5:       243² = 132304
Base  6:       523² = 452013
Base  7:      1431² = 2450361
Base  8:      3344² = 13675420
Base  9:     11642² = 136802574
Base 10:     32043² = 1026753849
Base 11:    111453² = 1240a536789
Base 12:    3966b9² = 124a7b538609
Base 13:   3828943² = 10254773ca86b9
Base 14:   3a9db7c² = 10269b8c57d3a4
Base 15:  1012b857² = 102597bace836d4
Base 16:  404a9d9b² = 1025648cfea37bd9

Stretch

The following version uses big.Int rather than uint64 so it can deal with the stretch goal. It takes about twice as long as before to reach base 16.

As in the case of the Perl 6 entry, I found base 17 to be glacially slow and so have skipped that altogether. Expect a run time of a few minutes to reach base 20. <lang go>package main

import ( 

   "fmt"
   "math/big"
   "strconv"

)

const maxBase = 20 const minSq20 = "1023456789abcdefghij"

func containsAll(sq string, base int) bool { 

   var found [maxBase]bool
   for _, r := range sq {
       if r < 58 {
           found[r-48] = true
       } else {
           found[r-87] = true
       }
   }
   for i := 0; i < base; i++ {
       if !found[i] {
          return false
       }
   }
   return true

}

func main() { 

   var nb, nn big.Int
   for n, base := uint64(2), 2; ; n++ {
       nb.SetUint64(n)
       sq := nb.Mul(&nb, &nb).Text(base)
       if !containsAll(sq, base) {
           continue
       }
       ns := strconv.FormatUint(n, base)
       fmt.Printf("Base %2d:%12s² = %s\n", base, ns, sq)
       if base == maxBase {
           break
       }
       base++
       if base == 17 {
           base++
       }
       nn.SetString(minSq20[:base], base)
       nb.SetUint64(n + 1)
       nb.Mul(&nb, &nb)
       if nn.Cmp(&nb) == 1 {
           nb.Sqrt(&nn)
           n = nb.Uint64() - 1
       }
   }

}</lang>

Output:
Base  2:          10² = 100
Base  3:          22² = 2101
Base  4:          33² = 3201
Base  5:         243² = 132304
Base  6:         523² = 452013
Base  7:        1431² = 2450361
Base  8:        3344² = 13675420
Base  9:       11642² = 136802574
Base 10:       32043² = 1026753849
Base 11:      111453² = 1240a536789
Base 12:      3966b9² = 124a7b538609
Base 13:     3828943² = 10254773ca86b9
Base 14:     3a9db7c² = 10269b8c57d3a4
Base 15:    1012b857² = 102597bace836d4
Base 16:    404a9d9b² = 1025648cfea37bd9
Base 18:   44b482cad² = 10236b5f8eg4ad9ch7
Base 19:  1011b55e9a² = 10234dhbg7ci8f6a9e5
Base 20:  49dgih5d3g² = 1024e7cdi3hb695fja8g

JavaScript

Translation of: Python

<lang javascript>(() => { 

   'use strict';

   // allDigitSquare :: Int -> Int
   const allDigitSquare = base => {
       const bools = replicate(base, false);
       return untilSucc(
           allDigitsUsedAtBase(base, bools),
           ceil(sqrt(parseInt(
               '10' + '0123456789abcdef'.slice(2, base),
               base
           )))
       );
   };

   // allDigitsUsedAtBase :: Int -> [Bool] -> Int -> Bool
   const allDigitsUsedAtBase = (base, bools) => n => {
       // Fusion of representing the square of integer N at a given base
       // with checking whether all digits of that base contribute to N^2.
       // Sets the bool at a digit position to True when used.
       // True if all digit positions have been used.
       const ds = bools.slice(0);
       let x = n * n;
       while (x) {
           ds[x % base] = true;
           x = floor(x / base);
       }
       return ds.every(x => x)
   };

   // showBaseSquare :: Int -> String
   const showBaseSquare = b => {
       const q = allDigitSquare(b);
       return justifyRight(2, ' ', str(b)) + ' -> ' +
           justifyRight(8, ' ', showIntAtBase(b, digit, q, )) +
           ' -> ' + showIntAtBase(b, digit, q * q, );
   };

   // TEST -----------------------------------------------
   const main = () => {
       // 1-12 only - by 15 the squares are truncated by
       // JS integer limits.

       // Returning values through console.log –
       // in separate events to avoid asynchronous disorder.
       print('Smallest perfect squares using all digits in bases 2-12:\n')
       print('Base      Root    Square')

       print(showBaseSquare(2));
       print(showBaseSquare(3));
       print(showBaseSquare(4));
       print(showBaseSquare(5));
       print(showBaseSquare(6));
       print(showBaseSquare(7));
       print(showBaseSquare(8));
       print(showBaseSquare(9));
       print(showBaseSquare(10));
       print(showBaseSquare(11));
       print(showBaseSquare(12));
   };

   // GENERIC FUNCTIONS ----------------------------------
   
   const
       ceil = Math.ceil,
       floor = Math.floor,
       sqrt = Math.sqrt;

   // Tuple (,) :: a -> b -> (a, b)
   const Tuple = (a, b) => ({
       type: 'Tuple',
       '0': a,
       '1': b,
       length: 2
   });

   // digit :: Int -> Char
   const digit = n =>
       // Digit character for given integer.
       '0123456789abcdef' [n];

   // enumFromTo :: (Int, Int) -> [Int]
   const enumFromTo = (m, n) =>
       Array.from({
           length: 1 + n - m
       }, (_, i) => m + i);

   // justifyRight :: Int -> Char -> String -> String
   const justifyRight = (n, cFiller, s) =>
       n > s.length ? (
           s.padStart(n, cFiller)
       ) : s;

   // print :: a -> IO ()
   const print = x => console.log(x)

   // quotRem :: Int -> Int -> (Int, Int)
   const quotRem = (m, n) =>
       Tuple(Math.floor(m / n), m % n);

   // replicate :: Int -> a -> [a]
   const replicate = (n, x) =>
       Array.from({
           length: n
       }, () => x);

   // showIntAtBase :: Int -> (Int -> Char) -> Int -> String -> String
   const showIntAtBase = (base, toChr, n, rs) => {
       const go = ([n, d], r) => {
           const r_ = toChr(d) + r;
           return 0 !== n ? (
               go(Array.from(quotRem(n, base)), r_)
           ) : r_;
       };
       return 1 >= base ? (
           'error: showIntAtBase applied to unsupported base'
       ) : 0 > n ? (
           'error: showIntAtBase applied to negative number'
       ) : go(Array.from(quotRem(n, base)), rs);
   };

   // Abbreviation for quick testing - any 2nd arg interpreted as indent size

   // sj :: a -> String
   function sj() {
       const args = Array.from(arguments);
       return JSON.stringify.apply(
           null,
           1 < args.length && !isNaN(args[0]) ? [
               args[1], null, args[0]
           ] : [args[0], null, 2]
       );
   }

   // str :: a -> String
   const str = x => x.toString();

   // untilSucc :: (Int -> Bool) -> Int -> Int
   const untilSucc = (p, x) => {
       // The first in a chain of successive integers
       // for which p(x) returns true.
       let v = x;
       while (!p(v)) v = 1 + v;
       return v;
   };

   // MAIN ---
   return main();

})();</lang>

Output:
Smallest perfect squares using all digits in bases 2-12:

Base      Root    Square
 2 ->       10 -> 100
 3 ->       22 -> 2101
 4 ->       33 -> 3201
 5 ->      243 -> 132304
 6 ->      523 -> 452013
 7 ->     1431 -> 2450361
 8 ->     3344 -> 13675420
 9 ->    11642 -> 136802574
10 ->    32043 -> 1026753849
11 ->   111453 -> 1240a536789
12 ->   3966b9 -> 124a7b538609

Julia

Runs in about 4 seconds with using occursin(). <lang julia>const num = "0123456789abcdef" hasallin(n, nums, b) = (s = string(n, base=b); all(x -> occursin(x, s), nums))

function squaresearch(base) 

   basenumerals = [c for c in num[1:base]]
   highest = parse(Int, "10" * num[3:base], base=base)
   for n in Int(trunc(sqrt(highest))):highest
       if hasallin(n * n, basenumerals, base)
           return n
       end
   end

end

println("Base Root N") for b in 2:16 

   n = squaresearch(b)
   println(lpad(b, 3), lpad(string(n, base=b), 10), "  ", string(n * n, base=b))

end

</lang>

Output:
Base     Root   N
  2        10  100
  3        22  2101
  4        33  3201
  5       243  132304
  6       523  452013
  7      1431  2450361
  8      3344  13675420
  9     11642  136802574
 10     32043  1026753849
 11    111453  1240a536789
 12    3966b9  124a7b538609
 13   3828943  10254773ca86b9
 14   3a9db7c  10269b8c57d3a4
 15  1012b857  102597bace836d4
 16  404a9d9b  1025648cfea37bd9

Pascal

Starting value equals squareroot of smallest value containing all digits to base. Than brute force. <lang pascal>program project1; //Find the smallest number n to base b, so that n*n includes all //digits of base b {$IFDEF FPC}{$MODE DELPHI}{$ENDIF} uses 

 sysutils;

function NToBase(n:Uint64;base:nativeUint):string; const 

charSet : array[0..36] of char ='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';

var 

quot : Uint64;
rest : NativeInt;

begin 

 result := ;
 repeat
   quot := n div base;
   rest := n-quot*base;
   result := charSet[rest]+result;
   n := quot;
 until n = 0;

end;

procedure OutResult(n:Int64;base:NativeUint); Begin 

 writeln(NToBase(n,base):11,NToBase(sqr(n),base):18);

end;

function CheckDigitToBase(n:UInt64;base:NativeUint):boolean; //mark used digits and count afterwards var 

 testSet : array [0..31] of boolean;
 quot : UInt64;
 rest : NativeInt;

begin 

 For rest := base-1 downto 0 do
   testSet[rest] := false;
 //convert to n to base, marking the digits
 repeat
   quot := n div base;
   rest := n-quot*base;
   n := quot;
   testSet[rest]:= true;
 until n = 0;
 //count used digits
 rest := base-1;
 repeat
   if Not(testSet[rest]) then
     break;
   dec(rest);
 until rest<0;
 CheckDigitToBase := rest<0;

end;

var 

 T0: TDateTime;
 n: UInt64;
 base,i :nativeInt;

begin 

 T0 := now;
 writeln('base  start value       n         square(n)');
 For base := 2 to 16 do
 Begin
   //compose the smallest value containing all digits to base
   //'1023456789AB... '    
   n := base;  // aka '10'
   IF base > 2 then 
     For i := 2 to base-1 do
       n := n*base+i;
   n := trunc(sqrt(n));        
   write(base:4,NToBase(n,base):10);        
   //now check square(n) until found 
   repeat
     IF CheckDigitToBase(sqr(n),base) then
     Begin
       OutResult(n,base);
       BREAK;
     end;
     inc(n);
   until false;
 end;
 writeln((now-T0)*86400:10:3,' s');
 {$IFDEF WINDOWS}readln;{$ENDIF}

end.</lang>

Output:
base  start value       n         square(n)
   2         1         10               100
   3        10         22              2101
   4        20         33              3201
   5       101        243            132304
   6       231        523            452013
   7      1011       1431           2450361
   8      2703       3344          13675420
   9     10116      11642         136802574
  10     31991      32043        1026753849
  11    101171     111453       1240A536789
  12    35A923     3966B9      124A7B538609
  13   1011810    3828943    10254773CA86B9
  14   3A9774A    3A9DB7C    10269B8C57D3A4
  15  10119105   1012B857   102597BACE836D4
  16  40466419   404A9D9B  1025648CFEA37BD9
     1.471 s

Perl

Library: ntheory

<lang perl>use strict; use warnings; use feature 'say'; use ntheory qw/fromdigits todigitstring/; use utf8; binmode('STDOUT', 'utf8');

sub first_square { 

   my $n = shift;
   my $sr = substr('1023456789abcdef',0,$n);
   my $r  = int fromdigits($sr, $n) ** .5;
   my @digits = reverse split , $sr;
   TRY: while (1) {
       my $sq = $r * $r;
       my $cnt = 0;
       my $s = todigitstring($sq, $n);
       my $i = scalar @digits;
       for (@digits) {
           $r++ and redo TRY if (-1 == index($s, $_)) || ($i-- + $cnt < $n);
           last if $cnt++ == $n;
       }
       return sprintf "Base %2d: %10s² == %s", $n, todigitstring($r, $n),
              todigitstring($sq, $n);
   }

}

say "First perfect square with N unique digits in base N: "; say first_square($_) for 2..16;</lang>

Output:
First perfect square with N unique digits in base N: 
Base  2:         10² == 100
Base  3:         22² == 2101
Base  4:         33² == 3201
Base  5:        243² == 132304
Base  6:        523² == 452013
Base  7:       1431² == 2450361
Base  8:       3344² == 13675420
Base  9:      11642² == 136802574
Base 10:      32043² == 1026753849
Base 11:     111453² == 1240a536789
Base 12:     3966b9² == 124a7b538609
Base 13:    3828943² == 10254773ca86b9
Base 14:    3a9db7c² == 10269b8c57d3a4
Base 15:   1012b857² == 102597bace836d4
Base 16:   404a9d9b² == 1025648cfea37bd9

Perl 6

Works with: Rakudo version 2019.03

As long as you have the patience, this will work for bases 2 through 36.

Bases 2 through 19 finish quickly, (about 10 seconds on my system), 20 takes a while, 21 is pretty fast, 22 is glacial.

Use analytical start value filtering based on observations by Hout++ and Nigel Galloway++ on the discussion page.

<lang perl6>#`[

Only search square numbers that have at least N digits; smaller could not possibly match.

Only bother to use analytics for large N. Finesse takes longer than brute force for small N.

]

unit sub MAIN ($timer = False);

sub first-square (Int $n) { 

   my @start = flat '1', '0', (2 ..^ $n)».base($n);

   if $n > 10 { # analytics
       my $root  = digital-root( (1 ..^ $n)».base($n).join, :base($n) );
       my @roots = (2..$n).map(*²).map: { digital-root($_.base($n), :base($n) ) };
       if $root ∉ @roots {
           my $offset = min(@roots.grep: * > $root ) - $root;
           @start[1+$offset] = $offset ~ @start[1+$offset];
       }
   }

   my $start = @start.join.parse-base($n).sqrt.ceiling;
   my @digits = reverse (^$n)».base($n);
   my $sq;
   my $now  = now;
   my $time = 0;
   for $start .. * {
       $sq = $_ * $_;
       my $s = $sq.base($n);
       my $f;
       $f = 1 and last unless $s.contains: $_ for @digits;
       if $timer && $n > 19 && $_ %% 1_000_000 {
           $time += now - $now;
           say "N $n:  {$_}² = $sq <$s> : {(now - $now).round(.001)}s" ~
               " : {$time.round(.001)} elapsed";
           $now = now;
       }
       next if $f;
       last
   }
   sprintf "Base %2d: %12s² == %s", $n, $sq.sqrt.base($n), $sq.base($n);

}

sub digital-root ($root is copy, :$base = 10) { 

   $root = $root.comb.map({:36($_)}).sum.base($base) while $root.chars > 1;
   $root.parse-base($base);

}

say "First perfect square with N unique digits in base N: "; say .&first-square for flat 

  2 .. 12, # required
 13 .. 16, # optional
 17 .. 19, # stretch
 20, # slow
 21, # pretty fast
 22, # very slow
</lang>
Output:
First perfect square with N unique digits in base N:
Base  2:           10² == 100
Base  3:           22² == 2101
Base  4:           33² == 3201
Base  5:          243² == 132304
Base  6:          523² == 452013
Base  7:         1431² == 2450361
Base  8:         3344² == 13675420
Base  9:        11642² == 136802574
Base 10:        32043² == 1026753849
Base 11:       111453² == 1240A536789
Base 12:       3966B9² == 124A7B538609
Base 13:      3828943² == 10254773CA86B9
Base 14:      3A9DB7C² == 10269B8C57D3A4
Base 15:     1012B857² == 102597BACE836D4
Base 16:     404A9D9B² == 1025648CFEA37BD9
Base 17:    423F82GA9² == 101246A89CGFB357ED
Base 18:    44B482CAD² == 10236B5F8EG4AD9CH7
Base 19:   1011B55E9A² == 10234DHBG7CI8F6A9E5
Base 20:   49DGIH5D3G² == 1024E7CDI3HB695FJA8G
Base 21:  4C9HE8175DA² == 1023467JKAIEHB5DF9A8CG
Base 22:  4F94788GJ0F² == 102369FBGDEJ48CHI7LKA5

Python

Works with: Python version 3.7

<lang python>Perfect squares using every digit in a given base.

from itertools import (count, dropwhile, repeat) from math import (ceil, sqrt) from time import time


  1. allDigitSquare :: Int -> Int -> Int

def allDigitSquare(base, above): 

   The lowest perfect square which
      requires all digits in the given base.
   
   bools = list(repeat(True, base))
   return next(dropwhile(missingDigitsAtBase(base, bools), count(
       max(above, ceil(sqrt(int('10' + '0123456789abcdef'[2:base], base))))
   )))


  1. missingDigitsAtBase :: Int -> [Bool] -> Int -> Bool

def missingDigitsAtBase(base, bools): 

   Fusion of representing the square of integer N at a given base
      with checking whether all digits of that base contribute to N^2.
      Clears the bool at a digit position to False when used.
      True if any positions remain uncleared (unused).
   
   def go(x):
       xs = bools.copy()
       while x:
           xs[x % base] = False
           x //= base
       return any(xs)
   return lambda n: go(n * n)


  1. digit :: Int -> Char

def digit(n): 

   Digit character for given integer.
   return '0123456789abcdef'[n]


  1. TEST ----------------------------------------------------
  2. main :: IO ()

def main(): 

   Smallest perfect squares using all digits in bases 2-16

   start = time()

   print(main.__doc__ + ':\n\nBase      Root    Square')
   q = 0
   for b in enumFromTo(2)(16):
       q = allDigitSquare(b, q)
       print(
           str(b).rjust(2, ' ') + ' -> ' +
           showIntAtBase(b)(digit)(q)().rjust(8, ' ') + ' -> ' +
           showIntAtBase(b)(digit)(q * q)()
       )

   print(
       '\nc. ' + str(ceil(time() - start)) + ' seconds.'
   )


  1. GENERIC -------------------------------------------------
  1. enumFromTo :: (Int, Int) -> [Int]

def enumFromTo(m): 

   Integer enumeration from m to n.
   return lambda n: list(range(m, 1 + n))


  1. showIntAtBase :: Int -> (Int -> String) -> Int -> String -> String

def showIntAtBase(base): 

   String representation of an integer in a given base,
      using a supplied function for the string representation
      of digits.
   
   def wrap(toChr, n, rs):
       def go(nd, r):
           n, d = nd
           r_ = toChr(d) + r
           return go(divmod(n, base), r_) if 0 != n else r_
       return 'unsupported base' if 1 >= base else (
           'negative number' if 0 > n else (
               go(divmod(n, base), rs))
       )
   return lambda toChr: lambda n: lambda rs: (
       wrap(toChr, n, rs)
   )


  1. MAIN ---

if __name__ == '__main__': 

   main()</lang>
Output:
Smallest perfect squares using all digits in bases 2-16:

Base      Root    Square
 2 ->       10 -> 100
 3 ->       22 -> 2101
 4 ->       33 -> 3201
 5 ->      243 -> 132304
 6 ->      523 -> 452013
 7 ->     1431 -> 2450361
 8 ->     3344 -> 13675420
 9 ->    11642 -> 136802574
10 ->    32043 -> 1026753849
11 ->   111453 -> 1240a536789
12 ->   3966b9 -> 124a7b538609
13 ->  3828943 -> 10254773ca86b9
14 ->  3a9db7c -> 10269b8c57d3a4
15 -> 1012b857 -> 102597bace836d4
16 -> 404a9d9b -> 1025648cfea37bd9

c. 30 seconds.

REXX

The   REXX   language doesn't have a   sqrt   function,   nor does it have a general purpose radix (base) convertor,
so RYO versions were included here.

These REXX versions can handle up to base 36.

slightly optimized

<lang rexx>/*REXX program finds/displays the first perfect square with N unique digits in base N.*/ numeric digits 40 /*ensure enough decimal digits for a #.*/ parse arg n . /*obtain optional argument from the CL.*/ if n== | n=="," then n= 16 /*not specified? Then use the default.*/ @start= 1023456789abcdefghijklmnopqrstuvwxyz /*contains the start # (up to base 36).*/ 

                          w= length(n)          /* [↓]  find the smallest square with  */
   do j=2  to n;          beg= left(@start, j)  /*      N  unique digits in base  N.   */
      do k=iSqrt( base(beg,10,j) )  until #==0  /*start each search from smallest sqrt.*/
      $= base(k*k, j, 10)                       /*calculate square, convert to base J. */
      $u= $;              upper $u              /*get an uppercase version fast count. */
      #= verify(beg, $u)                        /*count differences between 2 numbers. */
      end   /*k*/
   say 'base'  right(j,w)   "   root="   right(base(k,j,10),max(5,n))    '   square='   $
   end      /*j*/

exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ base: procedure; arg x 1 #,toB,inB /*obtain: three arguments. */ 

     @l= '0123456789abcdefghijklmnopqrstuvwxyz' /*lowercase (Latin or English) alphabet*/
     @u= @l;     upper @u                       /*uppercase    "    "    "         "   */
     if inb\==10  then                          /*only convert if  not  base 10.       */
        do;  #= 0                               /*result of converted  X  (in base 10).*/
          do j=1  for length(x)                 /*convert  X:   base inB  ──► base 10. */
          #= # * inB + pos(substr(x,j,1), @u)-1 /*build a new number,  digit by digit. */
          end    /*j*/                          /* [↑]  this also verifies digits.     */
        end
     y=                                         /*the value of  X  in base  B (so far).*/
     if tob==10  then return #                  /*if TOB is ten,  then simply return #.*/
        do  while  # >= toB                     /*convert #:    base 10  ──►  base toB.*/
        y= substr(@l, (# // toB) + 1, 1)y       /*construct the output number.         */
        #= # % toB                              /*      ··· and whittle  #  down also. */
        end    /*while*/                        /* [↑]  algorithm may leave a residual.*/
     return substr(@l, # + 1, 1)y               /*prepend the residual, if any.        */

/*──────────────────────────────────────────────────────────────────────────────────────*/ iSqrt: procedure; parse arg x; r=0; q=1; do while q<=x; q=q*4; end 

       do while q>1; q=q%4; _=x-r-q; r=r%2; if _>=0 then do;x=_;r=r+q; end; end; return r</lang>
output   when using the default input:
base  2    root=           10    square= 100
base  3    root=           22    square= 2101
base  4    root=           33    square= 3201
base  5    root=          243    square= 132304
base  6    root=          523    square= 452013
base  7    root=         1431    square= 2450361
base  8    root=         3344    square= 13675420
base  9    root=        11642    square= 136802574
base 10    root=        32043    square= 1026753849
base 11    root=       111453    square= 1240a536789
base 12    root=       3966b9    square= 124a7b538609
base 13    root=      3828943    square= 10254773ca86b9
base 14    root=      3a9db7c    square= 10269b8c57d3a4
base 15    root=     1012b857    square= 102597bace836d4
base 16    root=     404a9d9b    square= 1025648cfea37bd9

more optimized

This REXX version uses a highly optimized   base   function since it was that particular function that was consuming the majority of the CPU time.

It is about   10%   faster. <lang rexx>/*REXX program finds/displays the first perfect square with N unique digits in base N.*/ numeric digits 40 /*ensure enough decimal digits for a #.*/ parse arg n . /*obtain optional argument from the CL.*/ if n== | n=="," then n= 16 /*not specified? Then use the default.*/ @start= 1023456789abcdefghijklmnopqrstuvwxyz /*contains the start # (up to base 36).*/ call base /*initialize 2 arrays for BASE function*/ 

                                                /* [↓]  find the smallest square with  */
   do j=2  to n;          beg= left(@start, j)  /*      N  unique digits in base  N.   */
      do k=iSqrt( base(beg,10,j) )  until #==0  /*start each search from smallest sqrt.*/
      $= base(k*k, j, 10)                       /*calculate square, convert to base J. */
      #= verify(beg, $)                         /*count differences between 2 numbers. */
      end   /*k*/
   say 'base'            right(j, length(n) )                    "   root="   ,
                  lower( right( base(k, j, 10), max(5, n) ) )    '   square='    lower($)
   end      /*j*/

exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ base: procedure expose !. !!.; arg x 1 #,toB,inB /*obtain: three arguments. */ 

     @= 0123456789abcdefghijklmnopqrstuvwxyz    /*the characters for the Latin alphabet*/
     if x==  then do i=1  for length(@);   _= substr(@, i, 1);    m= i - 1;    !._= m
                    !!.m= substr(@, i, 1)
                    if i==length(@) then return /*Done with shortcuts?  Then go back.  */
                    end   /*i*/                 /* [↑]  assign shortcut radix values.  */
     if inb\==10  then                          /*only convert if  not  base 10.       */
        do;  #= 0                               /*result of converted  X  (in base 10).*/
          do j=1  for length(x)                 /*convert  X:   base inB  ──► base 10. */
          _= substr(x, j, 1);  #= # * inB + !._ /*build a new number,  digit by digit. */
          end    /*j*/                          /* [↑]  this also verifies digits.     */
        end
     y=                                         /*the value of  X  in base  B (so far).*/
     if tob==10  then return #                  /*if TOB is ten,  then simply return #.*/
        do  while  # >= toB                     /*convert #:    base 10  ──►  base toB.*/
        _= # // toB;           y= !!._ || y     /*construct the output number.         */
        #= # % toB                              /*      ··· and whittle  #  down also. */
        end    /*while*/                        /* [↑]  algorithm may leave a residual.*/
     return !!.# || y                           /*prepend the residual, if any.        */

/*──────────────────────────────────────────────────────────────────────────────────────*/ iSqrt: procedure; parse arg x; r=0; q=1; do while q<=x; q=q*4; end 

       do while q>1; q=q%4; _=x-r-q; r=r%2; if _>=0 then do;x=_;r=r+q; end; end; return r

/*──────────────────────────────────────────────────────────────────────────────────────*/ lower: @abc= 'abcdefghijklmnopqrstuvwxyz'; return translate(arg(1), @abc, translate(@abc))</lang>

output   is identical to the 1st REXX version.



Sidef

<lang ruby>func first_square(b) { 

   var start = [1, 0, (2..^b)...].flip.map_kv{|k,v| v * b**k }.sum.isqrt

   start..Inf -> first_by {|k|
       k.sqr.digits(b).freq.len == b
   }.sqr

}

for b in (2..16) { 

   var s = first_square(b)
   printf("Base %2d: %10s² == %s\n", b, s.isqrt.base(b), s.base(b))

}</lang>

Output:
Base  2:         10² == 100
Base  3:         22² == 2101
Base  4:         33² == 3201
Base  5:        243² == 132304
Base  6:        523² == 452013
Base  7:       1431² == 2450361
Base  8:       3344² == 13675420
Base  9:      11642² == 136802574
Base 10:      32043² == 1026753849
Base 11:     111453² == 1240a536789
Base 12:     3966b9² == 124a7b538609
Base 13:    3828943² == 10254773ca86b9
Base 14:    3a9db7c² == 10269b8c57d3a4
Base 15:   1012b857² == 102597bace836d4
Base 16:   404a9d9b² == 1025648cfea37bd9

zkl

Translation of: Julia

<lang zkl>fcn squareSearch(B){ 

  basenumerals:=B.pump(String,T("toString",B)); // 13 --> "0123456789abc"
  highest:=("10"+basenumerals[2,*]).toInt(B);   // 13 --> "10" "23456789abc"
  foreach n in ([highest.toFloat().sqrt().toInt() .. highest]){
    ns:=(n*n).toString(B);
    if(""==(basenumerals - ns) ) return(n.toString(B),ns);
 }
 Void

}</lang> <lang zkl>println("Base Root N"); foreach b in ([2..16]) 

 { println("%2d %10s  %s".fmt(b,squareSearch(b).xplode())) }</lang>
Output:
Base     Root   N
 2         10  100
 3         22  2101
 4         33  3201
 5        243  132304
 6        523  452013
 7       1431  2450361
 8       3344  13675420
 9      11642  136802574
10      32043  1026753849
11     111453  1240a536789
12     3966b9  124a7b538609
13    3828943  10254773ca86b9
14    3a9db7c  10269b8c57d3a4
15   1012b857  102597bace836d4
16   404a9d9b  1025648cfea37bd9
Retrieved from "https://rosettacode.org/wiki/First_perfect_square_in_base_n_with_n_unique_digits?oldid=290576"