First perfect square in base n with n unique digits
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.
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, numerals, b) = (s = string(n, base=b); all(x -> occursin(x, s), numerals))
function squaresearch(bas)
basenumerals = [c for c in num[1:bas]]
highest = parse(Int, "10" * num[3:bas], base=bas)
lowest = Int(trunc(sqrt(highest)))
for n in lowest:highest
nsquared = n * n
if hasallin(nsquared, basenumerals, bas)
return nsquared
end
end
throw("failed to find num for base $bas")
end
println("Base Root N") for b in 2:16
n = squaresearch(b) println(lpad(b, 3), lpad(string(Int(trunc(sqrt(n))), base=b), 10), " ", string(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
Stopping at 15 because 16 requires use bigint, which would make things very slow
<lang perl>use strict; use warnings; use feature 'say'; use ntheory 'todigitstring';
sub first_square {
my($n) = @_;
my $sq;
my $r = int($n**(($n-1)/2)) || 1;
my @digits = split , substr('0123456789abcdef',0,$n);
TRY: while (1) {
$sq = $r++**2;
my $cnt = 0;
my $s = todigitstring($sq, $n);
for (@digits) {
redo TRY if -1 == index($s,$_);
last TRY if ++$cnt == $n;
}
}
sprintf "Base %2d: %10s² == %s", $n, todigitstring(sqrt($sq),$n), todigitstring($sq, $n);
}
say "First perfect square with N unique digits in base N: "; say first_square($_) for 2..15;</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
Perl 6
<lang perl6># Only search perfect squares that have at least N digits;
- smaller could not possibly match.
sub first-square (Int $n) {
my $start = (($n - 1)/2).exp($n).floor || 1; my $sq = ($start .. *).map( *² ).hyper.first: *.base($n).comb.unique >= $n; 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