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
m (→Minimum start for Pascal version: thanks) |
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) |
||
| (11 intermediate revisions by 4 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 70 ⟶ 76:
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 400 ⟶ 432:
: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
| |||