Is there a pattern to the values of k for which 10^k+1 is divisible by a square?

[Pere Callahan]

Hi,

I recently became interested in some number theoretical questions. I have actually never really studied it before so my question might be really easy to answer.

I was trying to determine for which values of k the number 10^k+1 is divisible by a square. (http://www.research.att.com/~njas/sequences/A086982" ). The smallest such k is 11 with the corresponding square being 121=11^2. Is it a coincidence that the number 11 occurs twice here? Is there anything more to say about this sequence?

Thanks for any hints or tips on how to start a problem like that.

Pere

 

[Integral]

Even after checking your link I do not understand the sequence. Does the ^ operator have some meaning other then exponentiation?

 

[Pere Callahan]

I will try to it differently. First, the ^ operator means exponentiation in this context.

We consider the sequence
<br /> a_k=10^k+1<br />
with first terms 1,11,101,1001 etc. We are now interested in the factorization of these numbers into primes and form the sequence of those k such that in the factorization of a_k at least one prime factors occurs at least twice.
Is this any clearer?
Thanks

Pere

 

[sagardipak]

Well, answering your question, the 11 plays a special role here. You can easily prove that 10^k+1 is a multiple of 11 for every odd k.

Are you familiar with modular arithmetic? It is very helpful in number theory.

 

[ramsey2879]

Isn't it possible that any odd square not divisible by 5 has a multiplier such that the product would be 10^n + 1?

 

[sagardipak]

Isn't it possible that any odd square not divisible by 5 has a multiplier such that the product would be 10^n + 1?

Are you saying that if n is an odd perfect square, then n divides a number of the form 10^k+1? If so, that is not correct. Take n=9. It will never divide any number of that form. Actually, the division will always have a remainder of 2. Check that ;)

 

[ramsey2879]

Well, answering your question, the 11 plays a special role here. You can easily prove that 10^k+1 is a multiple of 11 for every odd k.

Are you familiar with modular arithmetic? It is very helpful in number theory.

Conjecture, If 10^n + 1 is divisible by a square then 10^{n*(2b + 1)}+1 is also divisible by a square.

This is just my initial conjecture, after attempting to find a link between these values of A082986 and the corresponding square divisors of 10^n +1, I may be able to formulate a proof.

The members of A086982 which are not divisible by any other member thereof may be consider special, they are 11, 21, 39, 136, 171, 202, 243, 292, 406, 548

 

[Hurkyl]

Conjecture, If 10^n + 1 is divisible by a square then 10^{n*(2b + 1)}+1 is also divisible by a square.

That's becuase 10^{n*(2b + 1)}+1 is divisible by 10^n + 1.

 

[ramsey2879]

That's becuase 10^{n*(2b + 1)}+1 is divisible by 10^n + 1.

Actually, I did not specify my conjecture fully, See below

If n is a member of A086982 then J = n*(2m) is not a proper candidate for A086982; but J = n*(2m+1) is since (10^{n} + 1)|(10^{J} + 1) in this case.

This holds for all values given so far for A086982. While the proof of the second part should have been clear to me, there is no clear proof or counterexample of the first part. Again the members of A086982 which are not divisible by any other member thereof may be consider special, they are 11, 21, 39, 136, 171, 202, 243, 292, 406, 548 and certain higher? values ( I'm not sure the list is accurate, i.e. should have been included or exhaustive up thru 548).

 

[ramsey2879]

Actually, I did not specify my conjecture fully, See below

If n is a member of A086982 then J = n*(2m) is not a proper candidate for A086982; but J = n*(2m+1) is since (10^{n} + 1)|(10^{J} + 1) in this case.

This holds for all values given so far for A086982. While the proof of the second part should have been clear to me, there is no clear proof or counterexample of the first part. Again the members of A086982 which are not divisible by any other member thereof may be consider special, they are 11, 21, 39, 136, 171, 202, 243, 292, 406, 548 and certain higher? values ( I'm not sure the list is accurate, i.e. should have been included or exhaustive up thru 548).

I just noticed that 21,136, 171 and 406 are of the form n*(2n+1) and that 11, 39, 202,243,and 548 are either prime , a power of a prime or a non trivial factor of a number of the form n(2n+1) i.e. = n(2n+1)/k where k is a factor of n that is less than n. Also for n = 3 to 16 the only numbers n*(2n+1) for which either such a number or their non trivial factors are not members of A086982 are 4*9, 12*25 and 15*31 the first two have the unique form in that both n and 2n+1 are not square free, the third counter example has uniqueness in that both n and 2n+1 are of the form 2^k + 1. !7*35 looks like a strong candidate for A086982 since no factor thereof is listed as a member.

 

[ramsey2879]

I just noticed that 21,136, 171 and 406 are of the form n*(2n+1) and that 11, 39, 202,243,and 548 are either prime , a power of a prime or a non trivial factor of a number of the form n(2n+1) i.e. = n(2n+1)/k where k is a factor of n that is less than n. Also for n = 3 to 16 the only numbers n*(2n+1) for which either such a number or their non trivial factors are not members of A086982 are 4*9, 12*25 and 15*31 the first two have the unique form in that both n and 2n+1 are not square free, the third counter example has uniqueness in that both n and 2n+1 are of the form 2^k + 1. !7*35 looks like a strong candidate for A086982 since no factor thereof is listed as a member.

I just found that 10^{17*35} + 1 is square free if 54 497020 076810
017716 040927 608557 405847 236264 333227 546750 778971 918214 428885 291202
227775 405113 137115 258841 677550 279903 256040 392380 412335 715412 615161
800428 170614 659594 562308 948027 482104 464988 118707 445963 149192 232300
306040 545218 930623 450732 077479 288238 596378 359205 788267 673107 403311
663394 923771 384430 617482 147227 372985 571814 695405 129822 576204 213241
is square free; see below
10 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000001 = 11 x 103 x 4013 x 9091 x 14281 x 42841 x 87211 x 674731 x 909091 x 4
147571 x 787 223761 x 1868 879293 x 21993 833369 x 265212 793249 617641 x
5673 320472 670315 859129 x 40 410112 822629 936463 361201 x 160 220794
821014 452066 741918 303580 917664 386555 934641 x 103746 647830 421551
242486 430622 636901 002236 971549 990724 717454 338463 x 54 497020 076810
017716 040927 608557 405847 236264 333227 546750 778971 918214 428885 291202
227775 405113 137115 258841 677550 279903 256040 392380 412335 715412 615161
800428 170614 659594 562308 948027 482104 464988 118707 445963 149192 232300
306040 545218 930623 450732 077479 288238 596378 359205 788267 673107 403311
663394 923771 384430 617482 147227 372985 571814 695405 129822 576204 213241
(Composite)

The program has been runnung for 2 hours mostly to factor the latter composite factor.
I don't know how much longer it will take the program to arrive at all prime factors.

 

[Hurkyl]

Actually, I did not specify my conjecture fully...

I just noticed that 21,136, 171 and 406 are of the form n*(2n+1) and that 11, 39, 202,243,and 548 are either prime...

Neither of these posts make sense to me; I can't decipher exactly what you're trying to say.

Incidentally, observe that for any m, if I set n = 2m, then m is a divisor of n(2n+1) satisfying |m| < |n|.

 

[ramsey2879]

Neither of these posts make sense to me; I can't decipher exactly what you're trying to say.

Incidentally, observe that for any m, if I set n = 2m, then m is a divisor of n(2n+1) satisfying |m| < |n|.

It is like Fermat's little theorem where we know that p|m^{p-1} but sometimes p|m^{(p-1)/k}. In my conjecture if k is even then 10^(n*(2n+1)/k) + 1 is not square free while 10^(n(2n+1)) + 1 is, so there is a difference with my conjecture in that respect. The important values of A086982 are n(2n+1) and which factors of those are in the A086982 list and which are not, i.e.
1*3 = 3 no there is no odd prime divisor of n
2*5 = 10 no
3*21 yes
4*9 = 36 no
5*11 = 55 yes
6 * 13 = 78 39 is a member of A086982 but 78 is not
7 * 15 = 105 yes so is 21
8*17 = 136 yes
9 * 19 = 171 yes
10 * 21 = 210 no but 5* 21 is
11 * 23 = 253 yes
12 * 25 = 300 no
13 * 27 = 351 yes so is 39
14 * 29 = 1106 no but 553 is
15 * 31 ?? (I decided to look into this)
16 * 33 no but 33 is
17*35 ??
...
68*137 yes so is 68*137/17 = 548

There are of course many holes in my conjecture but the remarkable fact is that all of the basic members of A086982 (not divisible by another member) but 11 and 243 fit this conjecture.

 

[CRGreathouse]

The program has been runnung for 2 hours mostly to factor the latter composite factor.
I don't know how much longer it will take the program to arrive at all prime factors.

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.

 

[ramsey2879]

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.

Wow In that case I wonder how the sequence A086982 was created in the first place. Checking to see if it is a square would not do since it could be a square multiplied by still another factor. The only apparent method is to factor the number completely. Could it be possible to factor numbers of the form 10^m +1 where m ranges from 5 to 548 in say 10 years because that would seem to be the only way to create the listing of A086982 or are such factorizations already posted somewhere? I am going to take a look at the notes and reference for this sequence.

 

[ramsey2879]

10^{(17*7*5)} +1 = 11*(10^{4} -10^{3} + 10^{2} -10^{1}+1) *
(10^{6} - 10^{5} +10 ^{4} - 10^{3} + 10^{2} - 10 + 1) *
(10^{16} - 10^{15} \dots + 1) =

11 * 9091 * 909091 * 9090909090909091 which can be factored further

 

[CRGreathouse]

Checking to see if it is a square would not do since it could be a square multiplied by still another factor.

If the number has no factors less than its third root, then it is squarefree unless it is a (prime) square. That's why I suggested testing the number to see if it's a square -- though it's not.

 

[CRGreathouse]

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.

 

[ramsey2879]

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]

See discussion here :

http://www.goiit.com/posts/list/algebra-question-by-pidey-76087.htm

 

[CRGreathouse]

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]

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 http://www.research.att.com/~njas/sequences/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]

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

 

[CRGreathouse]

I just sent Sloane a b-file for http://www.research.att.com/~njas/sequences/A086981 .

 

[dodo]

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.

 

[CRGreathouse]

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.

 

[dodo]

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]

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.