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 13:35, 7 November 2020
, 3 years agoThundergnat moved page Talk:First perfect square in base N with N unique digits to Talk:First perfect square in base n with n unique digits: Follow normal task title capitalization policy
Thundergnat (talk | contribs) m (Thundergnat moved page Talk:First perfect square in base N with N unique digits to Talk:First perfect square in base n with n unique digits: Follow normal task title capitalization policy) |
|||
| (44 intermediate revisions by 7 users not shown) | |||
Line 1:
==Incorrect Example==
Base 3 : Num 11 sqr 121
--LambertDW 18:28, 2 March 2020 (UTC)
Hmm. I am the original task author, but that list was added by someone else well after the task was written. You are correct though, that is wrong. --[[User:Thundergnat|Thundergnat]] ([[User talk:Thundergnat|talk]]) 23:19, 2 March 2020 (UTC)
==Leading zeros ?==
Line 57 ⟶ 63:
Obviously 2n+1 -> 2(n+1)+1 = (2n+1)+2<BR>
Its a pitty that "carry := 0;if num >= base then num := num-base;Carry=1; " are not optimized to cmove in freepascal, like C or freebasic do.
But the addition has mainly
I hardcoded startvalues for base 22 ( glaciel ) that runs in <b>35.529s</b> on TryItOnline
<pre>
start value first
sqrnum above 1023456789ABCDEFGHIJKL
start value 1023456789AF71694A3533 // 15588232346256352156349976289dec
N = sqrt(startvalue) 4F942523JK5 //124852842764017dec
results in
n = 4F94788GJ0F //124.853.426.667.963dec
-> sqr ->
102369FBGDEJ48CHI7LKA5 //15588378150732414428650569369dec
26.508s</pre>
It takes 583.903.946 long and short additions
: speed up adding in base < 127 < 256 Div 2 by using Uin64 to pack 8 digits.By offsetting every digit of the sum by 256-base=$FF-base one gets an natural carry into the next digit.
:example: base = 10 89 -> $0809 offset every digit by $F6 ( the new $00 ) -> $FEFF and add 1 = $0002
<pre>
$FEFF
+$0002
$FF01 </pre>
:Now check which digit overflows.If one digit overflows, its highest bit is not set anymore, so the digit 0 aka $F6 must be added
<pre>
$FF01 ( pre-result )
XOR $8080 (= Overflow-MASK )
= $0080 ( now shr by 7 Bits )
= $0001 ( Multiply by $F6 -> zero Offset )
* $F6 ( = zero offset mask )
= $00F6
+ $FF01 (now ADD pre-result )
= $FFF7 ( if one like convert back subtract "zero"
- $F6F6
= $0901 -> 91</pre>
: it speeds up additions by a factor of 3, but checking the used digits takes ~ 40% of runtime - 60%/3+40% = 60%
:: think of base 10 and the square of the last 2-digits. of a number.If the last 2 digits of the square are the same you need not to test the complete number.
<pre> 0 10 12 20 30 38 40 50 60 62 70 80 88 90
86 of 100 are left over not that impressive</pre>
::using more digits increases the proportion even more 4 digits -> 4660 of 10000 are left over to test.
::but 4 digits to base 37 lead to 1542240 of 1874161 need to be checked.Not that useful.
==Space compression and proof ?==
Line 168 ⟶ 212:
Base 17: 423F82GA9² == 101246A89CGFB357ED
:::The residuals base 16 are 1 4 9 16<br>0+1+...+15+16 -> 80 -> 8 therefore no 17 digit perfect square made from digits 0..g in base 17 so searching for one is pointless.<br>101246A89CGFB357ED -> 81 -> 9 therefore may be a perfect square, just as well since you say it is.<br>smallest possible number made repeating 1 is 10123456789abcdefg so you only need to verify that there is no perfect square between 10123456789abcdefg and 101246A89CGFB357ED which contains all the digits between 0 and g to prove that 101246A89CGFB357ED is the smallest.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 10:07, 24 May 2019 (UTC)
::::Note that adding a zero to a number doesn't change it's digital root so the repeated digit can not be zero so 10123456789abcdefg must be the smallest candidate--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 12:45, 25 May 2019 (UTC)
::::: Many thanks for confirming that Nigel. I had in fact realized it was true when submitting my original Go entry but omitted to explain the reasoning and so, as Thundergnat rightly pointed out, it looked like I was using a 'magic number'. You're also right that it's not really acceptable to assume an extra digit for bases 13 and 17 without further explanation so in my latest Go submission I'm justifying this from first principles. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 17:08, 25 May 2019 (UTC)
:::So digital root 9, I think, drawn from the dual-symmetry base 17 cycle for perfect squares of
::: <pre> [ '1', 'g', '1', '4', '9', 'g', '9', '4', '1', 'g', '1']</pre>
::: base 13 (digital root 1 for the first match), also has a dual-symmetry cycle.
::: Conceivable that there is some kind of congruence there ?:
<pre>
# '1', 'g', '1', '4', '9', 'g', '9', '4', '1', 'g', '1' base 17 (digital root 9 for that candidate)
Line 178 ⟶ 225:
# '4', '9', '4', '1', 'c', '1', '4', '9', '4' base 13 (digital root 1 for the first match found)</pre>
::: [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 23:59, 23 May 2019 (UTC)
::: 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 start 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 figured 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/##fVNNb9owGL7zK56iaARGoqaTWg1UOk277LDTtNNYKwfegKfEzuxkLULpj9p1t/4xZsdJIFRaDsQ47/s@H36ck0qvDwddxljzDS9YGigpC/he/eIaK5nvpph5MdM0xn4A87iPt@4drmQWhxnL/f3s3bXvPYyrcajLLLQdftP3uOUptfVbpjQWiObHYWFu9ig4aZkPqsHA8kq40kWgf5VMEfzPooAnWiKa7TCajPCEm/fzbmf40QwwVQgCfNOkUWwJudSax4ZErVPPhsf6bIcPumDKSkpSVmAUjaYYXZof/wpheG8RX/42goShdoRaik/ON9SeyMSASd2hYDitaw2EM81AnBrtw7/vDw9/Si6M4e1//AdOOzxyHlnFosxiMu5ygdiZcC7U9d3Cj4wwi2dPbvLyp17MsO/T8x46Yj1OqPqsvnDBszIzzUlCisSKLLW9J6qgnufcSZTMIAW9or3uiVo0yWqpW/NkkmiyB5Rx4TsR4UaRYTzp6g2twK0acrniNi5db7taWMy7O1zi4qLdPD9dnpyUXzZ56xQD/r5GetsUVS30EWa8FEvxVU5hEsUsb@vQtBauM5amZLTXseNig98sLQmPPE0hiNZgAvRUKNYOa6ywj8vq96iF/nGi7Pn1V9dYgVKThzMZjiGEbMBcaqG3skzXiMlwWZHWTO3ChkB1cuztobu7UyuwgW8o1EE2ZpqO8E3vEidSIboxFwtX0fxw@Ac 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 = (1..^$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 > 0 {
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:
[1 4 9 16 9 4 1 16 1 4 9 16 9 4 1 16]
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:
[1 4 9 16 8 2 15 13 13 15 2 8 16 9 4 1 17]
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:
[1 4 9 16 7 18 13 10 9 10 13 18 7 16 9 4 1 18]
Minimum difference of 19-digit root from one of the first 19 digital roots >= 9:
0
So no extra digits should be necessary.
Minimum start value: 1023456789ABCDEFGHI
*******************************************************************************
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:
[1 4 9 16 6 17 11 7 5 5 7 11 17 6 16 9 4 1 19]
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:
[1 4 9 16 5 16 9 4 1 20 1 4 9 16 5 16 9 4 1 20]
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>
I've just tried to run a variation of my Go program using this approach up to base 21. However, I'm getting a lower value than your Perl 6 program for base 21 itself even though I'm starting from 10234566789ABCDEFGHIJK as you are, viz:
Base 21: 4C9HE5FE27F² == 1023457DG9HI8J6B6KCEAF
compared to your:
Base 21: 4C9HE8175DA² == 1023467JKAIEHB5DF9A8CG
Unless there's something wrong with Go's big.Int routines, both numbers check out as perfect squares when I convert them to decimal so I'm at a loss to explain the difference. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 00:20, 26 May 2019 (UTC)
:Well, I think the simple explanation is that I screwed something up. When I run it again, I get the same thing you got, so I'm not sure where that came from. I must have saved a result from an interim version where I was still working out bugs and never went back and reverified it; which is pretty sad since 21 actually finishes very quickly. At any rate, you are correct, I have the wrong answer for base 21 right now. Fixing. --[[User:Thundergnat|Thundergnat]] ([[User talk:Thundergnat|talk]]) 02:32, 26 May 2019 (UTC)
I've run it through to base 25 now and found another anomaly at that point where, although we agree on N², we disagree on N where I have 1011E145FHGHM but you have 1011E145FHGI3.
This has certainly been an interesting task which has taught me a lot so thankyou for thinking it up in the first place.
I don't know whether any substantial optimizations are still possible, though I'm continuing to think about it as it would be nice to get the run time down for the higher bases. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 15:42, 26 May 2019 (UTC)
:Argh. Made faulty assumptions about how square root of big integers are handled in Perl 6. It was only in the display code, not the calculations, so I got the right ''square'' but then displayed an incorrect square root. Will fix that. Thanks.
:This turned out to be a more interesting task than I initially anticipated. I learned quite a bit more about number theory than I knew before. We have an interesting cross-section of talented people on here. --[[User:Thundergnat|Thundergnat]] ([[User talk:Thundergnat|talk]]) 16:41, 26 May 2019 (UTC)
==Calculating quadratic residues==
The valid digital roots can be calculated using the following code in F#:
<lang Fsharp>
let rSet g=set[for n in [0..g-1] do yield n*n%g]
</lang>
rSet 20 -> set [0; 1; 4; 5; 9; 16]. Remember that this is base 20 and 0 corresponds to 20.<br>Similar code in Python is:
<lang Python>
rSet=lambda g: {n*n%g for n in range(1,g)}
</lang>
rSet(20) -> {0, 1, 4, 5, 9, 16}<br>--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 17:02, 25 May 2019 (UTC)
==Trailing zero==
A minor optimization has occurred to me namely that N cannot end with '0', for any base greater than 2, because if it did, then N² would end with '00'.
However, this is impossible because:
* if N² has 'base' digits, it can't then be pandigital; or
* if N² has 'base+1' digits then the repeated digit would be zero and so the digital root would be unchanged.
<br>
As checking for this is very cheap, it may knock about 4 or 5% from the run time for bases >= 20.
--[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 16:27, 27 May 2019 (UTC)
==Optimization when no extra digit required==
Let me do this in base 10 to maintain sanity. As discussed (Space compression and proof) the Digital Root n Base10 for n from 1 to 20 gives 1 4 9 7 7 9 4 1 9 1 4 9 7 7 9 4 1 9 1 4. Digital Root 1023456789 Base10 is 9. So every third square is a possible solution. As discussed (analytically determine minimum start value) start from 31992**2. First find the first value whose Digital Root Base10 is 9. In this case it is 31992. It should then only be necessary to try every third value to find the solution.<br><pre>
> [31992..3..999999] |> List.map(fun n->n*n) |> List.find(fun n->n=1026753849);;
Real: 00:00:00.068, CPU: 00:00:00.110, GC gen0: 5, gen1: 1
val it : int = 1026753849
> [31992..999999] |> List.map(fun n->n*n) |> List.find(fun n->n=1026753849);;
Real: 00:00:00.204, CPU: 00:00:00.300, GC gen0: 14, gen1: 2
val it : int = 1026753849
</pre><br>which seems to save the expected two thirds time. This is a little trickier when an extra digit is required because you would have to check each extra digit separately (they would have different Digital Roots).<br>The sequence 1 4 9 7 7 9 4 1 9 1 4 9 7 7 9 4 1 9 1 4 can be produced as (n*n)%9 -> 1 4 0 7 7 0 4 1 0 1 4 0 7 7 0 4 1 0 1 4 for n = 1 to 10 with the usual 0 means 9.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 22:03, 27 May 2019 (UTC)
: //after watering the garden <br>
the digital root of the square of start value n ( pandigital:all digits of [0..Base-1] ) is for even numbers always Base-1.<BR>
base 10: 0123456789 -> 09 18 27 36 45 -> 0 -> 9 <BR>
For odd numbers Base % 2 ( casting out 9 aka Base-1 the Base % 2 is left over)<BR>
base 9: 012345678 -> 08 17 26 35 4 -> 4 <BR>
Now you only use such n , that there dgt-root**2 is the dgt-root of a pandigital number. Aha!<br>
for base 9: dgt root of the square [0..8] = 0 1 4 1 0 1 4 1 0 .. 1 4 1 0 <br>
So you only use numbers with digit root 2 and 6<br><br>
Now base 15: dgt-root of pandigital value ist 7<br>
dgt root of the square: 0 1 4 9 2 11 8 7 8 11 2 9 4 1 .. 0<br>
So one has only to check every 14.th value.<b>Bravo</b>!<br>
:Simple but brilliant, Nigel :)
:Even on my old machine, this has cut the time needed (in Go) to reach base 25 from 60 to under 4 minutes and bases 26 and 27 are now dispatched in under 16 and 30 minutes respectively.
:I wouldn't spend too much time on optimizing for the cases where an additional digit is required as they take very little time to process anyway as a result of previous optimizations. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 10:58, 29 May 2019 (UTC)
::@PureFox your calculation of digital root is to much work [[wp:Digital_root#Congruence_formula|Digital_root]] is only one ( n MOD (Base-1) ) calculation.All numbers are >> 1 no need to check for one digit.Similary to this<lang go>func sumDigits(n, base *big.Int) *big.Int {
r := new(big.Int)
// decrement base by one ?
r := Rem(n,base-1)
return r
}</lang>
:::Thanks for pointing out that I could use the congruence formula to simplify (and possibly quicken up) the calculation of the digital root which is used to help establish the optimum starting value for each base. Unfortunately, I haven't been able to use it as I wasn't able to obtain consistently faster times than before. Although it was marginally faster up to base 25, it then started to diverge and by the time base 28 was reached it was 48 seconds slower than before. This may be due to the vagaries of big.Int arithmetic in Go but thanks anyway for continuing to think about this task which has been a real team effort :) --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 19:50, 2 June 2019 (UTC)
==Minimum start for Pascal version==
I spotted a bug in the output of the extended Pascal version, for the value of base 17. The values should be
<pre>423F82GA9 101246A89CGFB357ED</pre> rather than <pre>4261CBG65 102369EB54FD9G7CA8
</pre>Looking into the code, it seems that although it correctly identifies which bases need an extra digit, the current Pascal code always adds a zero to the end. That is, it multiplies the minimum start value by the base. What other implementations do is to identify what digit should be added, and the location in the minimum start value where that digit should be added. I've made a [https://tio.run/##3Vl7b9tGEv@fn2KQK2DSoR6UXLeVYgO2Zbe6JlIuVuPeBYFBkStpbYqUuUu7TpGvXnf2RXIl2XHuUKA4wbbI3ZnZef52dp1Nr0jEG6uQRWHSmK2ih4dVns3zcAn4LeaCvtNqndE0Br4gwJZhkhDGIS2WU5JDCjyDacgITH1gGdKEOLebAk2jpIgJA6RHATGdU84gm2liCK9DWIWpHA8T5/dvhmeD0zM4e3vy2QH4/Zs348EpDE5fv/1pqAbGK06Xy08hp1kK49FnZDkdDYZnn52CEYYk7J4VnCbMx@f5ctVvtYRuaFZUJCFH1XmYc7gNkwLJnShLGUfKaBHm54RDD8I8D@8/tJvN/c5HoaiYgYOddtDp7n27/933Pxwdn6CKP/40/OfPr9@Mxm//9e588sv7i1///Z9wGsVkNl/Qq@tkmWarm5zx4vbut/tPO33H4fcrgivxUbHk2bEw/wByEmV5jKNrn5RPL@O5rU63sScVmt5z0t/OEqXc3z6D7gaUdoGrbfCSVI7xwZy/yzJ@fpM/oRnEObt8TdlX6SaZtApPkZxnyTNITlLee4pkREjMxil5k@VkIBILJWZZQsJ0k0Pa7tyGOebR0evhjyPodkSiYZCEJ9lN3jkWDzFJeKgH5bPQswplf41duFI6UlBVfl0nm7T9SdCDyQATc0KXKMbBcotIXOQExoWQ78oMFXXWq5bz@lJlAIryR1gLt2SY8r5zTOY0xeE7yheCBeIM38wowFmWC5YD6LYbOl8aARLdpVgibUUtPnc55cTdgR2vb/N9mUkX0gedwR/ox49SiE6yumTl@1mRRrKY50R66nGjezVLt5o//YL5OWFFwoUd7TW72gIjkKNZN1DbhRDmKk6/Mko7ppKonxCvXF1vjaAyXJlaxfYE4ahKC1eAYWXds6JbZpjUc1ra2GopOEU0BY2qkOMy4DJ0CKIw2BjswTKLQWqACjv1YkWrpjK3pRdmMI5jV7HgFpA6dtlqYpR@Cx05RxJGNonQ83JQEuP7sVy4r3UXMA13CxotQMCfVFzuNzdFiG5DncWb3nTuKFozRZxaki3RVBZVYTS4hcETNC7dpZ4IV83GVouRMI8WBU3nwmCWJYVITccGn0cTaH3J4cxa9aD0Q81/Kr8q4Z5RBddP0fpZVqg9N4UNXHMeRTyhUk1hrW@VilUmYqXdXhb0En1aT8NfKGZcQXvie3@vj/koIPErIMj2zILOF27F3NSF5BlfjXTpqeIqHWwXcpXkZkezMlSXbi066MKCglShcvjpr8OJnq6R5mRFQu5Yu6/WBEW8wRKpFgIxpCYGw/fWhIgl1SEsUmxDtAIbGtKn4tEZbQnGZgjkEOstV58u@d8vHM/0rtQeQePyBrPQZT7zpyq7HnOoYIiWK0UNbW/DvZverbn3XHR/70Xzd5KjSsRys8JeRCE5JaEmye5Em1u1qAZ8XgRt0RA2m02FYPACGWWbKZoGDi8DQB4ZToKvKaTkDos5X4a8qUPFbi@RVLYZtz3lCKH3dQ901Tll@LbsF54EUsFFU8pddiu9VHsXwm2iS0bwl@o5X@E/NshoywskG54pVD6EjimYau@8FsHqbAmnEL4sEhkPLdeWbyI5A/cag9XxpGOkDfgafKfezX7W3I5nFmI@d0lBF8bxNrprK8OurQy7Plzb@J6vG9UHm1eHaJhC7ecoq7JUKSyyBykNVRnV0hAff4JyGEXX5PoyDRy59ShF9rtGv6peLYzxRVers2d9SrW/NUXqikbYUefumpZm0NssvWEaoeBjOncFbqE5QR3LUr3VVEAmoMCP8Ixxvx3SpiIjhZimxp@@U0cdzWmga0ETbBwwt9vrXSGz5Chkeim5XyKD7BC0b4zEcR677PBgqn0mBbAGuA1FcTRCFj23JldSarSS/bTsl7T8CuuMm5XWSuqrr1L9r9B4Uz9EjJJcbGyv0P9lNVgzCpS3p8TWfJCKWT0xdrY5yclNQRmeIZhxi8zzes78V9nyt/b0/@7ooziuO9rHPx27mWu1xAS8Ula@FASbLheuZiA6cdmUh0siJAWHB4LcBbG@55exkBZ/ZUTsqrW7FrHI@gFt@nSESpa/NmKmHqjWoVRzPbVwv/t/q@EJ9kePHWDlTYk8MZUtjUiMK18wqeu2bedbeUcgRXalqpO2xMrsTrxs7eAkmbmjkcTFUgzpvC9vb8yDpNfoU04GlRR9ygt07alm5bALnnSzazUE@ox1KHrRjbZJ35nOaF5dlqrzbRTKKw9VSfWDpuyyMXA5Z@Z4L4dlGpXnyfptCcr1PgrYktMorOKqNJEHUmVxWhqrPtpLare3XGSxlY7qlHMmiWy3uaol9uTxaIuvzBH3ahc1qbjt0NWqvyOqv1ygtG09uGmp9JNhh1onYlOg9F3zUEff9TOy39ndoFcSvPodFxcnB4Lt/z3s@Jbcat@ptdJ47sCzPoeCkVhf0sjxslasW4crWdQiYs2nLuVqzOZx/A7cANgiqbELnLgyl1oCIzSxcdiZYZHFdmBEWW358bvTo59NaFPyGze3NirtnS9l2tageTZs4RFLqUNVIYLSqrMHDQi88qhvYkD9fwQKQlRnPwsT1dZXGSBqgdpRnwQ1uLkQgpLUdSdBg7fB2/1@f6/d7v3Q6/o7wNQFqb6pNaboV2lklRBJarBTYePEuvc1F2LplttMrcGOpNi43DcPytlu6kEVecwKpeGkZpHIHnP7Jiur863JlxLL62q7LjI2JsbyoK1MJ1gVsXaA@bfNxXA0GF@cf0ZgjtHe8l8zaHfz4eGPaJaEc/bQGHf/BA Try It Online! link ] with a kludgy fix. It is hard-coded to stop at base 25, as one only gets 60 seconds to execute there.--[[User:Enter your username|Enter your username]] ([[User talk:Enter your username|talk]]) 20:06, 6 June 2019 (UTC)
:thanks for the "fix"
<lang pascal> if DgtRtSqr.drs_NeedsOneMoreDigit then
if base <> 17 then mpz_mul_ui(sv_sqr, sv_sqr, base);</lang>
:I try to update the procedure StartValueCreate.
:I first had to change the TestSet .Even 64 bit-freepascal 1 shl x is done in 32 Bit, so i got no solution running 1e12 Tests for base=32 upwards.Nggggrrrrrr ( Rumpelstiltskin , i have to put me togehther )
::Looking at the revised Pascal code, it seems that the inserted digits are not being calculated correctly for some bases (such as base 17 and base 29). Here is some commented demo code written in Pascal that demonstrates a way to generate the correct information. (and a [https://tio.run/##hVRbdxo3EH7nV8xDzgGaNQbHcVsoPif1JaF1wLWT3nz8IFYCFGuljaQF49S/3R2NdmGJc9oXexnNfPPNN5ecuZSpvVmePj3t7wMXmXEgtRPWCw5czqV34A1kUsusyGDJVCE6nU4jt2ZuWQb4/5NIfW/Q@PJidH56dg7nlyePDYAvL95PTs/g9Ozi8t0oGia5l5l8YF4aDZNxNJ6g15uL0dtxgEqHh4kyJh8ePiLe2fh0dP7YKJxw6Hq9dh@9VG7QSI12Hi0Zu@/DGOGWYqQ9DOEIaQCkC2ZdH5y3Us/R2uz2Dl4dvj76/ocf3/x8ghTfvhv98uvF@/Hk8rer6w8ff//jz7/@ZtOUi9l8IT/dqUyb/LN1vliu7tcP/zQHjSWzCDxlTtQSDhpoA0DZrPCF1SjUQkTNmAJrjAczA51A4QKRtLBWIM2AQoGzQqckBb9q6RpueydH8JyKudT0BZjLFcpDfwjdAUjExwq7IbMGcS/LgLqbBmwEtEJa2INem6LK503o1r3yi0BC8@dlskpbv2AepyVVBRex@t3R@f/SZ1Kpkf66/Aj/X7Vfk8eVyBVLRevE5OsWtT2BXkJp2gkg1geDji1NdT8zwMuaBZ9vbtvP1SPUm4NbdI6fvfBJCaNTAq/KjDXFoJwYx20fmLVsfdPtdI4wFidi21xSFX2QjvtcMLs7PVjMUQ9bhGOOUBKzcJsA4/XxCABTAqC@1cODK9oZ51U7GpWWGGS0WmMjZ2IFhnOKdpAVzsOCLUW1@TEY9z/0ducGlOsQJHo9gNVCKhENPxFh4KbWOcwnljhlMQs3uulBC0SukcNqd4oPSm2ZBW2YWrG1Q0G2swz7cBCnBDXYrMSEc3Jpx9ku3yjILWw12kgqY3cIC0o6WtWv19dVxpnEa0BaxTa5OMTGggzIvaBQyIJFYzdvZOB2G15wsyV8B7K9SYkaesmUfBCQG@fkFHWrqUCgldB4mdNC0blMYinpQqR3dZ/IBBtdFjjYsupWrJBMYIbCELlbOB6SnRDRitHH1RPZIly0bIgHHcq1kHHXXcaUEigMDQTMrWBeBFim6f0bE4msixiMBAj5VKQtxmm2tyKNZvV0@N4OOR@ENaUOz09NcCi0Fqlwjtk1IVW1lTduZaUXStNo9A8SaPahSfsUvmHvOPwq7xFm3LJxdzLfFOTi0Vt9e4YpZKRTypHAIYHQRcA/naenfwE Try It Online! link])--[[User:Enter your username|Enter your username]] ([[User talk:Enter your username|talk]]) 19:36, 7 June 2019 (UTC)
<lang pascal>// demos inserted digits to minimum value...
program project1;
{$IFDEF FPC}
{$MODE DELPHI}
{$Optimization ON}
{$CODEALIGN proc=4,loop=4}
{$ENDIF}
uses
SysUtils;
const
max: NativeInt = 61;
chars: string = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz|';
var
base: NativeInt;
// returns the digital root of n, using current base
function dR(n: NativeInt): NativeInt;
begin
result := 0; if n = 0 then exit;
result := n MOD (base - 1); if result = 0 then result := base - 1;
end;
// returns a string that includes the inserted digit, using current base
function fillIn(n: NativeInt): string;
begin
result := StringReplace(Copy(chars, 1, base), IntToStr(n - 1), IntToStr(n - 1) + IntToStr(n), []);
result := chars[2] + chars[1] + Copy(result, 3, base);
end;
var
sdr: array[0..61] of NativeInt; // sdr - square digital roots, 61 = max
i, bdr, ad: NativeInt; // bdr - base digital root, ad - added digit
begin
// only a few odd bases must have digits added to the minimum value
base := 5; while base <= max do begin
// even bases don't need added digits, digital roots of odd bases are always = (base - 1) / 2
bdr := 0; if Odd(base) then bdr := base shr 1;
// make a list of the digital roots of the first few squares
for i := 1 to bdr do sdr[i - 1] := dR(i * i);
// initialize possible added digit for minimum calculation, then check for minimums
ad := base; for i := 0 to bdr - 1 do if sdr[i] >= bdr then if ad > sdr[i] then ad := sdr[i];
// the result is the smallest value greater than the base digital root, minus the bdr
Dec(ad, bdr);
// If the result (ad) is zero, then the inserted digit is unnecessary
if ad > 0 then writeln(base:2, ': ', ad:2, ' -> ', fillIn(ad));
// skip the bases that won't need added digits
Inc(base, 4);
end;
end.</lang>
{{out}}
<pre> 5: 2 -> 102234
13: 3 -> 10233456789ABC
17: 1 -> 10123456789ABCDEFG
21: 6 -> 10234566789ABCDEFGHIJK
29: 2 -> 10223456789ABCDEFGHIJKLMNOPQRS
37: 7 -> 10234567789ABCDEFGHIJKLMNOPQRSTUVWXYZa
45: 3 -> 10233456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghi
49: 1 -> 10123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklm
53: 3 -> 10233456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopq
61: 6 -> 10234566789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxy</pre>
::: try to fix it, when the still running even numbers finished. I don't think to let 37 start.
:::: I've been trying to verify the larger results produced by the Pascal program. I have verified the results as proper ''root,square'' pairs, except for 29 and 34.<br/><br/>On base 29, the figures verify as pandigital, but the value seems like it could be lower. It seems to me that the square could start with 102234... or higher, and not 102345677... or higher.<br/><br/>I was unable to verify pandigital results:<pre>BB6GLLFX5V75RA3RRL 102345679JICE8KP5LXA8L3QUPUWFPE4P</pre> for Base 34, as there are a number of duplicated digits in the square. But by considering the ''testcount'' value, I came up with the following result: <pre>5SEMXRII42NG8AKSL 102345679JIESRPA8BLCVKDNMHUFTGOQWX</pre>which has only one of every digit. Or, the actual minimum square for base 34 is a lower number. Perhaps a "copy paste" error caused this discrepancy on base 34?--[[User:Enter your username|Enter your username]] ([[User talk:Enter your username|talk]]) 23:59, 9 June 2019 (UTC)
::::: Still a work in progress.base 34 was a copy and paste failure<pre>Testcount : 205094427126 5SEMXRII42NG8AKSL 102345679JIESRPA8BLCVKDNMHUFTGOQWX 28900.032 seconds</pre> i have changed the program and checked, if the last digit of the number squared leads to the last digit of the squared number, and it does so <lang pascal> //check last digit sqr(num) mod base must be last digit of sqrnumber
if (sqr(Num.ntb_dgt[0]) mod Num.ntb_bas) <> sqr2B.ntb_dgt[0] then</lang>i stopped Base 36 at <pre>3,044,863 Mio tests about 1.1 e12 / day</pre> i will try to use multithreading. Instead of checking every 35 n-threads check every n*35, but using different start values.Tread 0 at normal , thread 1 at normal + 35 .. thread n-1 at normal + (n-1)*35
==Finding maximal distances to check if number needs extra digit==
<pre>insert 2
Base 29 test every 1
Start : Num 5BAEFC5QHESPCLA sqr 10223456789ABCDKM4JI4S470KCSHD
Result : Num 5BAEFC62RGS0KJF sqr 102234586REOSIGJD9PCF7HBLKANQM
4921.784 s Testcount : 92238034003
</pre>
The runtime is really slow by checking every number.I try to find the distances.
I checked all solutions for the possibly inserted digits.This makes only sense, if the inserted digit ist "small" , so that one will find a solution, before this inserted digit is reached by sqr(num)
<pre>
Base 17 -> base-1 = 16 -> (base-1) / 2 = 8
insert 1 this is the relevant digit -> smallest startvalue.
dgt/count: digital roots of 3,5,11,13 lead to possible solution
1 4 : 3 5 11 13 //distances = +2 = diff1 =(8-2*k) +6= (8-diff1)
0+3,8-3,8+3,16-3, 16+3,24-3, n*((Base-1)/2) +/- k (= first found value ) k = 3
8 4 : 4 8 12 16 //distances = +4 +4 +4 +4
0+4,8-4,8+4,16-4, 16+4,24-4,
9 4 : 1 7 9 15 //distances = +6 +2 +6 +2
0+1,8-1,8+1,16-1, 16+1,24-1,
Base 21 -> base-1 = 20 -> 10
insert 6
6 4 : 4 6 14 16 // +2 +8 +2 +8
Ed: 0+4,10-4,10+4,20-4, 20+4...
Base 29 -> base-1 = 28 -> 14
insert 2
2 4 : 4 10 18 24 // +6 +8 +6 +8
0+4,14-4,14+4,28-4, 28+4
</pre>
Now one sees that only few different distances need to be calculated.In the case of base 29 only 4 out of 28 = 1/7 => runtime about 700 s.Or for a 4-core CPU test every 28 from the different start values.
For base 49 one needs 8 Core to check every 48 ;-)
<pre> Base 49 48-> 24 ->12 -> 6 ( 5+1 = 6 ? )
insert 1
1 8 : 5 11 13 19 29 35 37 43 //+6+2+6+10+6+2+6+10</pre>
0+5,12-1(= 6-5),12+1,24-5,24+5,36-1,36+1,48-5
| |||