Anonymous user
Talk:Magnanimous numbers: Difference between revisions
m
→How to find bigger numbers faster: No new magnanimous number up to 1e19
(→How to find bigger numbers faster: new section) |
m (→How to find bigger numbers faster: No new magnanimous number up to 1e19) |
||
(3 intermediate revisions by the same user not shown) | |||
Line 1:
== How to find bigger numbers faster ==
Just a simple observation.<BR>Numbers with more than 2 digits that end in an even number <b>must</b> have all other
<pre>
557: 882428665
558: 995955112</pre>
So one can construct those numbers as base 5 numbers converted to decimal and append the last digit.<BR>
dgt[x] = 0..4 goes into
even decimal digits 2*dgt[x] -> /0/,2,4,6,8 and than odd digits 2*dgt[x]+1 -> 1,3,5,7,9<br>
/0/ ist tested one digit before.<BR>
lets go with total 3 digits, so 2 digits in base 5 in front once even, once odd interpretated<br>
<pre>
Dgt[0,0] = 00 even : 001, 003, 005, 007, 009 odd 11 : 110, 112, 114, 116, 118
Dgt[0,1] = 02 even : 021, 023, 025, 027, 029 odd 13 : 130, 132, 134, 136, 138
Dgt[0,2] = 04 even : 041, 043, 045, 047, 049 odd 15 : 150, 152, 154, 156, 158
Dgt[0,3] = 06 even : 061, 063, 065, 067, 069 odd 17 : 170, 172, 174, 176, 178
Dgt[0,4] = 08 even : 081, 083, 085, 087, 089 odd 19 : 190, 192, 194, 196, 198
Dgt[1,0] = 20 even : 201, 203, 205, 207, 209 odd 31 : 310, 312, 314, 316, 318
Dgt[1,1] = 22 even : 221, 223, 225, 227, 229 odd 33 : 330, 332, 334, 336, 338
Dgt[1,2] = 24 even : 241, 243, 245, 247, 249 odd 35 : 350, 352, 354, 356, 358
Dgt[1,3] = 26 even : 261, 263, 265, 267, 269 odd 37 : 370, 372, 374, 376, 378
Dgt[1,4] = 28 even : 281, 283, 285, 287, 289 odd 39 : 390, 392, 394, 396, 398
Dgt[2,0] = 40 even : 401, 403, 405, 407, 409 odd 51 : 510, 512, 514, 516, 518
Dgt[2,1] = 42 even : 421, 423, 425, 427, 429 odd 53 : 530, 532, 534, 536, 538
Dgt[2,2] = 44 even : 441, 443, 445, 447, 449 odd 55 : 550, 552, 554, 556, 558
Dgt[2,3] = 46 even : 461, 463, 465, 467, 469 odd 57 : 570, 572, 574, 576, 578
Dgt[2,4] = 48 even : 481, 483, 485, 487, 489 odd 59 : 590, 592, 594, 596, 598
Dgt[3,0] = 60 even : 601, 603, 605, 607, 609 odd 71 : 710, 712, 714, 716, 718
Dgt[3,1] = 62 even : 621, 623, 625, 627, 629 odd 73 : 730, 732, 734, 736, 738
Dgt[3,2] = 64 even : 641, 643, 645, 647, 649 odd 75 : 750, 752, 754, 756, 758
Dgt[3,3] = 66 even : 661, 663, 665, 667, 669 odd 77 : 770, 772, 774, 776, 778
Dgt[3,4] = 68 even : 681, 683, 685, 687, 689 odd 79 : 790, 792, 794, 796, 798
Dgt[4,0] = 80 even : 801, 803, 805, 807, 809 odd 91 : 910, 912, 914, 916, 918
Dgt[4,1] = 82 even : 821, 823, 825, 827, 829 odd 93 : 930, 932, 934, 936, 938
Dgt[4,2] = 84 even : 841, 843, 845, 847, 849 odd 95 : 950, 952, 954, 956, 958
Dgt[4,3] = 86 even : 861, 863, 865, 867, 869 odd 97 : 970, 972, 974, 976, 978
Dgt[4,4] = 88 even : 881, 883, 885, 887, 889 odd 99 : 990, 992, 994, 996, 998</pre>
Now one can see, that 101 isn't in there<br>
No big win for 3 digits 20*10 versus 900.<br>But for 9 digits 5^8*10 vs 1e9-1e8 : 3,906,250 vs 900,000,000 = 1/230.4 reducing a week (168 h ) to 45 min<br>
To speed up prime test of the partial numbers of digits, start with the one of same size in the middle.<br>
Show with 995,955,112
<pre>
first
9959 + 55112 = 65071
99595 + 5112 = 104707
995955 + 112 = 996067
995 + 955112 = 956107
9959551 + 12 =
99 + 5955112 =
9 + 95955112 =
99595511 + 2 =
</pre>
Especially for large numbers it is important to test first the smallest values, which can be checked in a sieve of erathostenes, to reject them as soon as possible.Notice, to check 1e9-1 = 999,999,999 , you need a sieve of size 1e8+8.
I can not imagine, how to get such a large number like the 571.th 97,393,713,331,910 in "acceptable" time.
-[[User:Horsth|Horsth]] ([[User talk:Horsth|talk]]) 17:49, 1 October 2021 (UTC)
It is done :-)<br>
modified using gmp see page
<pre>
getting primes 1.980 s
Count of gmp tests 213984
...
570 5391391551358
571 97393713331910
83.827 s // now 42.760 s
real 1m25,842s user 1m25,283ssys 0m0,220ss
</pre>
-[[User:Horst.h|Horst.h]] ([[User talk:Horst.h|talk]]) 15:27, 4 October 2021 (UTC)
::stopped searching after 18 digits finished.Still 571 magnanimous numbers <BR>
<pre>stopped
571 1,195,393,333,331,999,198 15260.633 s</pre>
19 digits will take about 16h...
As one can see, ending in 8, so no 7 in the number.
-[[User:Horst.h|Horst.h]] ([[User talk:Horst.h|talk]]) 17:28, 5 October 2021 (UTC)
|