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

;* [[Casting out nines]]

<br>

 

=={{header|C}}==

#include <string.h>

 

 

for (pos = 0; buffer[pos] != 0; pos++) {

count++;

}

}

 

return 0;

{{out}}

<pre>Base 2 : Num 10 Square 100

Base 15 : Num 1012B857 Square 102597BACE836D4</pre>

 

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

{{trans|C#}}

A stripped down version of the C#, using unsigned longs instead of BigIntegers, and shifted bits instead of a HashSet accumulator.

#include <iostream>

#include <cstdlib>

cout << "\nComputation time was " << et.count() * 1000 << " milliseconds" << endl;

return 0;

{{out}}

<pre>base inc id root sqr test count

=={{header|D}}==

{{trans|C}}

import std.exception;

import std.math;

find(i);

}

{{out}}

<pre>Base 2 : Num 10 Square 100

Base 15 : Num 1012B857 Square 102597BACE836D4

Base 16 : Num 404A9D9B Square 1025648CFEA37BD9</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|Factor}}==

The only thing this program does to save time is start the search at a root high enough such that its square has enough digits to be pandigital.

math.parser math.ranges math.statistics sequences ;

IN: rosetta-code.A260182

: main ( -- ) 2 16 [a,b] [ show-base ] each ;

 

{{out}}

<pre>

Base 16: 404a9d9b squared = 1025648cfea37bd9

</pre>

 

=={{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}}

 

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

 

import (

}

}

 

{{out}}

Base 28: 58a3ckp3n4cqd7² = 1023456cgjbirqedhp98kmoan7fl in 911.059s

</pre>

 

=={{header|J}}==

pandigital=: [ = [: # [: ~. #.inv NB. BASE pandigital Y

<pre>

assert 10 pandigital 1234567890

+----+------------+------------+

</pre>

 

=={{header|JavaScript}}==

{{Trans|Python}}

'use strict';

 

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

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

I use now gmp to calculate the start values.Check Chai Wah Wu list on oeis.org/A260182<BR>

GetThreadCount needs improvement for Linux<BR>

 

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

//digits of base b aka pandigital

{$IFDEF FPC}

{$MODE DELPHI}

{$ElSE}

{$APPTYPE CONSOLE}

uses

{$IFDEF UNIX}

{$ENDIF}

gmp,// to calculate start values

 

type

tRegion64 = 0..63;

tSolSet64 = set of tRegion64;

 

 

 

tDgtRootSqr = packed record

cft_delta: tNumtoBase;

cft_count : Uint64;

cft_ThreadID: NativeUint;

cft_ThreadHandle: NativeUint;

end;

 

procedure AddNum(var add1: tNumtoBase; const add2: tNumtoBase); forward;

 

var

ThreadBlocks: array of tCombineForOneThread;

Num, sqr2B, deltaNextSqr, delta: tNumtoBase;

DgtRtSqr: tDgtRootSqr;

gblThreadCount,

Finished: Uint32;

 

function GetThreadCount: NativeUInt;

begin

{$IFDEF Windows}

{$ELSE}

{$ENDIF}

end;

 

var

i: NativeInt;

begin

with num do

begin

end;

end;

 

procedure OutNumSqr;

begin

end;

 

function getDgtRtNum(const num: tNumtoBase): NativeInt;

var

i: NativeInt;

begin

with num do

begin

Result := 0;

Result := Result mod (ntb_bas - 1);

end;

Inc(i);

until i > base;

end;

end;

procedure conv_ui_num(base: NativeUint; ui: Uint64; var Num: tNumtoBase);

var

i: NativeUInt;

begin

with num do

begin

ntb_bas := base;

ntb_cnt := 0;

end;

 

procedure conv2Num(base: NativeUint; var Num: tNumtoBase; var s: mpz_t);

var

tmp: mpz_t;

i: NativeUInt;

begin

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

Num.ntb_dgt[i] := 0;

with num do

begin

ntb_bas := base;

i := 0;

repeat

Inc(i);

end;

mpz_clear(tmp);

//calc sqrt +1 and convert n new format.

var

k, dblDgt: NativeUint;

 

 

mpz_sqrt(sv, sv_sqr);

mpz_mul(sv_sqr, sv, sv);

 

conv2Num(base, sqr2B, sv_sqr);

 

mpz_clear(sv_sqr);

mpz_clear(sv);

end;

 

end;

 

var

pMask: tpMask64;

i: NativeInt;

begin

begin

end;

end;

 

procedure IncNumBig(var add1: tNumtoBase; n: Uint64);

var

i, s, b, carry: NativeUInt;

begin

i := 0;

carry := 0;

while n > 0 do

begin

carry := Ord(s >= b);

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

n := n div b;

Inc(i);

while carry <> 0 do

begin

carry := Ord(s >= b);

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

Inc(i);

end;

 

end;

 

//prerequisites carry < base

var

i, s, b: NativeUInt;

begin

b := add1.ntb_bas;

i := 0;

while carry <> 0 do

begin

carry := Ord(s >= b);

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

Inc(i);

end;

end;

end;

 

//starting the threads at num,num+stepWidth,..,num+(thdCount-1)*stepWidth

//stepwith not stepWidth but thdCount*stepWidth

var

tmpnum,tmpsqr2B,tmpdeltaNextSqr,tmpdelta :tNumToBase;

Begin

tmpnum := num;

tmpdeltaNextSqr := deltaNextSqr;

tmpdelta := delta;

Begin

end;

end;

end;

end;

 

 

 

 

 

end;

 

procedure TestRunThd(parameter: pointer);

var

begin

begin

end;

end;

 

var

stepWidth: Uint64;

begin

StartValueCreate(base);

deltaNextSqr := num;

AddNum(deltaNextSqr, deltaNextSqr);

end;

CalcDeltaSqr(num,deltaNextSqr,delta,stepWidth);

i := 0;

begin

while (j < UsedThreads) and (finished = 0) do

begin

cft_ThreadHandle :=

BeginThread(@TestRunThd, Pointer(j), cft_ThreadID,

end;

Inc(j);

end;

WaitForThreadTerminate(ThreadBlocks[0].cft_ThreadHandle, -1);

repeat

begin

WaitForThreadTerminate(cft_ThreadHandle, -1);

finished := j;

end;

until j = 0;

end;

OutNumSqr;

end;

 

var

base: NativeUint;

begin

gblThreadCount:= GetThreadCount;

writeln(' Cpu Count : ', gblThreadCount);

Test(base);

setlength(ThreadBlocks, 0);

{$IFDEF WINDOWS}

readln;

{$ENDIF}

Num 10 sqr 100

 

Base 29 test every 1 threads = 12

Start : Num 5BAEFC5QHESPCLA sqr 10223456789ABCDKM4JI4S470KCSHD

2.00 min 1496695534873

.. 27.00 min 20178502394905

Result : Num 1011J10DEFW1QTVBXR sqr 102345678RUEPV9KGQIWFOBAXCNSLDMYJHT

1681.925 s Testcount : 614575698110 20895573735740

 

{{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));

 

=={{header|Phix}}==

Partial translation of VB with bitmap idea from C++ and adopting the digit-array approach from pascal

instead of base conversion.

{{out}}

<pre>

Requires version 0.8.1+, not yet shipped, which will include demo\rosetta\PandigitalSquares.exw<br>

64 bit code omitted for clarity, the code in PandigitalSquares.exw is twice as long.

mask = length(sqi)

#ilASM{

@@:

mov [carry],eax

{{output}}

<pre>

=={{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|Raku}}==

[https://tio.run/##dVTNbtpAEL7zFBPXBDuBlQ1SqkDz0x4i5VBeoGqQA@uwlVmb3XVThMi5fZ1ce@NR@iJ0Zm1jO1UtYS8zO9/8fDOTcZVcHA65FAZ0/gifP95PwXONWHEFV3AXJZr7k06HdLFQ2gz0Oo8UB@9eGnClD9sO4LPawK02kTJoFCeRgV7Y60MvwJc3BMYe6O7@N3uMNB/jGSHJTMR4hmsIA9jCO4hklGyMmGurLHFdlaYGEHchnoSJkgH990p37FsqZB/GhOtROBhsw/aW7mq09YaMoZqtosw727/awxh9tjDdGatwWpCwq0EpYhvQn5@/KvjtUVuFnMax5lSLlZBecYs9KY4uzzDbAsCHQXGatMyLvL6E5yXIV0Sp8F7@1dbGu07xrvhwKz4alWJZpDQfVKkxvUbFnItEyKfJkUhbFKqa4t853gfv4S17Rx/r@izTZ6IJP7WMGgllQcNCFec4VVWIjGFZ6iIiKJqw/WuLSpcCQtWRorY2rv@6Md4MsZkWkETaQC4TrjXasnkqTSSkxhxmNoAy1Ta9RfOfnpateWmPM@h2IZwFQUC/N5QXaZ7b3InVYwmqR0cbcKaoGANs3dlu/1okAx9cfQ3YiF5t6TOV5nLhsSAI/Z124KUFRY9DJtZp6y7wJMo0Xzht55aYBi91s9Aj@Q9j025WUNPwu7NaQoXs1IY6U0Ka2APnE7IB3eFiDN1wpCmvK@gORoF2@ui4T1CNoWryhwNQZ1atnJub8gjn8J@SwMkJ9HpI/65YS80RRmP7ERrmabbBKXbJHfVDUK2q4sZV8cWWWD3arbAdjy5wA/g7nIp8VUZJbx@elyLh1f0lThC1xaQGa02VNSmCQ9LBuaOtCRlXMZ/jji2257MwS5hiZ4p1zqGcNyHBBjsdAzJI1uy0tXOpY2m5kmdaqhAO@7g1FV/nQvEFisORFV@QOM2MSHGhkvi9FV@SWBvFzXzZmRwOfwE Try it online!]

 

 

Only search square numbers that have at least N digits;

25, # very slow

26, # "

{{out}}

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

These REXX versions can handle up to base '''36''', but could be extended.

===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|Ruby}}==

Takes about 15 seconds on my dated PC, most are spent calculating base 13.

 

2.upto(16) do |n|

puts "Base %2d:%10s² = %-14s" % [n, res.to_s(n), (res*res).to_s(n)]

end

{{out}}

<pre>Base 2: 10² = 100

 

=={{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>