I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Talk:Magnanimous numbers

From Rosetta Code

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
  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)