Rosetta Code

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

Page Discussion

First perfect square in base n with n unique digits (view source)

Revision as of 10:51, 14 March 2020

17 bytes added ,  4 years ago
Rename Perl 6 -> Raku, alphabetize, minor clean-up
m (Remove unnecessary (and incorrect) list. Pascal entry has a bug)
(Rename Perl 6 -> Raku, alphabetize, minor clean-up)
Line 115:
Base 14 : Num 3A9DB7C Square 10269B8C57D3A4
Base 15 : Num 1012B857 Square 102597BACE836D4</pre>
 
=={{header|C++}}==
{{trans|C#}}
A stripped down version of the C#, using unsigned longs instead of BigIntegers, and shifted bits instead of a HashSet accumulator.
<lang Cpp>#include <string>
#include <iostream>
#include <cstdlib>
#include <math.h>
#include <chrono>
#include <iomanip>
 
using namespace std;
 
const int maxBase = 16; // maximum base tabulated
int base, bmo, tc; // globals: base, base minus one, test count
const string chars = "0123456789ABCDEF"; // characters to use for the different bases
unsigned long long full; // for allIn() testing
 
// converts base 10 to string representation of the current base
string toStr(const unsigned long long ull) {
unsigned long long u = ull; string res = ""; while (u > 0) {
lldiv_t result1 = lldiv(u, base); res = chars[(int)result1.rem] + res;
u = (unsigned long long)result1.quot;
} return res;
}
 
// converts string to base 10
unsigned long long to10(string s) {
unsigned long long res = 0; for (char i : s) res = res * base + chars.find(i); return res;
}
 
// determines whether all characters are present
bool allIn(const unsigned long long ull) {
unsigned long long u, found; u = ull; found = 0; while (u > 0) {
lldiv_t result1 = lldiv(u, base); found |= (unsigned long long)1 << result1.rem;
u = result1.quot;
} return found == full;
}
 
// returns the minimum value string, optionally inserting extra digit
string fixup(int n) {
string res = chars.substr(0, base); if (n > 0) res = res.insert(n, chars.substr(n, 1));
return "10" + res.substr(2);
}
 
// perform the calculations for one base
void doOne() {
bmo = base - 1; tc = 0; unsigned long long sq, rt, dn, d;
int id = 0, dr = (base & 1) == 1 ? base >> 1 : 0, inc = 1, sdr[maxBase] = { 0 };
full = ((unsigned long long)1 << base) - 1;
int rc = 0; for (int i = 0; i < bmo; i++) {
sdr[i] = (i * i) % bmo; if (sdr[i] == dr) rc++; if (sdr[i] == 0) sdr[i] += bmo;
}
if (dr > 0) {
id = base; for (int i = 1; i <= dr; i++)
if (sdr[i] >= dr) if (id > sdr[i]) id = sdr[i]; id -= dr;
}
sq = to10(fixup(id)); rt = (unsigned long long)sqrt(sq) + 1; sq = rt * rt;
dn = (rt << 1) + 1; d = 1; if (base > 3 && rc > 0) {
while (sq % bmo != dr) { rt += 1; sq += dn; dn += 2; } // alligns sq to dr
inc = bmo / rc; if (inc > 1) { dn += rt * (inc - 2) - 1; d = inc * inc; }
dn += dn + d;
} d <<= 1;
do { if (allIn(sq)) break; sq += dn; dn += d; tc++; } while (true);
rt += tc * inc;
cout << setw(4) << base << setw(3) << inc << " " << setw(2)
<< (id > 0 ? chars.substr(id, 1) : " ") << setw(10) << toStr(rt) << " "
<< setw(20) << left << toStr(sq) << right << setw(12) << tc << endl;
}
 
int main() {
cout << "base inc id root sqr test count" << endl;
auto st = chrono::system_clock::now();
for (base = 2; base <= maxBase; base++) doOne();
chrono::duration<double> et = chrono::system_clock::now() - st;
cout << "\nComputation time was " << et.count() * 1000 << " milliseconds" << endl;
return 0;
}</lang>
{{out}}
<pre>base inc id root sqr test count
2 1 10 100 0
3 1 22 2101 4
4 3 33 3201 2
5 1 2 243 132304 14
6 5 523 452013 20
7 6 1431 2450361 34
8 7 3344 13675420 41
9 4 11642 136802574 289
10 3 32043 1026753849 17
11 10 111453 1240A536789 1498
12 11 3966B9 124A7B538609 6883
13 1 3 3828943 10254773CA86B9 8242
14 13 3A9DB7C 10269B8C57D3A4 1330
15 14 1012B857 102597BACE836D4 4216
16 15 404A9D9B 1025648CFEA37BD9 18457
 
Computation time was 25.9016 milliseconds</pre>
 
=={{header|C#|Csharp}}==
Line 370 ⟶ 273:
Elasped time was 20.27 minutes
</pre>
 
=={{header|C++}}==
{{trans|C#}}
A stripped down version of the C#, using unsigned longs instead of BigIntegers, and shifted bits instead of a HashSet accumulator.
<lang Cpp>#include <string>
#include <iostream>
#include <cstdlib>
#include <math.h>
#include <chrono>
#include <iomanip>
 
using namespace std;
 
const int maxBase = 16; // maximum base tabulated
int base, bmo, tc; // globals: base, base minus one, test count
const string chars = "0123456789ABCDEF"; // characters to use for the different bases
unsigned long long full; // for allIn() testing
 
// converts base 10 to string representation of the current base
string toStr(const unsigned long long ull) {
unsigned long long u = ull; string res = ""; while (u > 0) {
lldiv_t result1 = lldiv(u, base); res = chars[(int)result1.rem] + res;
u = (unsigned long long)result1.quot;
} return res;
}
 
// converts string to base 10
unsigned long long to10(string s) {
unsigned long long res = 0; for (char i : s) res = res * base + chars.find(i); return res;
}
 
// determines whether all characters are present
bool allIn(const unsigned long long ull) {
unsigned long long u, found; u = ull; found = 0; while (u > 0) {
lldiv_t result1 = lldiv(u, base); found |= (unsigned long long)1 << result1.rem;
u = result1.quot;
} return found == full;
}
 
// returns the minimum value string, optionally inserting extra digit
string fixup(int n) {
string res = chars.substr(0, base); if (n > 0) res = res.insert(n, chars.substr(n, 1));
return "10" + res.substr(2);
}
 
// perform the calculations for one base
void doOne() {
bmo = base - 1; tc = 0; unsigned long long sq, rt, dn, d;
int id = 0, dr = (base & 1) == 1 ? base >> 1 : 0, inc = 1, sdr[maxBase] = { 0 };
full = ((unsigned long long)1 << base) - 1;
int rc = 0; for (int i = 0; i < bmo; i++) {
sdr[i] = (i * i) % bmo; if (sdr[i] == dr) rc++; if (sdr[i] == 0) sdr[i] += bmo;
}
if (dr > 0) {
id = base; for (int i = 1; i <= dr; i++)
if (sdr[i] >= dr) if (id > sdr[i]) id = sdr[i]; id -= dr;
}
sq = to10(fixup(id)); rt = (unsigned long long)sqrt(sq) + 1; sq = rt * rt;
dn = (rt << 1) + 1; d = 1; if (base > 3 && rc > 0) {
while (sq % bmo != dr) { rt += 1; sq += dn; dn += 2; } // alligns sq to dr
inc = bmo / rc; if (inc > 1) { dn += rt * (inc - 2) - 1; d = inc * inc; }
dn += dn + d;
} d <<= 1;
do { if (allIn(sq)) break; sq += dn; dn += d; tc++; } while (true);
rt += tc * inc;
cout << setw(4) << base << setw(3) << inc << " " << setw(2)
<< (id > 0 ? chars.substr(id, 1) : " ") << setw(10) << toStr(rt) << " "
<< setw(20) << left << toStr(sq) << right << setw(12) << tc << endl;
}
 
int main() {
cout << "base inc id root sqr test count" << endl;
auto st = chrono::system_clock::now();
for (base = 2; base <= maxBase; base++) doOne();
chrono::duration<double> et = chrono::system_clock::now() - st;
cout << "\nComputation time was " << et.count() * 1000 << " milliseconds" << endl;
return 0;
}</lang>
{{out}}
<pre>base inc id root sqr test count
2 1 10 100 0
3 1 22 2101 4
4 3 33 3201 2
5 1 2 243 132304 14
6 5 523 452013 20
7 6 1431 2450361 34
8 7 3344 13675420 41
9 4 11642 136802574 289
10 3 32043 1026753849 17
11 10 111453 1240A536789 1498
12 11 3966B9 124A7B538609 6883
13 1 3 3828943 10254773CA86B9 8242
14 13 3A9DB7C 10269B8C57D3A4 1330
15 14 1012B857 102597BACE836D4 4216
16 15 404A9D9B 1025648CFEA37BD9 18457
 
Computation time was 25.9016 milliseconds</pre>
 
=={{header|D}}==
Line 2,409:
todigitstring(sqrtint($s), $n), todigitstring($s, $n));
}</lang>
 
=={{header|Perl 6}}==
{{works with|Rakudo|2019.03}}
As long as you have the patience, this will work for bases 2 through 36.
 
Bases 2 through 19 finish quickly, (about 10 seconds on my system), 20 takes a while, 21 is pretty fast, 22 is glacial. 23 through 26 takes several hours.
 
Use analytical start value filtering based on observations by [[User:Hout|Hout]]++
and [[User:Nigel Galloway|Nigel Galloway]]++ on the
[[Talk:First_perfect_square_in_base_N_with_N_unique_digits#Space_compression_and_proof_.3F|discussion page]].
 
[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!]
 
<lang perl6>#`[
 
Only search square numbers that have at least N digits;
smaller could not possibly match.
 
Only bother to use analytics for large N. Finesse takes longer than brute force for small N.
 
]
 
unit sub MAIN ($timer = False);
 
sub first-square (Int $n) {
my @start = flat '1', '0', (2 ..^ $n)».base: $n;
 
if $n > 10 { # analytics
my $root = digital-root( @start.join, :base($n) );
my @roots = (2..$n).map(*²).map: { digital-root($_.base($n), :base($n) ) };
if $root ∉ @roots {
my $offset = min(@roots.grep: * > $root ) - $root;
@start[1+$offset] = $offset ~ @start[1+$offset];
}
}
 
my $start = @start.join.parse-base($n).sqrt.ceiling;
my @digits = reverse (^$n)».base: $n;
my $sq;
my $now = now;
my $time = 0;
my $sr;
for $start .. * {
$sq = .²;
my $s = $sq.base($n);
my $f;
$f = 1 and last unless $s.contains: $_ for @digits;
if $timer && $n > 19 && $_ %% 1_000_000 {
$time += now - $now;
say "N $n: {$_}² = $sq <$s> : {(now - $now).round(.001)}s" ~
" : {$time.round(.001)} elapsed";
$now = now;
}
next if $f;
$sr = $_;
last
}
sprintf( "Base %2d: %13s² == %-30s", $n, $sr.base($n), $sq.base($n) ) ~
($timer ?? ($time + now - $now).round(.001) !! '');
}
 
sub digital-root ($root is copy, :$base = 10) {
$root = $root.comb.map({:36($_)}).sum.base($base) while $root.chars > 1;
$root.parse-base($base);
}
 
say "First perfect square with N unique digits in base N: ";
say .&first-square for flat
2 .. 12, # required
13 .. 16, # optional
17 .. 19, # stretch
20, # slow
21, # pretty fast
22, # very slow
23, # don't hold your breath
24, # slow but not too terrible
25, # very slow
26, # "
;</lang>
{{out}}
<pre>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 17: 423F82GA9² == 101246A89CGFB357ED
Base 18: 44B482CAD² == 10236B5F8EG4AD9CH7
Base 19: 1011B55E9A² == 10234DHBG7CI8F6A9E5
Base 20: 49DGIH5D3G² == 1024E7CDI3HB695FJA8G
Base 21: 4C9HE5FE27F² == 1023457DG9HI8J6B6KCEAF
Base 22: 4F94788GJ0F² == 102369FBGDEJ48CHI7LKA5
Base 23: 1011D3EL56MC² == 10234ACEDKG9HM8FBJIL756
Base 24: 4LJ0HDGF0HD3² == 102345B87HFECKJNIGMDLA69
Base 25: 1011E145FHGHM² == 102345DOECKJ6GFB8LIAM7NH9
Base 26: 52K8N53BDM99K² == 1023458LO6IEMKG79FPCHNJDBA</pre>
 
=={{header|Phix}}==
Line 2,896 ⟶ 2,790:
 
c. 30 seconds.</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2019.03}}
As long as you have the patience, this will work for bases 2 through 36.
 
Bases 2 through 19 finish quickly, (about 10 seconds on my system), 20 takes a while, 21 is pretty fast, 22 is glacial. 23 through 26 takes several hours.
 
Use analytical start value filtering based on observations by [[User:Hout|Hout]]++
and [[User:Nigel Galloway|Nigel Galloway]]++ on the
[[Talk:First_perfect_square_in_base_N_with_N_unique_digits#Space_compression_and_proof_.3F|discussion page]].
 
[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!]
 
<lang perl6>#`[
 
Only search square numbers that have at least N digits;
smaller could not possibly match.
 
Only bother to use analytics for large N. Finesse takes longer than brute force for small N.
 
]
 
unit sub MAIN ($timer = False);
 
sub first-square (Int $n) {
my @start = flat '1', '0', (2 ..^ $n)».base: $n;
 
if $n > 10 { # analytics
my $root = digital-root( @start.join, :base($n) );
my @roots = (2..$n).map(*²).map: { digital-root($_.base($n), :base($n) ) };
if $root ∉ @roots {
my $offset = min(@roots.grep: * > $root ) - $root;
@start[1+$offset] = $offset ~ @start[1+$offset];
}
}
 
my $start = @start.join.parse-base($n).sqrt.ceiling;
my @digits = reverse (^$n)».base: $n;
my $sq;
my $now = now;
my $time = 0;
my $sr;
for $start .. * {
$sq = .²;
my $s = $sq.base($n);
my $f;
$f = 1 and last unless $s.contains: $_ for @digits;
if $timer && $n > 19 && $_ %% 1_000_000 {
$time += now - $now;
say "N $n: {$_}² = $sq <$s> : {(now - $now).round(.001)}s" ~
" : {$time.round(.001)} elapsed";
$now = now;
}
next if $f;
$sr = $_;
last
}
sprintf( "Base %2d: %13s² == %-30s", $n, $sr.base($n), $sq.base($n) ) ~
($timer ?? ($time + now - $now).round(.001) !! '');
}
 
sub digital-root ($root is copy, :$base = 10) {
$root = $root.comb.map({:36($_)}).sum.base($base) while $root.chars > 1;
$root.parse-base($base);
}
 
say "First perfect square with N unique digits in base N: ";
say .&first-square for flat
2 .. 12, # required
13 .. 16, # optional
17 .. 19, # stretch
20, # slow
21, # pretty fast
22, # very slow
23, # don't hold your breath
24, # slow but not too terrible
25, # very slow
26, # "
;</lang>
{{out}}
<pre>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 17: 423F82GA9² == 101246A89CGFB357ED
Base 18: 44B482CAD² == 10236B5F8EG4AD9CH7
Base 19: 1011B55E9A² == 10234DHBG7CI8F6A9E5
Base 20: 49DGIH5D3G² == 1024E7CDI3HB695FJA8G
Base 21: 4C9HE5FE27F² == 1023457DG9HI8J6B6KCEAF
Base 22: 4F94788GJ0F² == 102369FBGDEJ48CHI7LKA5
Base 23: 1011D3EL56MC² == 10234ACEDKG9HM8FBJIL756
Base 24: 4LJ0HDGF0HD3² == 102345B87HFECKJNIGMDLA69
Base 25: 1011E145FHGHM² == 102345DOECKJ6GFB8LIAM7NH9
Base 26: 52K8N53BDM99K² == 1023458LO6IEMKG79FPCHNJDBA</pre>
 
=={{header|REXX}}==
Line 3,033 ⟶ 3,034:
Base 16: 404a9d9b² = 1025648cfea37bd9
</pre>
 
=={{header|Sidef}}==
<lang ruby>func first_square(b) {
Thundergnat
10,333

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/290653"