Recognitions:
Homework Help

## Divisible by a square

Looking into it a little, I see that nothing more is known than what I posted:

Algorithms in algebraic number theory
 No good algorithms are known for the problem of recognizing squarefree numbers and the problem of finding the largest square dividing a given positive integer, even when the word “good” is given a less formal meaning (see [43, §2]).
The factorization of the ninth Fermat number
 At the moment there are no squarefreeness tests that are essentially faster than factoring[...] There do exist factoring methods that become a little faster if one only wishes to test squarefreeness; for example, if n is not a square which can easily be tested then to determine whether or not n is squarefree it suffices to do a trial division up to n^1/3 instead of n^1/2.

Of course anyone knowing otherwise is encouraged to post.

Blog Entries: 2
 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.
 See discussion here : http://www.goiit.com/posts/list/alge...idey-76087.htm
 Recognitions: Homework Help Science Advisor 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.
 Recognitions: Homework Help Science Advisor 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.
 Recognitions: Homework Help Science Advisor Okay, I have the calculations to p_1000, nothing changed (as expected).
 Recognitions: Homework Help Science Advisor 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.
 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.
 Recognitions: Homework Help Science Advisor 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.
 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.
 Recognitions: Homework Help Science Advisor 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.

 Similar discussions for: Divisible by a square Thread Forum Replies General Physics 8 Precalculus Mathematics Homework 8 Linear & Abstract Algebra 7 Linear & Abstract Algebra 7 Calculus & Beyond Homework 7