Register to reply 
Divisible by a square 
Share this thread: 
#19
Jul3008, 04:34 AM

P: 894




#20
Jul3008, 05:18 AM

P: 61



#21
Jul3008, 11:11 AM

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 nonmembers, 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. 


#22
Jul3008, 12:59 PM

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
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. 


#23
Jul3108, 07:41 AM

Sci Advisor
HW Helper
P: 3,682

Okay, I have the calculations to p_1000, nothing changed (as expected).



#24
Sep1008, 11:03 AM

Sci Advisor
HW Helper
P: 3,682



#25
Sep1108, 02:38 AM

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 [tex](11  1)^{11(2k+1)}[/tex]; you should get a list of multiples of 11^2, plus a final 1. 


#26
Sep1108, 08:54 AM

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, [tex]11^2  10^{11n}[/tex] [tex]7^2  10^{21n}[/tex] [tex]13^2  10^{39n}[/tex] [tex]17^2  10^{136n}[/tex] [tex]19^2  10^{171n}[/tex] [tex]101^2  10^{202n}[/tex] and so on. 


#27
Sep1108, 11:48 AM

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 nonzero, sorted values of A086981, I presume you mean) is more fundamental than, and in some sense "generates", A086982. 


#28
Sep1108, 09:08 PM

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 260digit numbers of special form, but 405digit numbers are about 12,000 times harder. 


Register to reply 
Related Discussions  
Infinitely divisible vs finitely divisible time  General Physics  8  
Numbers divisible by 3  Precalculus Mathematics Homework  8  
(n1)! is divisible by n  Linear & Abstract Algebra  7  
Prove that phi(a^n  1) is divisible by n  Linear & Abstract Algebra  7  
Show that (kn!) is divisible by (n!)^k ?  Calculus & Beyond Homework  7 