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: yes, it was a copy and paste error) |
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) |
||
| (6 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 465 ⟶ 497:
::::: 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
| |||