Talk:First perfect square in base n with n unique digits: Difference between revisions
Content added Content deleted
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: | 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 |
::::: 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 |
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> |