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
(→Minimum start for Pascal version: possible correction for base 34) |
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) |
||
| (7 intermediate revisions by 3 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 463 ⟶ 495:
::: 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
| |||