mersenneforum.org Computing divisors from complete factorization
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2021-10-04, 11:21 #12 alpertron     Aug 2002 Buenos Aires, Argentina 144710 Posts I asked this problem in another forum and someone pointed to https://stackoverflow.com/questions/...ithout-sorting . I will analyze the solution posted there.
 2021-10-04, 15:29 #13 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 1000110000112 Posts Here is an alternative that is probably the most practical for the factorials in particular as long as they can be calculated. Code: \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ f=100! theregister=100 theThou = vector(theregister);theCounter=0; theCounter=0; for(i=1,f,{ if(gcd(f,i)==i, theCounter=theCounter+1; theThou[theCounter]=i; if(theCounter==100, theCounter=0; print("***************"); print(theThou ); ); ); }) \\\\\\\\\\\\\\\\\\\\\\\\\\\\\ Code: *************** [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100] *************** [102, 104, 105, 106, 108, 110, 111, 112, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 128, 129, 130, 132, 133, 134, 135, 136, 138, 140, 141, 142, 143, 144, 145, 146, 147, 148, 150, 152, 153, 154, 155, 156, 158, 159, 160, 161, 162, 164, 165, 166, 168, 169, 170, 171, 172, 174, 175, 176, 177, 178, 180, 182, 183, 184, 185, 186, 187, 188, 189, 190, 192, 194, 195, 196, 198, 200, 201, 203, 204, 205, 207, 208, 209, 210, 212, 213, 215, 216, 217, 219, 220, 221, 222, 224, 225, 228, 230] *************** [231, 232, 234, 235, 236, 237, 238, 240, 242, 243, 244, 245, 246, 247, 248, 249, 250, 252, 253, 255, 256, 258, 259, 260, 261, 264, 265, 266, 267, 268, 270, 272, 273, 275, 276, 279, 280, 282, 284, 285, 286, 287, 288, 289, 290, 291, 292, 294, 295, 296, 297, 299, 300, 301, 304, 305, 306, 308, 310, 312, 315, 316, 318, 319, 320, 322, 323, 324, 325, 328, 329, 330, 332, 333, 335, 336, 338, 340, 341, 342, 343, 344, 345, 348, 350, 351, 352, 354, 355, 356, 357, 360, 361, 363, 364, 365, 366, 368, 369, 370] *************** [371, 372, 374, 375, 376, 377, 378, 380, 384, 385, 387, 388, 390, 391, 392, 395, 396, 399, 400, 402, 403, 405, 406, 407, 408, 410, 413, 414, 415, 416, 418, 420, 423, 424, 425, 426, 427, 429, 430, 432, 434, 435, 437, 438, 440, 441, 442, 444, 445, 448, 450, 451, 455, 456, 459, 460, 462, 464, 465, 468, 469, 470, 472, 473, 474, 475, 476, 477, 480, 481, 483, 484, 485, 486, 488, 490, 492, 493, 494, 495, 496, 497, 498, 500, 504, 506, 507, 510, 511, 512, 513, 516, 517, 518, 520, 522, 525, 527, 528, 529] *************** [530, 531, 532, 533, 534, 536, 539, 540, 544, 546, 549, 550, 551, 552, 553, 555, 558, 559, 560, 561, 564, 567, 568, 570, 572, 574, 575, 576, 578, 580, 581, 582, 583, 584, 585, 588, 589, 590, 592, 594, 595, 598, 600, 602, 603, 605, 608, 609, 610, 611, 612, 615, 616, 620, 621, 623, 624, 625, 627, 629, 630, 632, 636, 637, 638, 639, 640, 644, 645, 646, 648, 649, 650, 651, 656, 657, 658, 660, 663, 664, 665, 666, 667, 670, 671, 672, 675, 676, 679, 680, 682, 684, 686, 688, 689, 690, 693, 696, 697, 700] *************** [702, 703, 704, 705, 708, 710, 711, 712, 713, 714, 715, 720, 722, 725, 726, 728, 729, 730, 731, 732, 735, 736, 737, 738, 740, 741, 742, 744, 747, 748, 750, 752, 754, 756, 759, 760, 765, 767, 768, 770, 774, 775, 776, 777, 779, 780, 781, 782, 783, 784, 790, 792, 793, 795, 798, 799, 800, 801, 803, 804, 805, 806, 810, 812, 814, 816, 817, 819, 820, 825, 826, 828, 830, 832, 833, 836, 837, 840, 841, 845, 846, 847, 848, 850, 851, 852, 854, 855, 858, 860, 861, 864, 867, 868, 869, 870, 871, 873, 874, 875] *************** [876, 880, 882, 884, 885, 888, 890, 891, 893, 896, 897, 899, 900, 901, 902, 903, 910, 912, 913, 915, 918, 920, 923, 924, 925, 928, 930, 931, 935, 936, 938, 940, 943, 944, 945, 946, 948, 949, 950, 952, 954, 957, 960, 961, 962, 966, 968, 969, 970, 972, 975, 976, 979, 980, 984, 986, 987, 988, 989, 990, 992, 994, 996, 999, 1000, 1001, 1003, 1005, 1007, 1008, 1012, 1014, 1015, 1020, 1022, 1023, 1024, 1025, 1026, 1027, 1029, 1032, 1034, 1035, 1036, 1037, 1040, 1044, 1045, 1050, 1053, 1054, 1056, 1058, 1060, 1062, 1064, 1065, 1066, 1067] *************** [1068, 1071, 1072, 1073, 1075, 1078, 1079, 1080, 1081, 1083, 1085, 1088, 1089, 1092, 1095, 1098, 1100, 1102, 1104, 1105, 1106, 1107, 1110, 1113, 1116, 1118, 1120, 1121, 1122, 1125, 1127, 1128, 1131, 1134, 1136, 1139, 1140, 1144, 1147, 1148, 1150, 1152, 1155, 1156, 1157, 1159, 1160, 1161, 1162, 1164, 1166, 1168, 1170, 1173, 1175, 1176, 1178, 1180, 1183, 1184, 1185, 1188, 1189, 1190, 1196, 1197, 1200, 1204, 1206, 1207, 1209, 1210, 1215, 1216, 1218, 1219, 1220, 1221, 1222, 1224, 1225, 1230, 1232, 1235, 1239, 1240, 1241, 1242, 1245, 1246, 1247, 1248, 1250, 1254, 1258, 1260, 1261, 1264, 1265, 1269] *************** [1271, 1272, 1273, 1274, 1275, 1276, 1278, 1280, 1281, 1287, 1288, 1290, 1292, 1295, 1296, 1298, 1300, 1302, 1305, 1309, 1311, 1312, 1314, 1316, 1320, 1323, 1325, 1326, 1328, 1330, 1331, 1332, 1333, 1334, 1335, 1340, 1342, 1343, 1344, 1349, 1350, 1352, 1353, 1357, 1358, 1360, 1363, 1364, 1365, 1368, 1369, 1372, 1375, 1376, 1377, 1378, 1380, 1386, 1387, 1392, 1394, 1395, 1400, 1403, 1404, 1406, 1407, 1408, 1410, 1411, 1416, 1419, 1420, 1421, 1422, 1424, 1425, 1426, 1428, 1430, 1431, 1435, 1440, 1443, 1444, 1445, 1449, 1450, 1452, 1455, 1456, 1457, 1458, 1460, 1462, 1463, 1464, 1470, 1472, 1474] *************** [1475, 1476, 1479, 1480, 1482, 1484, 1485, 1488, 1491, 1494, 1495, 1496, 1500, 1501, 1504, 1505, 1508, 1512, 1513, 1517, 1518, 1519, 1520, 1521, 1525, 1530, 1533, 1534, 1536, 1537, 1539, 1540, 1541, 1547, 1548, 1550, 1551, 1552, 1554, 1558, 1560, 1562, 1564, 1566, 1568, 1573, 1575, 1577, 1580, 1581, 1584, 1586, 1587, 1590, 1591, 1593, 1595, 1596, 1598, 1599, 1600, 1602, 1606, 1608, 1610, 1612, 1615, 1617, 1620, 1624, 1625, 1628, 1632, 1633, 1634, 1638, 1640, 1643, 1645, 1647, 1649, 1650, 1652, 1653, 1656, 1659, 1660, 1664, 1665, 1666, 1672, 1674, 1675, 1677, 1679, 1680, 1681, 1682, 1683, 1690] *************** [1691, 1692, 1694, 1696, 1700, 1701, 1702, 1704, 1705, 1708, 1710, 1711, 1715, 1716, 1720, 1722, 1725, 1728, 1729, 1734, 1736, 1738, 1739, 1740, 1742, 1743, 1746, 1748, 1749, 1750, 1752, 1755, 1760, 1763, 1764, 1767, 1768, 1769, 1770, 1771, 1775, 1776, 1780, 1782, 1785, 1786, 1792, 1794, 1798, 1800, 1802, 1804, 1805, 1806, 1809, 1813, 1815, 1817, 1820, 1824, 1825, 1826, 1827, 1829, 1830, 1833, 1836, 1840, 1843, 1845, 1846, 1848, 1849, 1850, 1855, 1856, 1859, 1860, 1862, 1863, 1869, 1870, 1872, 1875, 1876, 1880, 1881, 1885, 1886, 1887, 1888, 1890, 1891, 1892, 1896, 1898, 1900, 1904, 1908, 1909] *************** [1911, 1914, 1917, 1920, 1922, 1924, 1925, 1927, 1932, 1935, 1936, 1938, 1940, 1943, 1944, 1947, 1950, 1952, 1953, 1955, 1958, 1960, 1961, 1968, 1971, 1972, 1974, 1975, 1976, 1978, 1980, 1984, 1988, 1989, 1992, 1995, 1998, 2000, 2001, 2002, 2006, 2009, 2010, 2013, 2014, 2015, 2016, 2021, 2023, 2024, 2025, 2028, 2030, 2035, 2037, 2040, 2044, 2046, 2047, 2048, 2050, 2052, 2054, 2057, 2058, 2059, 2064, 2065, 2067, 2068, 2070, 2072, 2074, 2075, 2077, 2079, 2080, 2088, 2090, 2091, 2093, 2100, 2106, 2107, 2108, 2109, 2112, 2115, 2116, 2117, 2120, 2124, 2125, 2128, 2130, 2132, 2133, 2134, 2135, 2136] *************** [2139, 2142, 2144, 2145, 2146, 2150, 2156, 2158, 2160, 2162, 2166, 2170, 2173, 2175, 2176, 2178, 2183, 2184, 2185, 2187, 2190, 2193, 2196, 2197, 2200, 2201, 2204, 2205, 2208, 2209, 2210, 2211, 2212, 2214, 2220, 2223, 2225, 2226, 2231, 2232, 2233, 2236, 2240, 2241, 2242, 2244, 2250, 2254, 2255, 2256, 2257, 2261, 2262, 2263, 2268, 2272, 2275, 2277, 2278, 2279, 2280, 2288, 2291, 2294, 2295, 2296, 2299, 2300, 2301, 2303, 2304, 2310, 2312, 2314, 2318, 2320, 2322, 2324, 2325, 2328, 2331, 2332, 2336, 2337, 2340, 2343, 2345, 2346, 2349, 2350, 2352, 2356, 2360, 2365, 2366, 2368, 2370, 2375, 2376, 2378] *************** [2379, 2380, 2385, 2387, 2392, 2394, 2397, 2400, 2401, 2403, 2405, 2407, 2408, 2409, 2412, 2414, 2415, 2418, 2419, 2420, 2425, 2430, 2431, 2432, 2436, 2438, 2440, 2442, 2444, 2448, 2449, 2450, 2451, 2457, 2460, 2464, 2465, 2470, 2475, 2478, 2479, 2480, 2482, 2484, 2485, 2490, 2491, 2492, 2494, 2496, 2499, 2500, 2501, 2508, 2511, 2516, 2520, 2522, 2523, 2527, 2528, 2530, 2535, 2537, 2538, 2541, 2542, 2544, 2546, 2548, 2550, 2552, 2553, 2555, 2556, 2560, 2562, 2565, 2573, 2574, 2576, 2580, 2581, 2583, 2584, 2585, 2590, 2592, 2596, 2597, 2600, 2601, 2604, 2607, 2610, 2613, 2618, 2619, 2622, 2623] *************** [2624, 2625, 2627, 2628, 2632, 2635, 2639, 2640, 2645, 2646, 2650, 2652, 2655, 2656, 2660, 2662, 2664, 2665, 2666, 2668, 2670, 2673, 2679, 2680, 2684, 2686, 2688, 2691, 2695, 2697, 2698, 2700, 2701, 2703, 2704, 2706, 2709, 2714, 2716, 2717, 2720, 2726, 2728, 2730, 2736, 2737, 2738, 2739, 2744, 2745, 2747, 2750, 2752, 2754, 2755, 2756, 2759, 2760, 2765, 2769, 2772, 2773, 2774, 2775, 2783, 2784, 2788, 2790, 2793, 2795, 2800, 2805, 2806, 2808, 2812, 2813, 2814, 2816, 2820, 2821, 2822, 2829, 2832, 2835, 2838, 2840, 2842, 2844, 2847, 2848, 2849, 2850, 2852, 2856, 2860, 2862, 2867, 2870, 2871, 2873] *************** [2875, 2880, 2881, 2883, 2886, 2888, 2890, 2891, 2898, 2900, 2904, 2905, 2907, 2910, 2911, 2912, 2914, 2915, 2916, 2920, 2923, 2924, 2925, 2926, 2928, 2937, 2940, 2944, 2945, 2948, 2950, 2952, 2958, 2960, 2961, 2964, 2967, 2968, 2970, 2975, 2976, 2982, 2988, 2989, 2990, 2992, 2993, 2997, 3000, 3002, 3003, 3007, 3008, 3009, 3010, 3015, 3016, 3021, 3024, 3025, 3026, 3034, 3036, 3038, 3040, 3042, 3045, 3050, 3053, 3055, 3059, 3060, 3066, 3068, 3069, 3071, 3072, 3074, 3075, 3078, 3080, 3081, 3082, 3087, 3094, 3096, 3100, 3102, 3104, 3105, 3108, 3111, 3115, 3116, 3120, 3124, 3125, 3127, 3128, 3132] *************** [3135, 3136, 3139, 3145, 3146, 3149, 3150, 3154, 3157, 3159, 3160, 3162, 3168, 3172, 3174, 3179, 3180, 3182, 3185, 3186, 3190, 3192, 3195, 3196, 3198, 3200, 3201, 3204, 3211, 3212, 3213, 3216, 3219, 3220, 3224, 3225, 3230, 3233, 3234, 3237, 3239, 3240, 3243, 3245, 3248, 3249, 3250, 3255, 3256, 3264, 3266, 3267, 3268, 3276, 3280, 3283, 3285, 3286, 3289, 3290, 3293, 3294, 3298, 3300, 3304, 3306, 3311, 3312, 3315, 3318, 3320, 3321, 3325, 3328, 3330, 3332, 3335, 3337, 3339, 3344, 3348, 3350, 3354, 3355, 3358, 3360, 3362, 3363, 3364, 3366, 3367, 3375, 3380, 3381, 3382, 3384, 3388, 3392, 3393, 3395] *************** [3397, 3400, 3402, 3403, 3404, 3408, 3410, 3416, 3417, 3420, 3422, 3430, 3431, 3432, 3440, 3441, 3444, 3445, 3450, 3451, 3456, 3458, 3465, 3468, 3471, 3472, 3476, 3477, 3478, 3479, 3480, 3483, 3484, 3485, 3486, 3492, 3496, 3498, 3500, 3504, 3509, 3510, 3515, 3519, 3520, 3525, 3526, 3528, 3534, 3536, 3538, 3540, 3542, 3549, 3550, 3551, 3552, 3553, 3555, 3560, 3564, 3565, 3567, 3569, 3570, 3572, 3575, 3577, 3584, 3588, 3589, 3591, 3596, 3599, 3600, 3604, 3608, 3610, 3612, 3618, 3619, 3621, 3625, 3626, 3627, 3630, 3634, 3640, 3645, 3648, 3649, 3650, 3652, 3654, 3655, 3657, 3658, 3660, 3663, 3666] *************** [3672, 3675, 3680, 3685, 3686, 3689, 3690, 3692, 3696, 3698, 3700, 3703, 3705, 3710, 3712, 3713, 3717, 3718, 3720, 3723, 3724, 3726, 3731, 3735, 3738, 3740, 3741, 3744, 3750, 3751, 3752, 3757, 3760, 3762, 3763, 3770, 3772, 3773, 3774, 3776, 3780, 3782, 3783, 3784, 3792, 3795, 3796, 3800, 3807, 3808, 3813, 3816, 3818, 3819, 3822, 3825, 3827, 3828, 3834, 3835, 3840, 3843, 3844, 3848, 3850, 3854, 3857, 3861, 3864, 3869, 3870, 3871, 3872, 3875, 3876, 3880, 3885, 3886, 3887, 3888, 3894, 3895, 3900, 3901, 3904, 3905, 3906, 3910, 3913, 3915, 3916, 3920, 3922, 3927, 3933, 3936, 3942, 3944, 3948, 3950] *************** [3952, 3953, 3956, 3960, 3965, 3968, 3969, 3971, 3975, 3976, 3977, 3978, 3984, 3990, 3993, 3995, 3996, 3999, 4000, 4002, 4004, 4005, 4012, 4015, 4018, 4020, 4025, 4026, 4028, 4029, 4030, 4032, 4042, 4046, 4047, 4048, 4050, 4056, 4059, 4060, 4067, 4070, 4071, 4074, 4080, 4081, 4085, 4087, 4088, 4089, 4092, 4094, 4095, 4096, 4100, 4104, 4107, 4108, 4114, 4116, 4118, 4123, 4125, 4128, 4130, 4131, 4134, 4136, 4140, 4144, 4147, 4148, 4150, 4154, 4158, 4160, 4161, 4165, 4171, 4176, 4180, 4182, 4183, 4185, 4186, 4187, 4189, 4199, 4200, 4205, 4209, 4212, 4214, 4216, 4218, 4221, 4224, 4225, 4230, 4232] *************** [4233, 4234, 4235, 4240, 4248, 4250, 4255, 4256, 4257, 4260, 4263, 4264, 4266, 4268, 4270, 4272, 4275, 4277, 4278, 4284, 4288, 4290, 4292, 4293, 4300, 4301, 4305, 4307, 4312, 4316, 4320, 4324, 4329, 4331, 4332, 4335, 4340, 4345, 4346, 4347, 4350, 4352, 4355, 4356, 4361, 4365, 4366, 4368, 4370, 4371, 4374, 4375, 4380, 4386, 4389, 4392, 4394, 4399, 4400, 4402, 4403, 4408, 4410, 4416, 4418, 4420, 4422, 4424, 4425, 4428, 4433, 4437, 4440, 4446, 4450, 4452, 4453, 4455, 4459, 4462, 4464, 4465, 4466, 4472, 4473, 4477, 4480, 4482, 4484, 4485, 4488, 4495, 4500, 4503, 4505, 4508, 4510, 4512, 4514, 4515] *************** [4522, 4524, 4526, 4536, 4539, 4543, 4544, 4550, 4551, 4554, 4556, 4557, 4558, 4559, 4560, 4563, 4565, 4575, 4576, 4582, 4588, 4590, 4592, 4598, 4599, 4600, 4602, 4606, 4608, 4611, 4615, 4617, 4620, 4623, 4624, 4625, 4628, 4636, 4640, 4641, 4644, 4648, 4650, 4653, 4655, 4656, 4661, 4662, 4664, 4669, 4672, 4674, 4675, 4680, 4686, 4690, 4692, 4693, 4697, 4698, 4700, 4704, 4712, 4715, 4717, 4719, 4720, 4725, 4730, 4731, 4732, 4736, 4740, 4743, 4745, 4750, 4752, 4753, 4756, 4757, 4758, 4760, 4761, 4770, 4773, 4774, 4779, 4784, 4785, 4788, 4794, 4797, 4800, 4802, 4805, 4806, 4807, 4810, 4814, 4816] *************** ........... Last fiddled with by a1call on 2021-10-04 at 15:30
2021-10-04, 15:38   #14
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

25·72 Posts

Quote:
 Originally Posted by alpertron I asked this problem in another forum and someone pointed to https://stackoverflow.com/questions/...ithout-sorting . I will analyze the solution posted there.
That is too much in memory, and running time if you request only (say) 4 batches of divisors.

There is a meet in the middle solution that is using (basically) only O(log(n)*(B+sqrt(D))) bits of memory,
and only O(log(D)*B) time for each batch request, here B=batchsize, D=numdivisors(n). The one time init cost is only O(log(D)*sqrt(D)).

Let n=n1*n2 and construct the divisors as d=d1*d2, where [gcd(n1,n2)=1; and numdivisors(n1) is the closest to numdivisors(n2)]
d1|n1 and d2|n2.

Let S1=divisors(n1);D1=length(S1);
S2=divisors(n2);D2=length(S2);
(S1 and S2 is sorted!)

If you fix d1 (from S1) then you know what would be the next smallest divisor using this number, just pick the next number from
the S2 set. So at anytime you will have D1=numdivisors(n1) pointers to the S2 set, and just use a priority queue/heap to
choose the smallest number from these (at most) D1 numbers, if you selected then update the pqueue/heap,
move the pointer to the next number from S2. Ofcourse with this method you'll get each time the (next) smallest divisor,
so ask it for B times.

Ask if something would not be clear.

2021-10-04, 15:56   #15
Dr Sardonicus

Feb 2017
Nowhere

5,791 Posts

Quote:
 Originally Posted by alpertron I would like to generate the divisors of a number from its complete factorization in powers of prime numbers. It is very easy to generate all of them if I do not need to be sorted, but I would like to show them in ascending order. Is there any way to do show the complete list of divisors without generating all of them and then sorting them? The number may have millions of divisors (this is the case for primorials and factorials). The idea is to show the list of divisors in batches of up to 1000 divisors. The user can continue asking for more divisors or cancel the generation of the list.
Oof. For a single prime power, it's almost trivial. For powers of two or more primes, it looks very tough.

The problem of finding all divisors up to a bound B can be reformulated as a linear inequality problem,

$\sum_{j=1}^{k}a_{j}\log(p_{j})\;\le\;B\text{, where }n\;=\;\prod_{j=1}^{k}p_{j}^{e_{j}}\text{ and }0\;\le\;a_{j}\;\le\;e_{j}$

Two cases come to mind, and I don't see a good way for either of them.

One case is a product of relatively few prime powers, some with large exponents, like a factorial or even a high power of a number with at least two prime factors, say 10^1000.

Another case is a square free number with many prime factors, like a primorial.

 2021-10-05, 14:13 #16 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 43038 Posts Not sure if you are still interested alpertron, but FTR, the code in post number 13 can be generalized to give results for factorials which are too large to be calculated.
 2021-10-05, 21:06 #17 alpertron     Aug 2002 Buenos Aires, Argentina 1,447 Posts At this moment I have a lot of work. I will continue with this on the weekend. Notice that the factorial of 100 was just an example. I really need to show the list of divisors of any integer number in ascending order given its complete factorization.
2021-10-06, 18:26   #18
Dr Sardonicus

Feb 2017
Nowhere

5,791 Posts

Quote:
 Originally Posted by R. Gerbicz If you fix d1 (from S1) then you know what would be the next smallest divisor using this number, just pick the next number from the S2 set. Ask if something would not be clear.
The bolded passage isn't clear to me. It's clear you're expressing the number n as a product of two factors, which are products of complementary sets of prime-power factors, with as nearly equal numbers of divisors as possible.

A simple example like n = 2^3*3^3 (S1 = {1,2,4,8}; S2 = {1,3,9,27}) might help my feeble brain grasp it...

Last fiddled with by Dr Sardonicus on 2021-10-06 at 18:27 Reason: Fix formatting

2021-10-06, 19:55   #19
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

110001000002 Posts

Quote:
 Originally Posted by Dr Sardonicus A simple example like n = 2^3*3^3 (S1 = {1,2,4,8}; S2 = {1,3,9,27}) might help my feeble brain grasp it...
Say d1=4 from S1 then the divisors that using this d1 is just:
1*d1
3*d1
9*d1
27*d1
for example we are at d=3*d1 and this was the smallest divisor, then the next smallest (using this d1) will be 9*d1, and this is what happens in general you need to move to the next term in S2 [notice that S2 was sorted].

this is what happens in the algorithm:

at the beginning:
the priority queue contains: 1,2,4,8. At the top, the smallest is 1, we pop this, and push to the queue 3*d1=3*1=3.
now in the queue: 3,2,4,8, the smallest is 2, pop this and push 3*d1=3*2=6.
the updated queue: 3,6,4,8 the smallest is 3, pop this and push 9*d1=9*1=9.
the queue: 9,6,4,8 etc.

Say n has roughly 10^7 divisors then the best S1, S2 [in general/average case] contains roughly
sqrt(10^7)~3000 divisors and you can generate quickly the sorted divisors in batches in-fly using only these small S1,S2 sets.

ps.
you don't need a sorted S1.
ofcourse in the queue you need to maintain also the pointers to S2 [and S1] to construct the next numbers at push.
the above 9,6,4,8 is only a list to describe the algorithm; use built-in priority queue/heap or implement that.

 2021-10-08, 16:31 #20 alpertron     Aug 2002 Buenos Aires, Argentina 144710 Posts The algorithm posted to Stack Overflow requires that all the divisors are present in memory. So it is not useful for me. I will show unsorted divisors in my Web application. If the number of divisors is small enough, I will implement Gerbicz's algorithm. But this will be done later.
 2021-10-10, 17:37 #21 alpertron     Aug 2002 Buenos Aires, Argentina 144710 Posts I've just uploaded a new version of the Integer Factorization Calculator that includes the list of divisors. Each batch of 1000 factors is sorted using Heapsort. To show the list of divisors you will need to press the button named Show divisors. If there are more than 1000 divisors, you will see a button named Show more divisors that you will need to press to see the next batch of divisors. Please let me know if you find any error. Last fiddled with by alpertron on 2021-10-10 at 17:37
2021-10-10, 20:05   #22
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

25·72 Posts

Quote:
 Originally Posted by alpertron I've just uploaded a new version of the Integer Factorization Calculator that includes the list of divisors. Each batch of 1000 factors is sorted using Heapsort. To show the list of divisors you will need to press the button named Show divisors. If there are more than 1000 divisors, you will see a button named Show more divisors that you will need to press to see the next batch of divisors. Please let me know if you find any error.
It's nice that you've coded it.
Try it for n=6402373705728000, that is 18!, it is missing a bunch of divisors, the first is 7, as I've looked all of these larger factorials are missing some divisors. Maybe some/all other numbers has also this bug where numdiv(n) or omega(n) is large?

Last fiddled with by R. Gerbicz on 2021-10-10 at 20:06

 Similar Threads Thread Thread Starter Forum Replies Last Post Alberico Lepore Alberico Lepore 1 2020-05-27 12:20 thorken Software 53 2019-01-29 15:34 Brain GPU Computing 20 2015-10-25 18:39 Khemikal796 Factoring 13 2005-04-15 15:21 GP2 Lounge 2 2003-12-03 14:13

All times are UTC. The time now is 01:15.

Sat May 28 01:15:57 UTC 2022 up 43 days, 23:17, 0 users, load averages: 1.72, 1.53, 1.59

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔