Register to reply

Divisible by a square

by Pere Callahan
Tags: divisible, square
Share this thread:
ramsey2879
#19
Jul30-08, 04:34 AM
P: 894
Quote Quote by CRGreathouse View Post
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.
spideyunlimit
#20
Jul30-08, 05:18 AM
P: 61
See discussion here :

http://www.goiit.com/posts/list/alge...idey-76087.htm
CRGreathouse
#21
Jul30-08, 11:11 AM
Sci Advisor
HW Helper
P: 3,684
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.
CRGreathouse
#22
Jul30-08, 12:59 PM
Sci Advisor
HW Helper
P: 3,684
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.
CRGreathouse
#23
Jul31-08, 07:41 AM
Sci Advisor
HW Helper
P: 3,684
Okay, I have the calculations to p_1000, nothing changed (as expected).
CRGreathouse
#24
Sep10-08, 11:03 AM
Sci Advisor
HW Helper
P: 3,684
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.
dodo
#25
Sep11-08, 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.
CRGreathouse
#26
Sep11-08, 08:54 AM
Sci Advisor
HW Helper
P: 3,684
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.
dodo
#27
Sep11-08, 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 non-zero, sorted values of A086981, I presume you mean) is more fundamental than, and in some sense "generates", A086982.
CRGreathouse
#28
Sep11-08, 09:08 PM
Sci Advisor
HW Helper
P: 3,684
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.


Register to reply

Related Discussions
Infinitely divisible vs finitely divisible time General Physics 8
Numbers divisible by 3 Precalculus Mathematics Homework 8
(n-1)! 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