I first mentioned Home Primes in a post from Sunday, March 8th 2020, titled Prime Weeks. As the Wikipedia entry states regarding this class of primes:
Investigations into home primes make up a minor side issue in number theory. Its questions have served as test fields for the implementation of efficient algorithms for factoring composite numbers, but the subject is really one in recreational mathematics.
So let's put serious mathematics aside and delve into this corner of recreational mathematics. Let's begin with the definition, from the same source, that runs:
In number theory, the home prime HP(\(n\)) of an integer \(n\) greater than 1 is the prime number obtained by repeatedly factoring the increasing concatenation of prime factors including repetitions.
Using SageMath, I was able to create an algorithm to determine the home prime for any composite integer. See Figure 1 with permalink attached.
As can be seen, the number
26327 (my diurnal age on the day of this post's creation) leads, after eight steps, to its home prime of
3325112912503. Apart from the fact that it represents my diurnal age, the reason that I chose 26327 as my example above is that it factorises to 7 x 3761 and the latter number has an important connection to home primes because it is a member of OEIS
A118756:
A118756 | |
a(\(n\)) = smallest prime \(p\) such that \(p\) is the home prime of exactly \(n\) natural numbers.
|
The sequence begins: 2, 23, 211, 379, 773, 3389, 23251, 3761, ... and so 3761 is in the position corresponding to \(n=8\). This means that there are seven composite numbers whose home prime is 3761. These are listed in the OEIS comments section for the sequence. The eight numbers are:
140, 332, 514, 566, 1281, 2257, 2283, 3761
Let's now consider
OEIS A037274 that lists the home primes (if known) for all the natural numbers:
A037274 |
|
Home primes: for n >= 2, a(n) = the prime that is finally reached when you start with n, concatenate its prime factors (A037276) and repeat until a prime is reached (a(n) = -1 if no prime is ever reached).
|
Here is the sequence up to \(n=48\):
1, 2, 3, 211, 5, 23, 7, 3331113965338635107, 311, 773, 11, 223, 13, 13367, 1129, 31636373, 17, 233, 19, 3318308475676071413, 37, 211, 23, 331319, 773, 3251, 13367, 227, 29, 547, 31, 241271, 311, 31397, 1129, 71129, 37, 373, 313, 3314192745739, 41, 379, 43, 22815088913, 3411949, 223, 47, 6161791591356884791277
Looking at the terms in this sequence, it can be seen that the home prime for \(n=8\) is a staggering 3331113965338635107. The progression is as follows:
31941 -> 3 * 3 * 3 * 7 * 13 * 13
311123771 -> 7 * 149 * 317 * 941
7149317941 -> 229 * 31219729
22931219729 -> 11 * 2084656339
112084656339 -> 3 * 347 * 911 * 118189
3347911118189 -> 11 * 613 * 496501723
11613496501723 -> 97 * 130517 * 917327
97130517917327 -> 53 * 1832651281459
531832651281459 -> 3 * 3 * 3 * 11 * 139 * 653 * 3863 * 5107
3331113965338635107 is prime, so a(8) = 3331113965338635107
However, upon reaching \(n=49\), we encounter the first number that has no known home prime. The composite numbers deriving from 49 and that so far do not lead to a prime are listed in OEIS A056938:
A056938 | |
Concatenate all the prime divisors in previous term (with repetition), starting at 49.
|
The initial terms are:
49, 77, 711, 3379, 31109, 132393, 344131, 1731653, 71143523, 11115771019, 31135742029, 717261644891, 11193431873899, 116134799345907, 3204751189066719, 31068250396355573, 62161149980213343, 336906794442245927, 734615161567701999, 31318836286194043641
IMPORTANT RESOURCES
This site provides a list of numbers up to 10000 together with the progressions to their respective home primes (if known).
This site lists the 471 numbers less than 10000 for which there are no known home primes. In TABLE 1 below I've copied and pasted the first column. The numbers with backgrounds shaded in green may have home primes but not those unshaded (as far as is known). For example, 669 leads to a home prime after 46 steps. I developed a modified algorithm to take into account numbers that don't end in a prime after a certain number of cycles (50 seems to be about the limit for SageMathCell). See Figure 2 that uses 669 as an example. Permalink attached.
TABLE 1
| 49 |
| 112 |
| 146 |
| 234 |
| 242 |
| 284 |
| 300 |
| 312 |
| 320 |
| 322 |
| 326 |
| 328 |
| 336 |
| 352 |
| 363 |
| 372 |
| 412 |
| 460 |
| 495 |
| 548 |
| 556 |
| 576 |
| 596 |
| 663 |
| 665 |
| 669 |
| 670 |
| 693 |
| 712 |
| 714 |
| 715 |
| 744 |
| 749 |
| 762 |
| 768 |
| 782 |
| 796 |
| 845 |
| 847 |
| 858 |
| 861 |
| 867 |
| 896 |
| 925 |
| 973 |
| 978 |
| 984 |
| 992 |
| 1008 |
| 1030 |
| 1053 |
| 1067 |
| 1138 |
| 1139 |
| 1220 |
| 1248 |
| 1298 |
| 1314 |
| 1315 |
| 1316 |
| 1328 |
| 1370 |
| 1394 |
| 1408 |
| 1416 |
| 1444 |
| 1448 |
| 1452 |
| 1455 |
| 1456 |
| 1467 |
| 1515 |
| 1519 |
| 1521 |
| 1529 |
| 1539 |
| 1552 |
| 1565 |
| 1568 |
| 1595 |
| 1596 |
| 1610 |
| 1628 |
| 1672 |
| 1681 |
| 1726 |
| 1734 |
| 1751 |
| 1757 |
| 1772 |
| 1781 |
| 1782 |
| 1846 |
| 1855 |
| 1897 |
| 1908 |
| 1915 |
| 1956 |
| 1964 |
| 1980 |
| 1985 |
| 2008 |
| 2021 |
| 2025 |
| 2040 |
| 2048 |
| 2068 |
| 2071 |
| 2104 |
| 2105 |
| 2112 |
| 2114 |
| 2117 |
| 2138 |
| 2147 |
| 2148 |
| 2172 |
| 2189 |
| 2206 |
| 2248 |
| 2252 |
| 2262 |
| 2265 |
| 2280 |
| 2316 |
| 2320 |
| 2321 |
| 2360 |
| 2390 |
| 2410 |
| 2432 |
| 2436 |
| 2442 |
| 2465 |
| 2480 |
| 2484 |
| 2510 |
| 2520 |
| 2558 |
| 2560 |
| 2581 |
| 2594 |
| 2611 |
| 2618 |
| 2637 |
| 2642 |
| 2658 |
| 2660 |
| 2662 |
| 2684 |
| 2686 |
| 2745 |
| 2774 |
| 2784 |
| 2796 |
| 2800 |
| 2802 |
| 2812 |
| 2816 |
| 2842 |
| 2848 |
| 2888 |
| 2922 |
| 2965 |
| 2993 |
| 3006 |
| 3016 |
| 3024 |
| 3036 |
| 3038 |
| 3056 |
| 3068 |
| 3102 |
| 3108 |
| 3110 |
| 3136 |
| 3158 |
| 3168 |
| 3172 |
| 3192 |
| 3200 |
| 3208 |
| 3210 |
| 3215 |
| 3238 |
| 3250 |
| 3252 |
| 3262 |
| 3270 |
| 3278 |
| 3285 |
| 3286 |
| 3288 |
| 3296 |
| 3304 |
| 3332 |
| 3336 |
| 3363 |
| 3368 |
| 3370 |
| 3386 |
| 3388 |
| 3393 |
| 3408 |
| 3429 |
| 3451 |
| 3454 |
| 3466 |
| 3470 |
| 3475 |
| 3489 |
| 3492 |
| 3495 |
| 3498 |
| 3520 |
| 3586 |
| 3604 |
| 3606 |
| 3662 |
| 3675 |
| 3685 |
| 3720 |
| 3721 |
| 3755 |
| 3766 |
| 3776 |
| 3782 |
| 3790 |
| 3800 |
| 3806 |
| 3813 |
| 3816 |
| 3835 |
| 3836 |
| 3852 |
| 3858 |
| 3867 |
| 3868 |
| 3879 |
| 3894 |
| 3905 |
| 3909 |
| 3916 |
| 3955 |
| 3966 |
| 3968 |
| 3970 |
| 4012 |
| 4020 |
| 4036 |
| 4046 |
| 4048 |
| 4050 |
| 4060 |
| 4065 |
| 4067 |
| 4097 |
| 4108 |
| 4109 |
| 4122 |
| 4145 |
| 4172 |
| 4186 |
| 4188 |
| 4203 |
| 4205 |
| 4224 |
| 4225 |
| 4230 |
| 4240 |
| 4257 |
| 4260 |
| 4300 |
| 4301 |
| 4318 |
| 4320 |
| 4352 |
| 4436 |
| 4440 |
| 4442 |
| 4454 |
| 4470 |
| 4480 |
| 4494 |
| 4497 |
| 4500 |
| 4532 |
| 4541 |
| 4556 |
| 4557 |
| 4559 |
| 4574 |
| 4580 |
| 4581 |
| 4582 |
| 4632 |
| 4687 |
| 4695 |
| 4719 |
| 4746 |
| 4776 |
| 4777 |
| 4790 |
| 4791 |
| 4836 |
| 4852 |
| 4883 |
| 4884 |
| 4887 |
| 4890 |
| 4891 |
| 4911 |
| 4927 |
| 4930 |
| 4936 |
| 4941 |
| 4944 |
| 4946 |
| 4980 |
| 4986 |
| 4992 |
| 5010 |
| 5029 |
| 5037 |
| 5055 |
| 5060 |
| 5090 |
| 5110 |
| 5115 |
| 5116 |
| 5145 |
| 5152 |
| 5154 |
| 5160 |
| 5180 |
| 5182 |
| 5185 |
| 5187 |
| 5194 |
| 5214 |
| 5256 |
| 5278 |
| 5280 |
| 5284 |
| 5301 |
| 5312 |
| 5320 |
| 5324 |
| 5368 |
| 5370 |
| 5377 |
| 5400 |
| 5403 |
| 5406 |
| 5416 |
| 5432 |
| 5460 |
| 5465 |
| 5488 |
| 5494 |
| 5496 |
| 5536 |
| 5551 |
| 5564 |
| 5608 |
| 5620 |
| 5621 |
| 5632 |
| 5652 |
| 5668 |
| 5670 |
| 5674 |
| 5680 |
| 5692 |
| 5698 |
| 5708 |
| 5720 |
| 5736 |
| 5740 |
| 5756 |
| 5760 |
| 5778 |
| 5792 |
| 5800 |
| 5845 |
| 5856 |
| 5858 |
| 5866 |
| 5871 |
| 5874 |
| 5882 |
| 5905 |
| 5910 |
| 5912 |
| 5916 |
| 5931 |
| 5949 |
| 6013 |
| 6024 |
| 6063 |
| 6069 |
| 6077 |
| 6078 |
| 6084 |
| 6094 |
| 6100 |
| 6102 |
| 6138 |
| 6146 |
| 6149 |
| 6154 |
| 6175 |
| 6176 |
| 6205 |
| 6210 |
| 6212 |
| 6223 |
| 6227 |
| 6244 |
| 6256 |
| 6294 |
| 6314 |
| 6328 |
| 6332 |
| 6333 |
| 6336 |
| 6351 |
| 6366 |
| 6384 |
| 6386 |
| 6400 |
| 6405 |
| 6409 |
| 6414 |
| 6436 |
| 6444 |
| 6445 |
| 6448 |
| 6452 |
| 6454 |
| 6467 |
| 6495 |
| 6516 |
| 6533 |
| 6541 |
| 6548 |
| 6550 |
| 6561 |
| 6572 |
| 6612 |
| 6615 |
| 6666 |
| 6670 |
| 6671 |
| 6680 |
| 6710 |
| 6729 |
| 6785 |
| 6811 |
| 6812 |
| 6816 |
| 6819 |
| 6820 |
| 6836 |
| 6840 |
| 6859 |
| 6864 |
| 6873 |
| 6877 |
| 6906 |
| 6919 |
| 6932 |
| 6944 |
| 6972 |
| 6985 |
| 6989 |
| 7009 |
| 7017 |
| 7024 |
| 7032 |
| 7048 |
| 7049 |
| 7056 |
| 7059 |
| 7065 |
| 7072 |
| 7089 |
| 7091 |
| 7092 |
| 7096 |
| 7119 |
| 7128 |
| 7168 |
| 7188 |
| 7194 |
| 7203 |
| 7204 |
| 7210 |
| 7248 |
| 7267 |
| 7282 |
| 7316 |
| 7343 |
| 7345 |
| 7360 |
| 7385 |
| 7394 |
| 7395 |
| 7403 |
| 7465 |
| 7494 |
| 7506 |
| 7540 |
| 7554 |
| 7562 |
| 7615 |
| 7628 |
| 7648 |
| 7654 |
| 7668 |
| 7686 |
| 7696 |
| 7707 |
| 7714 |
| 7720 |
| 7749 |
| 7765 |
| 7770 |
| 7776 |
| 7824 |
| 7826 |
| 7832 |
| 7864 |
| 7865 |
| 7872 |
| 7880 |
| 7896 |
| 7902 |
| 7904 |
| 7923 |
| 7965 |
| 7972 |
| 7987 |
| 8000 |
| 8008 |
| 8020 |
| 8049 |
| 8085 |
| 8112 |
| 8114 |
| 8120 |
| 8127 |
| 8134 |
| 8155 |
| 8170 |
| 8178 |
| 8189 |
| 8193 |
| 8222 |
| 8250 |
| 8255 |
| 8262 |
| 8277 |
| 8324 |
| 8349 |
| 8375 |
| 8382 |
| 8393 |
| 8398 |
| 8448 |
| 8449 |
| 8457 |
| 8475 |
| 8506 |
| 8516 |
| 8540 |
| 8546 |
| 8558 |
| 8560 |
| 8562 |
| 8569 |
| 8575 |
| 8585 |
| 8592 |
| 8603 |
| 8608 |
| 8610 |
| 8618 |
| 8624 |
| 8635 |
| 8668 |
| 8670 |
| 8680 |
| 8696 |
| 8704 |
| 8709 |
| 8710 |
| 8729 |
| 8734 |
| 8736 |
| 8739 |
| 8740 |
| 8757 |
| 8763 |
| 8784 |
| 8790 |
| 8793 |
| 8806 |
| 8824 |
| 8846 |
| 8873 |
| 8874 |
| 8890 |
| 8909 |
| 8932 |
| 8934 |
| 8940 |
| 8943 |
| 8949 |
| 8960 |
| 9002 |
| 9012 |
| 9025 |
| 9027 |
| 9048 |
| 9075 |
| 9080 |
| 9086 |
| 9088 |
| 9095 |
| 9104 |
| 9119 |
| 9120 |
| 9130 |
| 9141 |
| 9145 |
| 9158 |
| 9189 |
| 9262 |
| 9266 |
| 9273 |
| 9282 |
| 9295 |
| 9316 |
| 9328 |
| 9339 |
| 9350 |
| 9373 |
| 9412 |
| 9446 |
| 9448 |
| 9449 |
| 9458 |
| 9482 |
| 9486 |
| 9487 |
| 9495 |
| 9499 |
| 9502 |
| 9513 |
| 9524 |
| 9529 |
| 9570 |
| 9577 |
| 9585 |
| 9588 |
| 9591 |
| 9594 |
| 9595 |
| 9600 |
| 9603 |
| 9620 |
| 9624 |
| 9630 |
| 9644 |
| 9648 |
| 9651 |
| 9659 |
| 9667 |
| 9685 |
| 9688 |
| 9690 |
| 9702 |
| 9724 |
| 9732 |
| 9740 |
| 9747 |
| 9761 |
| 9773 |
| 9780 |
| 9792 |
| 9812 |
| 9815 |
| 9836 |
| 9863 |
| 9874 |
| 9877 |
| 9881 |
| 9890 |
| 9900 |
| 9922 |
| 9937 |
| 9951 |
| 9961 |
| 9964 |
| 9965 |
| 9975 |
| 9978 |
| 9983 |
| 9998 |
| 10014 |
| 10018 |
| 10024 |
| 10031 |
| 10045 |
| 10048 |
| 10050 |
| 10052 |
| 10058 |
| 10064 |
| 10081 |
| 10090 |
| 10094 |
| 10098 |
| 10132 |
| 10136 |
| 10158 |
| 10179 |
| 10200 |
| 10203 |
| 10208 |
| 10218 |
| 10234 |
| 10240 |
| 10244 |
| 10266 |
| 10270 |
| 10272 |
| 10302 |
| 10304 |
| 10305 |
| 10312 |
| 10332 |
| 10335 |
| 10353 |
| 10374 |
| 10380 |
| 10395 |
| 10409 |
| 10411 |
| 10415 |
| 10424 |
| 10437 |
| 10467 |
| 10478 |
| 10485 |
| 10490 |
| 10492 |
| 10496 |
| 10523 |
| 10530 |
| 10538 |
| 10541 |
| 10542 |
| 10566 |
| 10572 |
| 10577 |
| 10579 |
| 10580 |
| 10595 |
| 10609 |
| 10610 |
| 10616 |
| 10620 |
| 10624 |
| 10640 |
| 10650 |
| 10659 |
| 10668 |
| 10676 |
| 10683 |
| 10700 |
| 10703 |
| 10748 |
| 10755 |
| 10764 |
| 10773 |
| 10825 |
| 10829 |
| 10830 |
| 10832 |
| 10836 |
| 10845 |
| 10850 |
| 10863 |
| 10864 |
| 10865 |
| 10872 |
| 10895 |
| 10913 |
| 10914 |
| 10948 |
| 10956 |
| 10969 |
| 10971 |
| 10972 |
| 10976 |
| 10982 |
| 10991 |
| 11000 |
| 11011 |
| 11024 |
| 11040 |
| 11067 |
| 11080 |
| 11130 |
| 11133 |
| 11136 |
| 11168 |
| 11183 |
| 11187 |
| 11189 |
| 11244 |
| 11247 |
| 11254 |
| 11256 |
| 11275 |
| 11280 |
| 11286 |
| 11293 |
| 11334 |
| 11370 |
| 11378 |
| 11440 |
| 11476 |
| 11496 |
| 11500 |
No comments:
Post a Comment