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

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'''.

 

;See also:

<br>

 

 

 

 

 

 

}

 

}

 

}

 

int main() {

{{out}}

 

{{libheader|System.Numerics}}

{{trans|Visual Basic .NET}}

Based on the Visual Basic .NET version, plus it shortcuts some of the ''allIn()'' checks. When the numbers checked are below a threshold, not every digit needs to be checked, saving a little time.

using System.Collections.Generic;

using System.Numerics;

Console.WriteLine("Elasped time was {0,8:0.00} minutes", (DateTime.Now - st0).TotalMinutes);

}

{{out}}

<pre>base inc id root square test count time total

28 9 58A3CKP3N4CQD7 -> 1023456CGJBIRQEDHP98KMOAN7FL 749592976 508.4498s 1215.9292s

Elasped time was 20.27 minutes

</pre>

 

=={{header|F_Sharp|F#}}==

===The Task===

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

{{out}}

<pre>

===Using [[Factorial base numbers indexing permutations of a collection]]===

On the discussion page for [[Factorial base numbers indexing permutations of a collection]] an anonymous contributor queries the value of [[Factorial base numbers indexing permutations of a collection]]. Well let's see him use an inverse Knuth shuffle to partially solve this task. This solution only applies to bases that do not require an extra digit. Still I think it's short and interesting.<br>Note that the minimal candidate is 1.0....0 as a factorial base number.

// Nigel Galloway: May 30th., 2019

let fN n g=let g=n|>Array.rev|>Array.mapi(fun i n->(int64 n)*(pown g i))|>Array.sum

printfn "%A" (fG 12|>Seq.head) // -> [|1; 2; 4; 10; 7; 11; 5; 3; 8; 6; 0; 9|]

printfn "%A" (fG 14|>Seq.head) // -> [|1; 0; 2; 6; 9; 11; 8; 12; 5; 7; 13; 3; 10; 4|]

 

=={{header|Go}}==

This takes advantage of major optimizations described by Nigel Galloway and Thundergnat (inspired by initial pattern analysis by Hout) in the Discussion page and a minor optimization contributed by myself.

 

import (

}

}

 

{{out}}

<pre>

Base 2: 10² = 100 in 0.000s

Base 6: 523² = 452013 in 0.000s

Base 7: 1431² = 2450361 in 0.000s

</pre>

<br>

 

For example, to reach base 28 (the largest base shown in the OEIS table) we have:

 

import (

}

}

 

{{out}}

Base 2: 10² = 100 in 0.000s

Base 3: 22² = 2101 in 0.000s

</pre>

 

=={{header|JavaScript}}==

{{Trans|Python}}

'use strict';

 

// in separate events to avoid asynchronous disorder.

print('Smallest perfect squares using all digits in bases 2-12:\n')

 

print(showBaseSquare(2));

// MAIN ---

return main();

{{Out}}

<pre>Smallest perfect squares using all digits in bases 2-12:

11 -> 111453 -> 1240a536789

12 -> 3966b9 -> 124a7b538609</pre>

 

=={{header|Julia}}==

Runs in about 4 seconds with using occursin().

hasallin(n, nums, b) = (s = string(n, base=b); all(x -> occursin(x, s), nums))

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

end

<pre>

Base Root N

16 404a9d9b 1025648cfea37bd9

</pre>

 

=={{header|Pascal}}==

Than brute force.<BR>

[https://tio.run/##zVdtU9tGEP6uX7EfMmMJZCMBIYmNmYGAGzcJThOntM0wGb0c9lH5ZKQTlMnkr5fu3p3ebDfTtM1M/AHkvX27Z59dr9LwmkWyuwzyKEi6V8vo4WGZpbMsWAD@pzN/YO3sjLiIQc4Z5IsgSVguQRSLkGUgQKYQBjmD0IU8RZ0Az7YEcBElRcxyQH10EPMZlzmkV0bZ@vRoPDo9G8HozfPPnx69npyewenZqzcvxvjt7Px0PPpsFTnLLYD8Pi8kT/KBFaUilxZE8yB7xyT0Iciy4P6D1@vtHVySbzqBYcfzd/f2Hx88efrs@OQ5BvnhxfjHl69en0/e/PT23fT9zxe//PpbZwBgyfslwwjyvFjI9IQSG0LGojSLAcUrHyHDj/GsHdbv7qvA4b1kg80mkZDu5hNEAtDbBYZbs2UCZbdBhnJMjhzkN9nuCT3ELJEBCsm2znywFgKvYF0VIpI8FfCaC46l@yhswr9/Hkh@y95zIZ0@/T3Ypyp3wPfWkev1eh2TCseQtenAOmEzLlCesbxIEJmhqi6msrMDwe8BdHyvg8fjka76EewSiYQGd5Rm5HBIQs2hrg9xapCoXeqnLVLY5oNWNJnh/WxERtpa6Gx7vWf0cSo8LAUlWEjniMVFxuB5Km53kb82Xop43G@gKEo4VmEqq3FTpBj6/VhjpiBpIAIVJOpmnk53yQKprqWNh9g1Mb/VWCk5xu8Zen3gl0qjS7pbtYogKcn0V2wvmzv0XAhsDjw20UpXSDuy4E0ZEa6skUVFihKGEBTLJXay7lCrURdOdZnz2dyuASrTdLBSpkfWk8dE1kCfFOTEVi28AnqFbU2vcZNdd1zOyUSTo5Q2EvWfdM2VFYPuBObt1QnCXcYlszvQcQZtw41WLSMzaz7UF7xUTuh@m7g1FhHe64TPFLmCOPbb7DJcGStG7ewsM5axm4LnGCvH71QaHJnoSA3bYMFc1e6tvivRcnM3dCMcRvebcQvpipRCWfxBi5fG0ny7m/OEIY2OSgxqnPOWH43CtrLeRgMc3RBqXCuPkyy286NhaPBWDvIu2F2tcXyOJuZsxa/SbDDedMoq6TX8NOHKzLXnw69K/1tkvTlHnICVCXXmITUXTsK2s7pn/4ZXG0mlsutX9V/nVR820EpfezjU9DpUKk1i/StKffel@O@FOI7jZiFc/LPbnmX/qKvJ9ohsXeUGDjUu2ySqxqFu7q@sRrutq1Hn0TAn773m0CNIwi@Xp7L5tuUyAxVKPjVTXaUWTvz/i1m4qGRskd4y2uL4FeRHoV5RwnsIuezKOx7HCRez728kTHENb25z48aWgrMTzCKjaM/da5f09dq86TdW/dopb49Vqmr6trdGJa@WJ72P4qrvrp/RytqQVxsrDfRiQSLTRuWJWz4ofTPsqkPfaVFjdavCPSbFLQjwfSGu1xiA6sLGRHfDtaoMJd/70s9/w7h8nLwF24d8njTMqdjXl05daKOsMwZVZmOk4BiWzupa4@fk7dnxSzOh6D6C/SExSEEjQ79oqQMDmka@hdg6ZrvO5kXxKkj09ldvKhjB1SpmSVNeVTJGoCIqjQviSSJs3vf3ncYGpGk39fowPQ0km/KFCqLW/r6o@EZXLOfN1FN8SO8GJf/Qb0dZrL0tlQ8aE1s4UFcJK6gXO6quDmjeKfyDsp5VrzjNYDYG7049Z@vpwb7n9X2vv6fOy3fTi/H56eTi3eeMBXEiBtWLKd659/DwZ3SVBLP8oTvZ@ws Try it online!]

//Find the smallest number n to base b, so that n*n includes all

//digits of base b

writeln((now-T0)*86400:10:3);

{$IFDEF WINDOWS}readln;{$ENDIF}

{{out}}

<pre>base n square(n) Testcnt

</pre>

===Inserted nearly all optimizations found by [[User:Hout|Hout]] and [[User:Nigel Galloway|Nigel Galloway]]===

//Find the smallest number n to base b, so that n*n includes all

//digits of base b aka pandigital

{$IFDEF FPC}

//{$R+,O+}

{$MODE DELPHI}

{$ENDIF}

uses

 

const

{$ALIGN 32}

 

charSet: array[0..62] of char =

'0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';

type

tNumtoBase = packed record

ntb_dgt: array[tRegion1] of byte;

ntb_cnt,

end;

tDgtRootSqr = packed record

drs_bas: byte;

drs_Sol: byte;

drs_SolCnt: byte;

drs_NeedsOneMoreDigit: boolean;

end;

 

var

{$ALIGN 32}

Num, sqr2B, deltaNextSqr, delta: tNumtoBase;

DgtRtSqr: tDgtRootSqr;

{$ALIGN 8}

 

procedure OutNum(const num: tNumtoBase);

Write(' ');

end;

procedure OutNumSqr;

writeln;

end;

 

procedure CalcDgtRootSqr(base: NativeUInt);

var

begin

ChkCnt[i] := 0;

ChkSet[i] := [];

for i := 0 to base - 1 do

if drs_List[i] = drs_Sol then

Inc(drs_SolCnt);

end;

//if not found then NeedsOneMoreDigit

drs_NeedsOneMoreDigit := drs_SolCnt = 0;

for j := 1 to Base do

for i := 0 to Base do

end;

i := 1;

repeat

drs_Dgt2Add := i;

BREAK;

end;

until i > base;

end;

end;

i: NativeUInt;

begin

for i := 0 to high(tNumtoBase.ntb_dgt) do

Num.ntb_dgt[i] := 0;

var

sv_sqr, sv: mpz_t;

 

begin

begin

dblDgt := DgtRtSqr.drs_Dgt2Add;

mpz_mul_ui(sv_sqr, sv_sqr, base);

mpz_add_ui(sv_sqr, sv_sqr, k);

end

else

mpz_mul_ui(sv_sqr, sv_sqr, base);

mpz_add_ui(sv_sqr, sv_sqr, k);

end;

mpz_mul_ui(sv_sqr, sv_sqr, base);

mpz_add_ui(sv_sqr, sv_sqr, k);

end;

end

else

begin

begin

mpz_mul_ui(sv_sqr, sv_sqr, base);

mpz_clear(sv_sqr);

mpz_clear(sv);

end;

 

end;

 

//prerequisites carry < base

var

end;

 

//add1 <= add1+add2;

var

begin

carry := 0;

for i := 0 to add2.ntb_cnt - 1 do

begin

carry := Ord(s >= base);

s := s - (-carry and base);

while carry = 1 do

begin

carry := Ord(s >= base);

s := s - (-carry and base);

add1.ntb_cnt := i;

end;

var

begin

end;

 

var

begin

repeat

//next square number

until TestSetComplete = TestSet;

end;

 

var

begin

StartValueCreate(base);

deltaNextSqr := num;

AddNum(deltaNextSqr, deltaNextSqr);

begin

//Find first number which can get the solution

while drs_List[getDgtRtNum(num)] <> drs_sol do

begin

AddNum(sqr2B, deltaNextSqr);

end;

end;

i := 0;

end;

 

var

T: TDateTime;

begin

{$IFDEF WINDOWS}

readln;

{$ENDIF}

Base 2 test every 1

Base 3 test every 1

Base 6 test every 5

Base 7 test every 6

Base 8 test every 7

Base 9 test every 4

Base 10 test every 3

Base 11 test every 10

Base 12 test every 11

Base 14 test every 13

Base 15 test every 14

Base 16 test every 15

Base 18 test every 17

Base 19 test every 6

Base 20 test every 19

Base 22 test every 21

Base 23 test every 22

Base 24 test every 23

Base 25 test every 12

Base 26 test every 5

Base 27 test every 26

Base 28 test every 9

 

</pre>

 

 

{{libheader|ntheory}}

use warnings;

use feature 'say';

 

say "First perfect square with N unique digits in base N: ";

{{out}}

<pre>First perfect square with N unique digits in base N:

 

{{libheader|ntheory}}

use warnings;

use ntheory qw(:all);

printf("Base %2d: %10s² == %s\n", $n,

todigitstring(sqrtint($s), $n), todigitstring($s, $n));

 

{{out}}

 

=={{header|Python}}==

{{Works with|Python|3.7}}

 

from time import time

 

'''

bools = list(repeat(True, base))

 

 

# missingDigitsAtBase :: Int -> [Bool] -> Int -> Bool

def missingDigitsAtBase(base, bools):

Clears the bool at a digit position to False when used.

True if any positions remain uncleared (unused).

 

 

# main :: IO ()

def main():

print(

str(b).rjust(2, ' ') + ' -> ' +

showIntAtBase(b)(digit)(q * q)('')

)

 

 

 

# enumFromTo :: (Int, Int) -> [Int]

 

 

def showIntAtBase(base):

'''String representation of an integer in a given base,

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>Smallest perfect squares using all digits in bases 2-16:

 

c. 30 seconds.</pre>

 

=={{header|REXX}}==

<br>so RYO versions were included here.

 

===slightly optimized===

numeric digits 40 /*ensure enough decimal digits for a #.*/

@start= 1023456789abcdefghijklmnopqrstuvwxyz /*contains the start # (up to base 36).*/

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, $u) /*count differences between 2 numbers. */

end /*k*/

end /*j*/

exit /*stick a fork in it, we're all done. */

@u= @l; upper @u /*uppercase " " " " */

if inb\==10 then /*only convert if not 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. */

y= /*the value of X in base B (so far).*/

if tob==10 then return # /*if TOB is ten, then simply return #.*/

y= substr(@l, (# // toB) + 1, 1)y /*construct the output number. */

#= # % toB /* ··· and whittle # down also. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

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

{{out|output|text=&nbsp; when using the default input:}}

<pre>

</pre>

 

 

It is about &nbsp; '''10%''' &nbsp; faster.

numeric digits 40 /*ensure enough decimal digits for a #.*/

@start= 1023456789abcdefghijklmnopqrstuvwxyz /*contains the start # (up to base 36).*/

call base /*initialize 2 arrays for BASE function*/

/* [↓] find the smallest square with */

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

end /*j*/

exit /*stick a fork in it, we're all done. */

end /*i*/ /* [↑] assign shortcut radix values. */

if inb\==10 then /*only convert if not 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. */

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

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

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text=&nbsp; is identical to the 1^st REXX version.}} <br><br>

 

=={{header|Sidef}}==

 

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

var s = first_square(b)

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

{{out}}

<pre>

</pre>

 

=={{header|Visual Basic .NET}}==

{{libheader|System.Numerics}}

 

Module Program

Console.WriteLine("Elasped time was {0,8:0.00} minutes", (DateTime.Now - st0).TotalMinutes)

End Sub

{{out}}This output is on a somewhat modern PC. For comparison, it takes TIO.run around 30 seconds to reach base20, so TIO.run is around 3 times slower there.

<pre>base inc id root square test count time total

28 9 58A3CKP3N4CQD7 -> 1023456CGJBIRQEDHP98KMOAN7FL 749593055 711.660s 1617.981s

Elasped time was 26.97 minutes</pre>Base29 seems to take an order of magnitude longer. I'm looking into some shortcuts.

 

=={{header|zkl}}==

{{trans|Julia}}

basenumerals:=B.pump(String,T("toString",B)); // 13 --> "0123456789abc"

highest:=("10"+basenumerals[2,*]).toInt(B); // 13 --> "10" "23456789abc"

}

Void

foreach b in ([2..16])

{{out}}

<pre>