mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2021-10-04, 11:21   #12
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

144710 Posts
Default

I asked this problem in another forum and someone pointed to https://stackoverflow.com/questions/...ithout-sorting . I will analyze the solution posted there.
alpertron is offline   Reply With Quote
Old 2021-10-04, 15:29   #13
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

1000110000112 Posts
Default

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
a1call is offline   Reply With Quote
Old 2021-10-04, 15:38   #14
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

25·72 Posts
Default

Quote:
Originally Posted by alpertron View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2021-10-04, 15:56   #15
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

5,791 Posts
Default

Quote:
Originally Posted by alpertron View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2021-10-05, 14:13   #16
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

43038 Posts
Default

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.
a1call is offline   Reply With Quote
Old 2021-10-05, 21:06   #17
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

1,447 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2021-10-06, 18:26   #18
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

5,791 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
<snip>
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.
<snip>
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
Dr Sardonicus is offline   Reply With Quote
Old 2021-10-06, 19:55   #19
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

110001000002 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2021-10-08, 16:31   #20
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

144710 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2021-10-10, 17:37   #21
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

144710 Posts
Default

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
alpertron is offline   Reply With Quote
Old 2021-10-10, 20:05   #22
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

25·72 Posts
Default

Quote:
Originally Posted by alpertron View Post
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
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Phantom factorization - subcubic factorization of integers? Alberico Lepore Alberico Lepore 1 2020-05-27 12:20
MEGAPOST apps to compute mersenne primes, factorization and computing decimals of pi on android thorken Software 53 2019-01-29 15:34
GPU Computing Cheat Sheet (a.k.a. GPU Computing Guide) Brain GPU Computing 20 2015-10-25 18:39
Complete Factorization??? Khemikal796 Factoring 13 2005-04-15 15:21
The difference between P2P and distributed computing and grid computing 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

Powered by vBulletin® Version 3.8.11
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.

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