First perfect square in base n with n unique digits: Difference between revisions
Thundergnat (talk | contribs) (→{{header|Perl 6}}: Tweaks; Add some stretch examples) |
(→{{header|Javascript}}: Added a rudimentary JS draft bases 2-12 only (JS integers truncate by 15)) |
||
Line 112: | Line 112: | ||
Base 16: 404a9d9b² = 1025648cfea37bd9 |
Base 16: 404a9d9b² = 1025648cfea37bd9 |
||
</pre> |
</pre> |
||
=={{header|JavaScript}}== |
|||
{{Trans|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> |
|||
{{Out}} |
|||
<pre>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</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
Revision as of 23:19, 22 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.
- (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
JavaScript
<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
<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
As long as you have the patience, this will work for bases 2 through 36.
Base 17 is crushingly slow....
<lang perl6># Only search perfect squares that have at least N digits;
- smaller could not possibly match.
sub first-square (Int $n) {
my $start = ([~] flat '10', (2 ..^ $n)».base($n)).parse-base($n).sqrt.floor; my @digits = reverse (^$n)».base($n); my $now = now; my $sq; for $start .. * { $sq = .²; my $s = $sq.base: $n; my $f; $f = 1 and last unless $s.contains: $_ for @digits; next if $f; last } 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 #17,# stretch - loooong stretch 18, # stretch 19, # stretch 20, # stretch
- </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 18: 44B482CAD² == 10236B5F8EG4AD9CH7 Base 19: 1011B55E9A² == 10234DHBG7CI8F6A9E5 Base 20: 49DGIH5D3G² == 1024E7CDI3HB695FJA8G
Python
<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
- allDigitSquare :: Int -> Int
def allDigitSquare(base):
The lowest perfect square which requires all digits in the given base. bools = list(repeat(True, base)) return next(dropwhile(missingDigitsAtBase(base, bools), count( ceil(sqrt(int('10' + '0123456789abcdef'[2:base], base))) )))
- 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)
- digit :: Int -> Char
def digit(n):
Digit character for given integer. return '0123456789abcdef'[n]
- TEST ----------------------------------------------------
- main :: IO ()
def main():
Smallest perfect squares using all digits in bases 2-16
start = time()
print(main.__doc__ + ':\n\nBase Root Square') for b in enumFromTo(2)(16): q = allDigitSquare(b) print( str(b).rjust(2, ' ') + ' -> ' + showIntAtBase(b)(digit)(q)().rjust(8, ' ') + ' -> ' + showIntAtBase(b)(digit)(q * q)() )
print( '\nc. ' + str(ceil(time() - start)) + ' seconds.' )
- GENERIC -------------------------------------------------
- enumFromTo :: (Int, Int) -> [Int]
def enumFromTo(m):
Integer enumeration from m to n. return lambda n: list(range(m, 1 + n))
- 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) )
- 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. 32 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.
This REXX version can handle up to base 36. <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