First perfect square in base n with n unique digits: Difference between revisions
(Convert to draft task.) |
(Added Go) |
||
Line 13: | Line 13: | ||
* (optional) Do the same for bases '''13''' through '''16'''. |
* (optional) Do the same for bases '''13''' through '''16'''. |
||
=={{header|Go}}== |
|||
<lang go>package main |
|||
import ( |
|||
"fmt" |
|||
"math" |
|||
"strconv" |
|||
) |
|||
func containsAll(sq string, base int) bool { |
|||
set := make(map[rune]bool) |
|||
for _, r := range sq { |
|||
set[r] = true |
|||
} |
|||
if len(set) == base { |
|||
return true |
|||
} |
|||
return false |
|||
} |
|||
func main() { |
|||
const maxBase = 16 |
|||
const minSq16 = "1023456789abcdef" |
|||
for n, base := uint64(2), 2; ; n++ { |
|||
sq := strconv.FormatUint(n*n, base) |
|||
if len(sq) < base || !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 = uint64(math.Sqrt(float64(minNN))) - 1 |
|||
} |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
Revision as of 09:45, 21 May 2019
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"
)
func containsAll(sq string, base int) bool {
set := make(map[rune]bool) for _, r := range sq { set[r] = true } if len(set) == base { return true } return false
}
func main() {
const maxBase = 16 const minSq16 = "1023456789abcdef" for n, base := uint64(2), 2; ; n++ { sq := strconv.FormatUint(n*n, base) if len(sq) < base || !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 = 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 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.Bag.elems >= $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