Talk:Magnanimous numbers: Difference between revisions
(→How to find bigger numbers faster: new section) |
(→How to find bigger numbers faster: show/explain how it works) |
||
Line 1: | Line 1: | ||
== How to find bigger numbers faster == |
== 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 |
Just a simple observation.<BR>Numbers with more than 2 digits that end in an even number <b>must</b> 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. |
||
<pre> |
<pre> |
||
557: 882428665 |
557: 882428665 |
||
558: 995955112</pre> |
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) |
-[[User:Horsth|Horsth]] ([[User talk:Horsth|talk]]) 17:49, 1 October 2021 (UTC) |
Revision as of 08:48, 2 October 2021
How to find bigger numbers faster
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)