[math-fun] Prime factors of 10^N + 1
Decided to list these just for the heck of it. Some amusing almost-patterns for 10^0 + 1 through 10^19 + 1: 1 = 1 11 = 11 101 = 101 1001 = 7 * 11 * 13 10001 = 73 * 137 100001 = 11 * 9091 1000001 = 101 * 9901 10000001 = 11 * 909091 100000001 = 17 * 5882353 1000000001 = 7 * 11 * 13 * 19 * 52579 10000000001 = 101 * 3541 * 27961 100000000001 = 11 * 11 * 23 * 4093 * 8779 1000000000001 = 73 * 137 * 99990001 10000000000001 = 11 * 859 * 1058313049 100000000000001 = 29 * 101 * 281 * 121499449 1000000000000001 = 7 * 11 * 13 * 211 * 241 * 2161 * 9091 10000000000000001 = 353 * 449 * 641 * 1409 * 69857 100000000000000001 = 11 * 103 * 4013 * 21993833369 1000000000000000001 = 101*9901*999999000001 10000000000000000001 = 11*909090909090909091 10^20 + 1 is too large for my software. —Dan
10^20+1=73*137*1676321*5964848081 10^21+1=7^2*11*13*127*2689*459691*909091 Most of these patterns are related to the fact that 10^n+1 is a divisor of (10^(2n)-1). On Mon, Sep 25, 2017 at 3:36 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Decided to list these just for the heck of it.
Some amusing almost-patterns for 10^0 + 1 through 10^19 + 1:
1 = 1
11 = 11
101 = 101
1001 = 7 * 11 * 13
10001 = 73 * 137
100001 = 11 * 9091
1000001 = 101 * 9901
10000001 = 11 * 909091
100000001 = 17 * 5882353
1000000001 = 7 * 11 * 13 * 19 * 52579
10000000001 = 101 * 3541 * 27961
100000000001 = 11 * 11 * 23 * 4093 * 8779
1000000000001 = 73 * 137 * 99990001
10000000000001 = 11 * 859 * 1058313049
100000000000001 = 29 * 101 * 281 * 121499449
1000000000000001 = 7 * 11 * 13 * 211 * 241 * 2161 * 9091
10000000000000001 = 353 * 449 * 641 * 1409 * 69857
100000000000000001 = 11 * 103 * 4013 * 21993833369
1000000000000000001 = 101*9901*999999000001
10000000000000000001 = 11*909090909090909091
10^20 + 1 is too large for my software.
—Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
Hello, here are the factors of 10^n+1 up to n=75 , 1, 11 2, 101 3, 7 11 13 4, 73 137 5, 11 9091 6, 101 9901 7, 11 909091 8, 17 5882353 9, 7 11 13 19 52579 10, 101 3541 27961 11, 11^2 23 4093 8779 12, 73 137 99990001 13, 11 859 1058313049 14, 29 101 281 121499449 15, 7 11 13 211 241 9091 2161 16, 353 449 641 1409 69857 17, 11 103 21993833369 4013 18, 101 999999000001 9901 19, 11 909090909090909091 20, 73 137 1676321 5964848081 21, 7^2 11 13 127 459691 909091 2689 22, 89 101 1052788969 1056689261 23, 11 47 139 549797184491917 2531 24, 17 9999999900000001 5882353 25, 11 251 78875943472201 5051 9091 26, 101 521 1900381976777332243781 27, 7 11 13 19 14175966169 70541929 52579 28, 73 137 127522001020150503761 7841 29, 11 59 154083204930662557781201849 30, 61 101 39526741 4188901 3541 27961 9901 31, 11 909090909090909090909090909091 32, 834427406578561 976193 6187457 19841 33, 7 11^2 13 23 183411838171 599144041 4093 8779 34, 101 2324557465671829 1491383821 28559389 35, 11 265212793249617641 4147571 9091 909091 36, 73 137 3199044596370769 99990001 98641 3169 37, 11 422650073734453 296557347313446299 7253 38, 101 722817036322379041 1369778187490592461 39, 7 11 13^2 157 859 388847808493 1058313049 216451 6397 40, 17 19721061166646717498359681 5070721 5882353 41, 11 2670502781396266997 3404193829806058997303 42, 29 101 281 4458192223320340849 121499449 226549 9901 43, 11 2182600451 7306116556571817748755241 57009401 44, 73 137 617 16205834846012967584927082656402106953 45, 7 11 13 19 211 241 3762091 8985695684401 9091 52579 29611 2161 46, 101 1289 18371524594609 4181003300071669867932658901 47, 11 4855067598095567 297262705009139006771611927 6299 48, 97 353 449 641 1409 75118313082913 66554101249 69857 206209 49, 11 197 5076141624365532994918781726395939035533 909091 50, 101 14103673319201 1680588011350901 7019801 60101 3541 27961 51, 7 11 13 103 21993833369 291078844423 377526955309799110357 4013 52, 73 137 632527440202150745090622412245443923049201 1580801 53, 11 9090909090909090909090909090909090909090909090909091 54, 101 109 59779577156334533866654838281 999999000001 153469 9901 55, 11^2 23 331 20163494891 318727841165674579776721 9091 4093 5171 8779 56, 17 113 73765755896403138401 119968369144846370226083377 5882353 57, 7 11 13 909090909090909091 753201806271328462547977919407 1458973 58, 101 349 11811806375201836408679635736258669583187541 38861 618049 59, 11 1090805842068098677837 4411922770996074109644535362851087 1889 60, 73 137 1676321 100009999999899989999000000010001 5964848081 99990001 61, 11 11205222530116836855321528257890437575145023592596037161 81131 62, 101 483128549554512237305554588359039822397307149685578249 2049349 63, 7^2 11 13 19 127 5274739 189772422673235585874485732659 459691 52579 909091 2689 64, 15343168188889137818369 515217525265213267447869906815873 1265011073 65, 11 131 859 8396862596258693901610602298557167100076327481 1058313049 9091 66, 89 101 1052788969 789390798020221 1056689261 2361000305507449 5419170769 9901 67, 11 909090909090909090909090909090909090909090909090909090909090909091 68, 73 137 65552746171882583264230070868884366877803237222654400793 152533657 69, 7 11 13 47 139 143574021480139 549797184491917 24649445347649059192745899 31051 2531 70, 29 101 281 421 60368344121 848654483879497562821 121499449 13489841 3541 27961 3471301 71, 11 31321069464181068355415209323405389541706979493156189716729115659 290249 72, 17 111994624258035614290513943330720125433979169 9999999900000001 5882353 8929 73, 11 293 10826684964539959837294043117 286578888976194997999922592330908602103011 74, 101 149 669031686661427842829 708840373781 40548140514062774758071840361 111149 3109 75, 7 11 13 211 241 251 78875943472201 10000099999999989999899999000000000100001 5051 9091 2161 and to continue, use pari-gp or mathematica, this is what was done on Maple in reasonable time. (in raw format up to 80), 76, ``(73)*``(137)*``(457)*``(5240808656722481737)*``(297478330786365628414805305290302483555043017)*``(1403417) 77, ``(11)^2*``(23)*``(463)*``(4539402627853030477)*``(4924630160315726207887)*``(7444361)*``(24179)*``(590437)*``(4093)*``(8779)*``(909091) 78, ``(101)*``(521)*``(6060517860310398033985611921721)*``(53397071018461)*``(1900381976777332243781)*``(9901)*``(3121) 79, ``(11)*``(1423)*``(9615060929)*``(66443174541490579097997510158021076958392938976011506949065646573) 80, ``(353)*``(449)*``(641)*``(1409)*``(947147262401)*``(349954396040122577928041596214187605761)*``(18453761)*``(69857)*``(1634881) Best regards, Simon Plouffe
Maybe I meant "familiar" rather than "related". Consider: 1/7 = 0.142857 (repeating) = 142857/999999 so 999999 must be divisible by 7. Taking the 9's out leaves 111111, and then we can take out 111 leaving 1001, so 1001 is divisible by 7. This can also be done just by saying 999999 is 10^6-1 = (10^3-1)(10^3+1), where that last is of the form you are interested in. Ultimately Euler's theorem (a^phi(n)=1 mod n) is the root of many of the divisibility results. For n=7, phi(n)=6, so 10^6=1 mod 7, so 10^6-1 divides 7, and this is (10^3+1)(10^3-1). So the repeating small primes (11 every second value, 7 every third, etc.) can be seen more or less directly, since if 10^phi(n) == 1 (mod n), so does 10^(k phi(n)) for positive integer k. Patterns in factors such as 99990001 are just arithmetic tricks (what do I need to multiply 10001 by to get 1000000000001) visible in some primes. In this case it is 10^8 - 10^4 + 1 which shows up as those repeated 9's and 0's. -tom On Mon, Sep 25, 2017 at 4:43 PM, James Davis <lorentztrans@gmail.com> wrote:
Most of these patterns are related to the fact that 10^n+1 is a divisor of (10^(2n)-1).
I've played with these, but I don't understand - why is 10^+1 being a divisor of 10^(2n)-1 related?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
Thanks! That saves me a week.
Consider: 1/7 = 0.142857 (repeating) = 142857/999999 so 999999 must be divisible by 7. Taking the 9's out leaves 111111, and then we can take out 111 leaving 1001, so 1001 is divisible by 7. This can also be done just by saying 999999 is 10^6-1 = (10^3-1)(10^3+1), where that last is of the form you are interested in.
Ultimately Euler's theorem (a^phi(n)=1 mod n) is the root of many of the divisibility results. For n=7, phi(n)=6, so 10^6=1 mod 7, so 10^6-1 divides 7, and this is (10^3+1)(10^3-1). So the repeating small primes (11 every second value, 7 every third, etc.) can be seen more or less directly, since if 10^phi(n) == 1 (mod n), so does 10^(k phi(n)) for positive integer k.
Patterns in factors such as 99990001 are just arithmetic tricks (what do I need to multiply 10001 by to get 1000000000001) visible in some primes. In this case it is 10^8 - 10^4 + 1 which shows up as those repeated 9's and 0's.
-tom
On Sep 25, 2017, at 5:30 PM, James Davis <lorentztrans@gmail.com> wrote:
Thanks! That saves me a week.
Then perhaps I can waste you some more time? So square-free, the exceptions pop out! By eyeball it seems like 11^2 is a divisor when n = an odd multiple of 11. And 7^2 divides n=21 and 63, and there's even a 13^2 for n=39 (no doubt all these are related to n=3 being 7 11 13?) What is the smallest n divisible by a cube? By two distinct squares? By any square that's relatively prime to 1001?
The Cunningham Project seeks to factor the numbers b^n +- 1 for b = 2, 3, 5, 6, 7, 10, 11, 12, up to high powers n. The Cunningham tables are the tables in the book *"Factorizations of b^n +- 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers,*" by John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff, Jr., American Mathematical Society, Providence, Rhode Island, third edition, 2002. Although the first two editions were published as paper books, the third edition is an electronic book available at http://www.ams.org/books/conm/022/ . On Mon, Sep 25, 2017 at 9:27 PM, Marc LeBrun <mlb@well.com> wrote:
On Sep 25, 2017, at 5:30 PM, James Davis <lorentztrans@gmail.com> wrote:
Thanks! That saves me a week.
Then perhaps I can waste you some more time?
So square-free, the exceptions pop out! By eyeball it seems like 11^2 is a divisor when n = an odd multiple of 11.
And 7^2 divides n=21 and 63, and there's even a 13^2 for n=39 (no doubt all these are related to n=3 being 7 11 13?)
What is the smallest n divisible by a cube? By two distinct squares? By any square that's relatively prime to 1001?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 2017-09-25 16:43, James Davis wrote:
Most of these patterns are related to the fact that 10^n+1 is a divisor of (10^(2n)-1).
I've played with these, but I don't understand - why is 10^+1 being a divisor of 10^(2n)-1 related?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Because it's a step in showing that if {x} is the set of prime divisors of 10^n + 1, they are also divisors of 10^((2k+1)n) + 1 for all k. If X = product{x} divides 10^{(2k+1)n} + 1, it also divides 10^{(2k+3)n} + 1, because: ( 10^{(2k+1)n} + 1 ) * (10^{2n} - 1 ) is divisible by X, and = 10^{(2k+3)n} + 1 - (10^{2n} - 1) - ( 10^{(2k+1)n} + 1 ). ( X divides 10^{2n} - 1 and (by assumption) 10^{(2k+1)n} + 1, so it must also divide 10^{(2k+3)n} + 1 ) So the factors of 10^2 + 1 should show up at n=2, 6, 10, 14 etc. The factors of 10^3 should show up at n=3, 9, 15, 21, etc. etc.
On 2017-09-25 17:13, Michael Greenwald wrote:
On 2017-09-25 16:43, James Davis wrote:
Most of these patterns are related to the fact that 10^n+1 is a divisor of (10^(2n)-1).
I've played with these, but I don't understand - why is 10^+1 being a divisor of 10^(2n)-1 related?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Because it's a step in showing that if {x} is the set of prime divisors of 10^n + 1, they are also divisors of 10^((2k+1)n) + 1 for all k.
If X = product{x} divides 10^{(2k+1)n} + 1, it also divides 10^{(2k+3)n} + 1, because: ( 10^{(2k+1)n} + 1 ) * (10^{2n} - 1 ) is divisible by X, and = 10^{(2k+3)n} + 1 - (10^{2n} - 1) - ( 10^{(2k+1)n} + 1 ). ( X divides 10^{2n} - 1 and (by assumption) 10^{(2k+1)n} + 1, so it must also divide 10^{(2k+3)n} + 1 )
So the factors of 10^2 + 1 should show up at n=2, 6, 10, 14 etc. The factors of 10^3 should show up at n=3, 9, 15, 21, etc. etc.
Never mind: I misunderstood what you were asking, and I answered a much simpler, and much less interesting question than Tom Rokicki answered.
10^20 + 1 is too large for my software
Forget your computer software for this kind of stuff. The website factordb.com is a factor database. http://factordb.com/index.php?query=10%5En%2B1&use=n&n=1&VP=on&VC=on&EV=on&O... That's 10^n+1 up to n=200. Click "next page" to get the next 200. Note that n=311 is the first one that still has an unfactored composite.
participants (8)
-
Dan Asimov -
Hans Havermann -
James Davis -
Marc LeBrun -
Michael Greenwald -
Simon Plouffe -
Tomas Rokicki -
W. Edwin Clark