Talk:First perfect square in base n with n unique digits: Difference between revisions
Talk:First perfect square in base n with n unique digits (view source)
Revision as of 15:03, 25 May 2019
, 4 years ago→analytically determine minimum start value: new section
(→Space compression and proof ?: Why 10123456789abcdefg is the smallest candidate) |
Thundergnat (talk | contribs) (→analytically determine minimum start value: new section) |
||
Line 183:
::: Nigel, how would you formulate cases like base 12 and 14 in terms of quadratic residues ? The repeated digit sums of the first all-digit perfect squares seen for 12 and 14 are 'b' and 'd' respectively, corresponding to x^2 mod (N-1) == 0. Am I right in thinking that the 0 case is not usually treated as a member of the set of residuals ? Presumably we need to tack it on to our working lists of residuals here ... [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 12:01, 24 May 2019 (UTC)
:::: Scratch that – I see that you are already including such cases above in ''residuals base 16 -> 1 4 9 16'' [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 12:18, 24 May 2019 (UTC)
== analytically determine minimum start value ==
As a hint to other entry authors: here is how to easily determine a minimum star value analytically. This will work correctly for any base up to 36, but is kind of pointless below base 10 as brute force is probably faster than doing the calculation.
Note: I would not have figure this out without the above analysis by Hout and Nigel Galloway. Kudos to both of them.
Here is a Perl 6 script showing each step spelled out: [https://tio.run/##fVO9btswEN79FBdDqGXXIqIUSFAbcYqiS4dORae6CSj7ZLOQSJWUmhiG8lBdu@XF3KMoypYDlINEUXf3/dyxQJ1dHw6mSmAtNqLkWaSVKiEMmpcwsFLFbgqzIOEGx7AfAC3389a92UrlCct5Ee5n767D4GFcj5mpcmYzwjbvcSsy9PFbrg0sIJ4fi7GCzjA6SZkP6sHA8kqFNmVkflVcI4SfZQmB9EQM38FoMoInuHk/706GH6kARUEUwTeDBsotQqGMEQmRaHSa2fAYn@/ggym5tpLSjJcwikdTGF3SI7wCxu4t4svfVpAkakeopfzkfIPGE5USmDIdCgynTSxBONMI4tToEML7fnH2UwlJhvtv@A@ccXjoPLKKZZUnSO4KCYkz4Vyoy7slZYxZONu4ycufZjODfZ9d8NDx6lGCuk/qi5Air3JKTlPUKFdome0DWUdNPWdOqlUOSuIr1uuepoWzyhO31qk0NWjbkwsZOglso5EIT3w4kYrcrqVWaGFnpUv1u4VFvLuDS7i48IfnrRVpF@4GrdMKEO4blLdtQO1hjxDjpVzKr2oKNErcUrbeTBvJJudZhqS6mTchN/CbZxXCo8gykIhr4BLwqdTcF2tdsMsN6ffYQ/84UfX8@q9LrAEzGoQzGY4hSNWCuXEFs1VVtoYEicsKjeF6x1oC9UnDfbvdpWkU2ElvKTQTTEZSBnvTu72p0hDf0I2Cq3h@OPwD Try it online!]
<pre>sub digital-root ($root is copy, :$base) {
$root = $root.comb.map({:36($_)}).sum.base($base) while $root.chars > 1;
$root.parse-base($base);
}
sub first-square (Int $n) {
say '*' x 79;
say "Base $n -- Uses the possible digits:";
say my @start = flat '1', '0', (2 ..^ $n)».base($n);
say "\nDigital root of those digits: ",
my $root = digital-root( (^$n)».base($n).join, :base($n) );
say "\nDigital roots of the first $n numbers in base $n:";
say my @roots = (2..$n).map(*²).map: { digital-root($_.base($n), :base($n) ) };
say "\nMinimum difference of {$n}-digit root from one of the first $n digital roots > $root:";
my $offset = min(@roots.grep: * > $root ) - $root;
print $offset = $offset > $n ?? 0 !! $offset.base($n);
if $offset {
say " ({$root+$offset} - $root = $offset)\n\nSo, at a minimum, the smallest starting value will need an extra $offset";
@start[1+$offset] = $offset ~ @start[1+$offset];
} else {
say "\n\nSo no extra digits should be necessary.";
}
say "Minimum start value: ", @start.join;
}
.&first-square for 17 .. 21;</pre>
Which outputs:
<pre>*******************************************************************************
Base 17 -- Uses the possible digits:
[1 0 2 3 4 5 6 7 8 9 A B C D E F G]
Digital root of those digits: 8
Digital roots of the first 17 numbers in base 17:
[4 9 16 9 4 1 16 1 4 9 16 9 4 1 16 1]
Minimum difference of 17-digit root from one of the first 17 digital roots > 8:
1 (9 - 8 = 1)
So, at a minimum, the smallest starting value will need an extra 1
Minimum start value: 10123456789ABCDEFG
*******************************************************************************
Base 18 -- Uses the possible digits:
[1 0 2 3 4 5 6 7 8 9 A B C D E F G H]
Digital root of those digits: 17
Digital roots of the first 18 numbers in base 18:
[4 9 16 8 2 15 13 13 15 2 8 16 9 4 1 17 1]
Minimum difference of 18-digit root from one of the first 18 digital roots > 17:
0
So no extra digits should be necessary.
Minimum start value: 1023456789ABCDEFGH
*******************************************************************************
Base 19 -- Uses the possible digits:
[1 0 2 3 4 5 6 7 8 9 A B C D E F G H I]
Digital root of those digits: 9
Digital roots of the first 19 numbers in base 19:
[4 9 16 7 18 13 10 9 10 13 18 7 16 9 4 1 18 1]
Minimum difference of 19-digit root from one of the first 19 digital roots > 9:
1 (10 - 9 = 1)
So, at a minimum, the smallest starting value will need an extra 1
Minimum start value: 10123456789ABCDEFGHI
*******************************************************************************
Base 20 -- Uses the possible digits:
[1 0 2 3 4 5 6 7 8 9 A B C D E F G H I J]
Digital root of those digits: 19
Digital roots of the first 20 numbers in base 20:
[4 9 16 6 17 11 7 5 5 7 11 17 6 16 9 4 1 19 1]
Minimum difference of 20-digit root from one of the first 20 digital roots > 19:
0
So no extra digits should be necessary.
Minimum start value: 1023456789ABCDEFGHIJ
*******************************************************************************
Base 21 -- Uses the possible digits:
[1 0 2 3 4 5 6 7 8 9 A B C D E F G H I J K]
Digital root of those digits: 10
Digital roots of the first 21 numbers in base 21:
[4 9 16 5 16 9 4 1 20 1 4 9 16 5 16 9 4 1 20 1]
Minimum difference of 21-digit root from one of the first 21 digital roots > 10:
6 (16 - 10 = 6)
So, at a minimum, the smallest starting value will need an extra 6
Minimum start value: 10234566789ABCDEFGHIJK</pre>
| |||