Talk:Magnanimous numbers
How to find bigger numbers faster[edit]
Just a simple observation.
Numbers with more than 2 digits that end in an even number must have all other digits odd and vice versa, so the sum of of partial numbers can't get even and therefor not prime.The exception ist 101, which sums to 2, the only even prime.
557: 882428665 558: 995955112
So one can construct those numbers as base 5 numbers converted to decimal and append the last digit.
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
/0/ ist tested one digit before.
lets go with total 3 digits, so 2 digits in base 5 in front once even, once odd interpretated
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
Now one can see, that 101 isn't in there
No big win for 3 digits 20*10 versus 900.
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
To speed up prime test of the partial numbers of digits, start with the one of same size in the middle.
Show with 995,955,112
first 9959 + 55112 = 65071 99595 + 5112 = 104707 995955 + 112 = 996067 995 + 955112 = 956107 9959551 + 12 = 99 + 5955112 = 9 + 95955112 = 99595511 + 2 =
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.
-Horsth (talk) 17:49, 1 October 2021 (UTC)
It is done :-)
modified using gmp see page
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
-Horst.h (talk) 15:27, 4 October 2021 (UTC)
- stopped searching after 18 digits finished.Still 571 magnanimous numbers
- stopped searching after 18 digits finished.Still 571 magnanimous numbers
stopped 571 1,195,393,333,331,999,198 15260.633 s
19 digits will take about 16h... As one can see, ending in 8, so no 7 in the number. -Horst.h (talk) 17:28, 5 October 2021 (UTC)