First perfect square in base n with n unique digits

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)

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

<lang go>package main

import (

   "fmt"
   "math"
   "strconv"

)

const maxBase = 16 const minSq16 = "1023456789abcdef"

var found = make([]bool, maxBase) var blankFound = make([]bool, maxBase)

func containsAll(sq string, base int) bool {

   copy(found, blankFound)
   for _, r := range sq {
       if r < 58 {
           found[r-48] = true
       } else {
           found[r-87] = true
       }
   }
   for _, r := range found[:base] {
       if r == false {
           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

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

Perl

Library: ntheory

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

sub first_square {

   my $n = shift;
   my $r = int( $n**( ($n - 1) / 2) ) || 1;
   my @digits = reverse split , substr('0123456789abcdef',0,$n);
   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

<lang perl6># Only search perfect squares that have at least N digits;

1. smaller could not possibly match.

sub first-square (Int $n) {

   my int $start = (($n - 1)/2).exp($n).floor || 2;
   my @digits = reverse (^$n)».base: $n;
   my $sq = ($start .. *).map( {.²} ).hyper.first: {
       my $s = .base: $n;
       my $f;
       $f = 1 and last unless $s.contains: $_ for @digits;
       next if $f;
       $_
   }
   sprintf "Base %2d: %10s² == %s", $n, $sq.sqrt.base($n), $sq.base($n);

}

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

  2 .. 12, # required
 13 .. 16  # optional

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