Anonymous user
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 08:30, 20 June 2019
, 4 years agoFinding maximal distances to check if number needs extra digit
m (→Minimum start for Pascal version: yes, it was a copy and paste error) |
(Finding maximal distances to check if number needs extra digit) |
||
Line 465:
::::: 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
insert 1
1 4 : 3 5 11 13 //distances = +2 +6 +2 +6 // digital roots of 3,5,11,13 lead to possible solution
8 4 : 4 8 12 16 //distances = +4 +4 +4 +4
9 4 : 1 7 9 15 //distances = +6 +2 +6 +2
12 4 : 2 6 10 14 //distances = +4 +4 +4 +4
Base 21 -> base-1 = 20
insert 6
6 4 : 4 6 14 16 // +2 +8 +2 +8
10 2 : 10 20 // +10 +10
11 4 : 1 9 11 19 // +8 +2 +8 +2
14 4 : 2 8 12 18 // +6 +4 +6 +4
15 2 : 5 15 // +10 +10
19 4 : 3 7 13 17 // +6 +6 +4 +4
Base 29 -> base-1 = 28
insert 2
2 4 : 4 10 18 24 // +6 +8 +6 +8
7 2 : 7 21 //+14 +14
11 4 : 5 9 19 23 //+4 +10 +4 10
14 2 : 14 28 //+14 +14
15 4 : 1 13 15 27 //+12+2+12+2
18 4 : 2 12 16 26 //+10+4+10+4
22 4 : 6 8 20 22 //+2+12+2+12
23 4 : 3 11 17 25 //+8+6+8+6
</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
insert 1
1 8 : 5 11 13 19 29 35 37 43 //+6+2+6+10+6+2+6+10</pre>
| |||