# Divisible by a square

by Pere Callahan
Tags: divisible, square
P: 894
 Quote by CRGreathouse 1. You're trying to factor a 344-digit number. This could take longer than your lifetime. 2. It looks like you're using the alpertron ECM applet. ECM is good at finding small factors and bad at finding large factors. 3. You don't need to search for all factors; checking if the number is a square and searching up to the sixth root would suffice. Of course there's no good way to do that (since the sixth root is about 2e57); even ECMing to a good degree of confidence would be too time-consuming.
Yes I am using the ECM applet. I have a couple of question I assumed that every factor listed has been checked as a divisor of the last composite factor, but maybe I am not correct. If, supposing that the program factored 10^565 + 1 algebraically then individually factored each of these components, would it check all factors of the factored components as a factor of the other components before continuing on with the factoring routine? If not then maybe I should enter the larger known factors for testing as a factor of the unfactored expression. Two apparently there are numbers known as Cunningham numbers which tend to be factors of the form A^n + 1. I see that the applet has automatically check the box to try these factors as I entered 10^595 + 1 as the expression to factor. How many of the factors listed by the applet in my case as prime factors are known as Cunningham factors? Obviously there is no need to worry that those haven't been checked as a factor of the unfactored component.
 P: 61 See discussion here : http://www.goiit.com/posts/list/alge...idey-76087.htm
 Sci Advisor HW Helper P: 3,682 Well, I still have no idea on how to rigorously prove that large numbers are not in the sequence. But I can distinguish members from non-members, even at reasonably large sizes, to high confidence. This stems from the idea that divisibility by large squares is rare. All of the members on the OEIS so far: 11, 21, 33, 39, 55, 63, 77, 99, 105, 117, 121, 136, 143, 147, 165, 171, 187, 189, 195, 202, 209, 231, 243, 253, 273, 275, 292, 297, 315, 319, 341, 351, 357, 363, 385, 399, 406, 407, 408, 429, 441, 451, 473, 483, 495, 507, 513, 517, 525, 539, 548, 561, 567 are there because of a small factor: in particular, p^2 | (10^a(n) + 1) for 10 < p < 488 for each entry a(n) on the above list. So I can just test for divisibility by small prime squares. Let's say I use the first 400 prime squares. The chance that a 'random' number is divisible by one of these prime squares is 39.20481419896...% and the change that a 'random' number is divisible by any prime square is 39.20728981459...% giving the chance that a 'random' number is divisible by a larger prime square as 0.00407205867...% and the chance that a 'random' number is divisible by a larger prime square, but not one on the list, as 0.00247561563...% So checking for divisibility by the first 400 primes gives 99.997% confidence for membership on the list.
 Sci Advisor HW Helper P: 3,682 Of course making a list decreases certainty dramatically (raising it to the power of the size of the list). Thus calculating the values of A086982 up to 7000 (plus checking small members, remembering that uncertainty comes only from *skipped* elements) requires about 1000 primes at 95% confidence. This will probably take 10 hours of preprocessing (and negligible time after that). So here's my preliminary list for A086982 up to 7000: 11, 21, 33, 39, 55, 63, 77, 99, 105, 117, 121, 136, 143, 147, 165, 171, 187, 189, 195, 202, 209, 231, 243, 253, 273, 275, 292, 297, 315, 319, 341, 351, 357, 363, 385, 399, 406, 407, 408, 429, 441, 451, 473, 483, 495, 507, 513, 517, 525, 539, 548, 561, 567, 583, 585, 605, 606, 609, 627, 649, 651, 663, 671, 680, 693, 715, 729, 735, 737, 741, 759, 777, 781, 803, 819, 825, 847, 855, 861, 869, 876, 891, 897, 903, 913, 935, 945, 952, 957, 975, 979, 987, 1001, 1010, 1023, 1029, 1045, 1053, 1067, 1071, 1081, 1089, 1111, 1113, 1131, 1133, 1155, 1177, 1197, 1199, 1209, 1215, 1218, 1221, 1224, 1239, 1243, 1265, 1281, 1287, 1309, 1323, 1331, 1353, 1365, 1375, 1397, 1407, 1414, 1419, 1441, 1443, 1449, 1460, 1463, 1485, 1491, 1496, 1507, 1521, 1529, 1533, 1539, 1551, 1573, 1575, 1595, 1599, 1617, 1639, 1644, 1659, 1661, 1677, 1683, 1701, 1705, 1711, 1727, 1743, 1749, 1751, 1755, 1768, 1771, 1785, 1793, 1815, 1818, 1827, 1830, 1833, 1837, 1859, 1869, 1881, 1903, 1911, 1925, 1947, 1953, 1958, 1969, 1989, 1991, 1995, 2013, 2030, 2035, 2037, 2040, 2044, 2057, 2067, 2079, 2101, 2121, 2123, 2145, 2163, 2167, 2187, 2189, 2205, 2211, 2222, 2223, 2233, 2247, 2255, 2277, 2289, 2299, 2301, 2312, 2321, 2331, 2343, 2365, 2373, 2379, 2387, 2409, 2415, 2431, 2453, 2457, 2475, 2497, 2499, 2519, 2535, 2541, 2563, 2565, 2583, 2584, 2585, 2607, 2613, 2625, 2626, 2628, 2629, 2651, 2667, 2673, 2691, 2695, 2709, 2717, 2739, 2740, 2751, 2761, 2769, 2783, 2793, 2805, 2827, 2835, 2842, 2847, 2849, 2856, 2871, 2877, 2893, 2907, 2915, 2919, 2925, 2937, 2959, 2961, 2981, 3003, 3025, 3030, 3045, 3047, 3069, 3081, 3087, 3091, 3113, 3128, 3129, 3135, 3157, 3159, 3165, 3171, 3179, 3197, 3201, 3212, 3213, 3223, 3237, 3243, 3245, 3249, 3255, 3267, 3289, 3297, 3311, 3315, 3333, 3339, 3355, 3377, 3381, 3393, 3399, 3400, 3421, 3423, 3434, 3443, 3465, 3471, 3487, 3507, 3509, 3531, 3549, 3553, 3575, 3591, 3597, 3615, 3619, 3627, 3633, 3641, 3645, 3654, 3663, 3672, 3675, 3685, 3705, 3707, 3717, 3729, 3751, 3759, 3773, 3783, 3795, 3796, 3801, 3817, 3836, 3838, 3839, 3843, 3861, 3883, 3885, 3905, 3927, 3933, 3934, 3939, 3944, 3949, 3969, 3971, 3993, 4011, 4015, 4017, 4037, 4053, 4059, 4081, 4095, 4103, 4125, 4131, 4137, 4147, 4169, 4173, 4179, 4191, 4213, 4216, 4221, 4235, 4242, 4251, 4257, 4263, 4275, 4279, 4301, 4305, 4323, 4329, 4345, 4347, 4367, 4380, 4389, 4407, 4411, 4431, 4433, 4455, 4466, 4473, 4477, 4485, 4488, 4499, 4515, 4521, 4543, 4557, 4563, 4565, 4587, 4599, 4609, 4617, 4631, 4641, 4646, 4653, 4656, 4675, 4683, 4697, 4719, 4725, 4741, 4760, 4763, 4767, 4785, 4797, 4807, 4809, 4829, 4851, 4873, 4875, 4893, 4895, 4917, 4932, 4935, 4939, 4953, 4959, 4961, 4964, 4977, 4983, 5005, 5019, 5027, 5031, 5032, 5049, 5050, 5061, 5071, 5093, 5103, 5109, 5115, 5133, 5137, 5145, 5159, 5181, 5187, 5203, 5225, 5229, 5247, 5253, 5265, 5269, 5271, 5278, 5291, 5301, 5304, 5313, 5335, 5343, 5355, 5357, 5379, 5397, 5401, 5405, 5421, 5423, 5439, 5445, 5454, 5467, 5481, 5489, 5490, 5499, 5511, 5523, 5533, 5548, 5555, 5565, 5576, 5577, 5589, 5599, 5607, 5621, 5643, 5648, 5649, 5655, 5665, 5687, 5691, 5709, 5731, 5733, 5753, 5775, 5797, 5811, 5817, 5819, 5841, 5848, 5858, 5859, 5863, 5874, 5885, 5886, 5889, 5901, 5907, 5929, 5943, 5951, 5967, 5973, 5985, 5995, 6017, 6027, 6028, 6039, 6045, 6061, 6069, 6075, 6083, 6090, 6105, 6111, 6120, 6123, 6127, 6132, 6149, 6153, 6171, 6193, 6195, 6201, 6215, 6237, 6259, 6262, 6275, 6279, 6281, 6303, 6321, 6325, 6327, 6328, 6347, 6357, 6363, 6369, 6391, 6392, 6405, 6413, 6435, 6447, 6457, 6479, 6489, 6501, 6513, 6523, 6531, 6545, 6561, 6567, 6573, 6589, 6591, 6611, 6615, 6633, 6655, 6657, 6664, 6666, 6669, 6677, 6699, 6716, 6721, 6741, 6743, 6747, 6765, 6783, 6787, 6809, 6825, 6831, 6853, 6867, 6875, 6897, 6902, 6903, 6909, 6919, 6936, 6941, 6951, 6963, 6981, 6985, 6993 This list is not certain, because It's based on the assumption that 10^n+1 is not divisible by a large prime square for any n < 7000 off this list (~95% confidence) My calculations to p_1000 = 7919 are not done yet (> 93% confidence) Both are based on the heuristic that the numbers 'behave randomly'. The latter is based on much shakier assumptions, but won't be an issue once the calculations are complete.
 Sci Advisor HW Helper P: 3,682 Okay, I have the calculations to p_1000, nothing changed (as expected).
 Sci Advisor HW Helper P: 3,682 I just sent Sloane a b-file for A086981, the sequence which creates this sequence. The next 3000 terms had nothing that would change what I posted; in fact the smallest entry in the range 1001-4000 was A086981(1128) = 45455. This means that 45455, 3 * 45455, 5 * 45455, etc. are all in A086982.
 P: 688 The ignorant comment of the day: All odd multiples of 11 (and a few random even ones) appear to be there. Edit: Hmm, I think I see. Try to evaluate the binomial $$(11 - 1)^{11(2k+1)}$$; you should get a list of multiples of 11^2, plus a final -1.
 Sci Advisor HW Helper P: 3,682 The sequence includes all odd multiples of {11, 21, 39, 136, 171, 202, 243, 253, 292, 406, 548, 1081, 1711, 1751, 1830, 1958, 2667, 3165, 3197, 3615, 3934, 4656, 5648, 5886, 6123, 6275, 6328, 7184, 8515, 9653, 10256, 11026, 11167, 13546, 13861, 15931, 16290, 18205, 18528, 20242, 21389, 22544, 24753, 26106, 27028, 27148, 29470, 32415, 32896, 34453, 34689, 34732, 35410, 35651, 36046, 40100, 41718, 45023, 45455, ...}. For odd n, $$11^2 | 10^{11n}$$ $$7^2 | 10^{21n}$$ $$13^2 | 10^{39n}$$ $$17^2 | 10^{136n}$$ $$19^2 | 10^{171n}$$ $$101^2 | 10^{202n}$$ and so on.
 P: 688 Is there a number in A086982 such that: - It is not an odd multiple of a previous member, and - Any of its odd multiples is not in A086982? (Actually only the second condition is relevant, the first is rather cosmetic. For example, all the odd multiples of 33 are in the sequence, since all the odd multiples of 11 are.) If there is none, it would appear that the list in post #26 (the non-zero, sorted values of A086981, I presume you mean) is more fundamental than, and in some sense "generates", A086982.
 Sci Advisor HW Helper P: 3,682 Is A086982 precisely the odd multiples of the nonzero values of A086981? Yes. But careful. I don't know that my list is the start of the sorted list of the nonzero members of A086981 (though I think it is). There could be a prime square dividing 10^k+1 for a fairly small k. I've only searched for divisibility by primes up to 40,000 or so (thus prime squares up to 1.6 billion) so technically I only know that 1 to 9 are not on the list. Hmm. 10^k+1 can't be a prime square by Mihăilescu's theorem (otherwise 10^k and 10^k+1 would be consecutive powers). It can't be 2, 3, or 5 times a prime square since it's 1 mod 2, 2 mod 3, and 1 mod 5. So at worst it is 7 times a prime square. Actually, since primes (greater than 5) are 1, 3, 7, or 9 mod 10, prime squares are 1 or 9 mod 10. Thus 7 times a prime square would be 3 or 7 mod 10, which is right out. 11 times a prime square, though... still a possibility, for all I know. So I haven't missed anything up to 17.6 billion, which is more than 10^10, so I know that 11 is the first member of the list. Of course for the small entries we could just factor 10^k+1 directly. It might be practical to go to k = 200 or so, proving the first five members of the sequence. (I think I did this already.) But proving the first ten seems far out of reach with current SNFS technology. msieve has factored 260-digit numbers of special form, but 405-digit numbers are about 12,000 times harder.

 Related Discussions General Physics 8 Precalculus Mathematics Homework 8 Linear & Abstract Algebra 7 Linear & Abstract Algebra 7 Calculus & Beyond Homework 7