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

{{trans|F#}}

import Data.List (find, unfoldr)

import Data.Char (intToDigit)

digits :: Integral a => a -> a -> [a]

sequenceForBaseN :: Integral a => a -> [a]

searchSequence :: Integral a => a -> Maybe a

searchSequence

where

digitsSet = Set.fromList [0 .. pred b]

[2 .. 16]

where

{{out}}

<pre>Base 2: 10² -> 100

 

=={{header|J}}==

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

<pre>

assert 10 pandigital 1234567890

=={{header|Java}}==

{{trans|C#}}

import java.time.Duration;

import java.util.ArrayList;

}

}

{{out}}

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

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

=={{header|Kotlin}}==

{{trans|Java}}

import java.time.Duration

import java.util.ArrayList

++base

}

{{out}}

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

26 5 K99MDB35N8K25 -> ABDJNHCPF97GKMEI6OL8543201 402922566 05:15.307 06:49.008

27 26 JJBO73E11F1101 -> A6N9QC7PKGFJIBHDMOLE8543201 457555291 06:01.338 12:50.347</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

 

The runtime is on my 6-Core PC AMD Ryzen 2200G ( 3.7 Ghz on all 4 cores Linux64 with SMT= off)<BR>

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

//digits of base b aka pandigital

readln;

{$ENDIF}

{{out}}

<pre style="height:35ex">

 

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

parse arg LO HI . /*obtain optional argument from the CL.*/

b2d: return x2d( b2x( arg(1) ) ) /*convert binary number to decimal*/

d2b: return x2b( d2x( arg(1) ) ) + 0 /* " hexadecimal " " " */

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

<pre>

 

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

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

parse arg LO HI . /*obtain optional argument from the CL.*/

b2d: return x2d( b2x( arg(1) ) ) /*convert binary number to decimal*/

d2b: return x2b( d2x( arg(1) ) ) + 0 /* " hexadecimal " " " */

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