Re: [math-fun] mersenne primes and their multiples
Cris Moore <moore@santafe.edu> wrote:
I was wondering what primes can occur as factors of ?sparse? integers, i.e. those with only a few 1s in their binary expansion.
How few is few? I looked at 21-bit numbers with three or fewer one-bits. Zero one-bits of course only gives me zero. One one-bit gives me powers of two, whose only prime factor is two. Two one-bits is where it gets interesting. I only looked at numbers whose rightmost bit is one, since all others are equal to such a number times some power of two. Here are the prime factors of the two-one-bit numbers: 3: 3 5: 5 9: 3^2 17: 17 33: 3 11 65: 5 13 129: 3 43 257: 257 513: 3^3 19 1025: 5^2 41 2049: 3 683 4097: 17 241 8193: 3 2731 16385: 5 29 113 32769: 3^2 11 331 65537: 65537 131073: 3 43691 262145: 5 13 37 109 524289: 3 174763 1048577: 17 61681 Every other one is divisible by three. Every fourth one is divisible by five. None are divisible by seven. Do all primes that ever appear appear at regular intervals? Here are the prime factors of the three-one-bit numbers: 7: 7 11: 11 13: 13 19: 19 21: 3 7 25: 5^2 35: 5 7 37: 37 41: 41 49: 7^2 67: 67 69: 3 23 73: 73 81: 3^4 97: 97 131: 131 133: 7 19 137: 137 145: 5 29 161: 7 23 193: 193 259: 7 37 261: 3^2 29 265: 5 53 273: 3 7 13 289: 17^2 321: 3 107 385: 5 7 11 515: 5 103 517: 11 47 521: 521 529: 23^2 545: 5 109 577: 577 641: 641 769: 769 1027: 13 79 1029: 3 7^3 1033: 1033 1041: 3 347 1057: 7 151 1089: 3^2 11^2 1153: 1153 1281: 3 7 61 1537: 29 53 2051: 7 293 2053: 2053 2057: 11^2 17 2065: 5 7 59 2081: 2081 2113: 2113 2177: 7 311 2305: 5 461 2561: 13 197 3073: 7 439 4099: 4099 4101: 3 1367 4105: 5 821 4113: 3^2 457 4129: 4129 4161: 3 19 73 4225: 5^2 13^2 4353: 3 1451 4609: 11 419 5121: 3^2 569 6145: 5 1229 8195: 5 11 149 8197: 7 1171 8201: 59 139 8209: 8209 8225: 5^2 7 47 8257: 23 359 8321: 53 157 8449: 7 17 71 8705: 5 1741 9217: 13 709 10241: 7^2 11 19 12289: 12289 16387: 7 2341 16389: 3^3 607 16393: 13^2 97 16401: 3 7 11 71 16417: 16417 16449: 3 5483 16513: 7^2 337 16641: 3^2 43^2 16897: 61 277 17409: 3 7 829 18433: 18433 20481: 3 6827 24577: 7 3511 32771: 32771 32773: 13 2521 32777: 73 449 32785: 5 79 83 32801: 32801 32833: 32833 32897: 67 491 33025: 5^2 1321 33281: 23 1447 33793: 47 719 34817: 37 941 36865: 5 73 101 40961: 40961 49153: 13 19 199 65539: 65539 65541: 3 7 3121 65545: 5 13109 65553: 3 21851 65569: 7 17 19 29 65601: 3^2 37 197 65665: 5 23 571 65793: 3 7 13 241 66049: 257^2 66561: 3 11 2017 67585: 5 7 1931 69633: 3^3 2579 73729: 17 4337 81921: 3 7 47 83 98305: 5 19661 131075: 5^2 7^2 107 131077: 23 41 139 131081: 19 6899 131089: 7 61 307 131105: 5 13 2017 131137: 71 1847 131201: 7 18743 131329: 11 11939 131585: 5 26317 132097: 7 113 167 133121: 133121 135169: 29 59 79 139265: 5 7 23 173 147457: 147457 163841: 163841 196609: 7 28087 262147: 262147 262149: 3 87383 262153: 262153 262161: 3^2 29129 262177: 23 11399 262209: 3 87403 262273: 11 113 211 262401: 3 47 1861 262657: 262657 263169: 3^6 19^2 264193: 349 757 266241: 3 88747 270337: 270337 278529: 3 227 409 294913: 41 7193 327681: 3^2 23 1583 393217: 11 35747 524291: 29 101 179 524293: 7 11^2 619 524297: 17 30841 524305: 5 19 5519 524321: 7 74903 524353: 524353 524417: 61 8597 524545: 5 7^2 2141 524801: 524801 525313: 525313 526337: 7 17 4423 528385: 5 11 13 739 532481: 647 823 540673: 7 77239 557057: 557057 589825: 5^2 23593 655361: 7 251 373 786433: 786433 1048579: 7 163 919 1048581: 3^2 263 443 1048585: 5 209717 1048593: 3 7 13 23 167 1048609: 1048609 1048641: 3 11 43 739 1048705: 5 7 19^2 83 1048833: 3^2 116537 1049089: 1049089 1049601: 3 7 151 331 1050625: 5^4 41^2 1052673: 3 350891 1056769: 7 150967 1064961: 3^3 39443 1081345: 5 23 9403 1114113: 3 7^2 11 13 53 1179649: 1179649 1310721: 3 67 6521 1572865: 5 7 44939 The first few primes that don't appear are 31, 89, and 127, two of which are Mersenne primes. (Well, okay, 2 never appears, but only because I skipped all even numbers.)
Contrapositively speaking, you might enjoy proving the following: any multiple of the Mersenne prime 2^k-1 has at least k 1s.
Every number in the form 2^k-1, whether prime or not, consists of k adjacent one-bits. Whenever you multiply such a number by anything, you are adding shifted versions of that string of k adjacent one-bits. Due to carries, that results in a sequence of one-bits over all of the overlap region except the rightmost bit of the overlap. You also get one one-bit for each bit to the right of the overlap. And due to carries, you get at least one one-bit to the left of the overlap. So that totals at least k one-bits.
For the first list, the two-one-bit primes that are divisible by three have the form 2^(2*k+1) + 1, which is just 2*(4^k) + 1. Since 4 = 1 (mod 3), all powers of 4 are 1 (mod 3), so twice a power of 4 is 2 (mod 3), and adding 1 produces 0 (mod 3). Similarly, the ones that are divisible by five have the form 2^(4*k + 2) + 1, which is just 4*(16^k) + 1. Since 16 = 1 (mod 5), all powers of 16 are 1 (mod 5), so four times a power of 16 is 4 (mod 5), and adding 1 produces 0 (mod 5). Other such patterns exist. For instance, 16*(256^k) + 1 is always a multiuple of 17, 10*(1024^k) + 1 is always a multiple of 11, etc. Tom Keith F. Lynch writes:
Cris Moore <moore@santafe.edu> wrote:
I was wondering what primes can occur as factors of ?sparse? integers, i.e. those with only a few 1s in their binary expansion.
How few is few?
I looked at 21-bit numbers with three or fewer one-bits. Zero one-bits of course only gives me zero. One one-bit gives me powers of two, whose only prime factor is two. Two one-bits is where it gets interesting. I only looked at numbers whose rightmost bit is one, since all others are equal to such a number times some power of two. Here are the prime factors of the two-one-bit numbers:
3: 3 5: 5 9: 3^2 17: 17 33: 3 11 65: 5 13 129: 3 43 257: 257 513: 3^3 19 1025: 5^2 41 2049: 3 683 4097: 17 241 8193: 3 2731 16385: 5 29 113 32769: 3^2 11 331 65537: 65537 131073: 3 43691 262145: 5 13 37 109 524289: 3 174763 1048577: 17 61681
Every other one is divisible by three. Every fourth one is divisible by five. None are divisible by seven. Do all primes that ever appear appear at regular intervals?
Here are the prime factors of the three-one-bit numbers:
7: 7 11: 11 13: 13 19: 19 21: 3 7 25: 5^2 35: 5 7 37: 37 41: 41 49: 7^2 67: 67 69: 3 23 73: 73 81: 3^4 97: 97 131: 131 133: 7 19 137: 137 145: 5 29 161: 7 23 193: 193 259: 7 37 261: 3^2 29 265: 5 53 273: 3 7 13 289: 17^2 321: 3 107 385: 5 7 11 515: 5 103 517: 11 47 521: 521 529: 23^2 545: 5 109 577: 577 641: 641 769: 769 1027: 13 79 1029: 3 7^3 1033: 1033 1041: 3 347 1057: 7 151 1089: 3^2 11^2 1153: 1153 1281: 3 7 61 1537: 29 53 2051: 7 293 2053: 2053 2057: 11^2 17 2065: 5 7 59 2081: 2081 2113: 2113 2177: 7 311 2305: 5 461 2561: 13 197 3073: 7 439 4099: 4099 4101: 3 1367 4105: 5 821 4113: 3^2 457 4129: 4129 4161: 3 19 73 4225: 5^2 13^2 4353: 3 1451 4609: 11 419 5121: 3^2 569 6145: 5 1229 8195: 5 11 149 8197: 7 1171 8201: 59 139 8209: 8209 8225: 5^2 7 47 8257: 23 359 8321: 53 157 8449: 7 17 71 8705: 5 1741 9217: 13 709 10241: 7^2 11 19 12289: 12289 16387: 7 2341 16389: 3^3 607 16393: 13^2 97 16401: 3 7 11 71 16417: 16417 16449: 3 5483 16513: 7^2 337 16641: 3^2 43^2 16897: 61 277 17409: 3 7 829 18433: 18433 20481: 3 6827 24577: 7 3511 32771: 32771 32773: 13 2521 32777: 73 449 32785: 5 79 83 32801: 32801 32833: 32833 32897: 67 491 33025: 5^2 1321 33281: 23 1447 33793: 47 719 34817: 37 941 36865: 5 73 101 40961: 40961 49153: 13 19 199 65539: 65539 65541: 3 7 3121 65545: 5 13109 65553: 3 21851 65569: 7 17 19 29 65601: 3^2 37 197 65665: 5 23 571 65793: 3 7 13 241 66049: 257^2 66561: 3 11 2017 67585: 5 7 1931 69633: 3^3 2579 73729: 17 4337 81921: 3 7 47 83 98305: 5 19661 131075: 5^2 7^2 107 131077: 23 41 139 131081: 19 6899 131089: 7 61 307 131105: 5 13 2017 131137: 71 1847 131201: 7 18743 131329: 11 11939 131585: 5 26317 132097: 7 113 167 133121: 133121 135169: 29 59 79 139265: 5 7 23 173 147457: 147457 163841: 163841 196609: 7 28087 262147: 262147 262149: 3 87383 262153: 262153 262161: 3^2 29129 262177: 23 11399 262209: 3 87403 262273: 11 113 211 262401: 3 47 1861 262657: 262657 263169: 3^6 19^2 264193: 349 757 266241: 3 88747 270337: 270337 278529: 3 227 409 294913: 41 7193 327681: 3^2 23 1583 393217: 11 35747 524291: 29 101 179 524293: 7 11^2 619 524297: 17 30841 524305: 5 19 5519 524321: 7 74903 524353: 524353 524417: 61 8597 524545: 5 7^2 2141 524801: 524801 525313: 525313 526337: 7 17 4423 528385: 5 11 13 739 532481: 647 823 540673: 7 77239 557057: 557057 589825: 5^2 23593 655361: 7 251 373 786433: 786433 1048579: 7 163 919 1048581: 3^2 263 443 1048585: 5 209717 1048593: 3 7 13 23 167 1048609: 1048609 1048641: 3 11 43 739 1048705: 5 7 19^2 83 1048833: 3^2 116537 1049089: 1049089 1049601: 3 7 151 331 1050625: 5^4 41^2 1052673: 3 350891 1056769: 7 150967 1064961: 3^3 39443 1081345: 5 23 9403 1114113: 3 7^2 11 13 53 1179649: 1179649 1310721: 3 67 6521 1572865: 5 7 44939
The first few primes that don't appear are 31, 89, and 127, two of which are Mersenne primes. (Well, okay, 2 never appears, but only because I skipped all even numbers.)
Contrapositively speaking, you might enjoy proving the following: any multiple of the Mersenne prime 2^k-1 has at least k 1s.
Every number in the form 2^k-1, whether prime or not, consists of k adjacent one-bits. Whenever you multiply such a number by anything, you are adding shifted versions of that string of k adjacent one-bits. Due to carries, that results in a sequence of one-bits over all of the overlap region except the rightmost bit of the overlap. You also get one one-bit for each bit to the right of the overlap. And due to carries, you get at least one one-bit to the left of the overlap. So that totals at least k one-bits.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Sorry, I should have said "binary numbers", not "primes". Tom Tom Karzes writes:
For the first list, the two-one-bit primes that are divisible by three have the form 2^(2*k+1) + 1, which is just 2*(4^k) + 1. Since 4 = 1 (mod 3), all powers of 4 are 1 (mod 3), so twice a power of 4 is 2 (mod 3), and adding 1 produces 0 (mod 3).
Similarly, the ones that are divisible by five have the form 2^(4*k + 2) + 1, which is just 4*(16^k) + 1. Since 16 = 1 (mod 5), all powers of 16 are 1 (mod 5), so four times a power of 16 is 4 (mod 5), and adding 1 produces 0 (mod 5).
Other such patterns exist. For instance, 16*(256^k) + 1 is always a multiuple of 17, 10*(1024^k) + 1 is always a multiple of 11, etc.
Tom
Keith F. Lynch writes:
Cris Moore <moore@santafe.edu> wrote:
I was wondering what primes can occur as factors of ?sparse? integers, i.e. those with only a few 1s in their binary expansion.
How few is few?
I looked at 21-bit numbers with three or fewer one-bits. Zero one-bits of course only gives me zero. One one-bit gives me powers of two, whose only prime factor is two. Two one-bits is where it gets interesting. I only looked at numbers whose rightmost bit is one, since all others are equal to such a number times some power of two. Here are the prime factors of the two-one-bit numbers:
3: 3 5: 5 9: 3^2 17: 17 33: 3 11 65: 5 13 129: 3 43 257: 257 513: 3^3 19 1025: 5^2 41 2049: 3 683 4097: 17 241 8193: 3 2731 16385: 5 29 113 32769: 3^2 11 331 65537: 65537 131073: 3 43691 262145: 5 13 37 109 524289: 3 174763 1048577: 17 61681
Every other one is divisible by three. Every fourth one is divisible by five. None are divisible by seven. Do all primes that ever appear appear at regular intervals?
Here are the prime factors of the three-one-bit numbers:
7: 7 11: 11 13: 13 19: 19 21: 3 7 25: 5^2 35: 5 7 37: 37 41: 41 49: 7^2 67: 67 69: 3 23 73: 73 81: 3^4 97: 97 131: 131 133: 7 19 137: 137 145: 5 29 161: 7 23 193: 193 259: 7 37 261: 3^2 29 265: 5 53 273: 3 7 13 289: 17^2 321: 3 107 385: 5 7 11 515: 5 103 517: 11 47 521: 521 529: 23^2 545: 5 109 577: 577 641: 641 769: 769 1027: 13 79 1029: 3 7^3 1033: 1033 1041: 3 347 1057: 7 151 1089: 3^2 11^2 1153: 1153 1281: 3 7 61 1537: 29 53 2051: 7 293 2053: 2053 2057: 11^2 17 2065: 5 7 59 2081: 2081 2113: 2113 2177: 7 311 2305: 5 461 2561: 13 197 3073: 7 439 4099: 4099 4101: 3 1367 4105: 5 821 4113: 3^2 457 4129: 4129 4161: 3 19 73 4225: 5^2 13^2 4353: 3 1451 4609: 11 419 5121: 3^2 569 6145: 5 1229 8195: 5 11 149 8197: 7 1171 8201: 59 139 8209: 8209 8225: 5^2 7 47 8257: 23 359 8321: 53 157 8449: 7 17 71 8705: 5 1741 9217: 13 709 10241: 7^2 11 19 12289: 12289 16387: 7 2341 16389: 3^3 607 16393: 13^2 97 16401: 3 7 11 71 16417: 16417 16449: 3 5483 16513: 7^2 337 16641: 3^2 43^2 16897: 61 277 17409: 3 7 829 18433: 18433 20481: 3 6827 24577: 7 3511 32771: 32771 32773: 13 2521 32777: 73 449 32785: 5 79 83 32801: 32801 32833: 32833 32897: 67 491 33025: 5^2 1321 33281: 23 1447 33793: 47 719 34817: 37 941 36865: 5 73 101 40961: 40961 49153: 13 19 199 65539: 65539 65541: 3 7 3121 65545: 5 13109 65553: 3 21851 65569: 7 17 19 29 65601: 3^2 37 197 65665: 5 23 571 65793: 3 7 13 241 66049: 257^2 66561: 3 11 2017 67585: 5 7 1931 69633: 3^3 2579 73729: 17 4337 81921: 3 7 47 83 98305: 5 19661 131075: 5^2 7^2 107 131077: 23 41 139 131081: 19 6899 131089: 7 61 307 131105: 5 13 2017 131137: 71 1847 131201: 7 18743 131329: 11 11939 131585: 5 26317 132097: 7 113 167 133121: 133121 135169: 29 59 79 139265: 5 7 23 173 147457: 147457 163841: 163841 196609: 7 28087 262147: 262147 262149: 3 87383 262153: 262153 262161: 3^2 29129 262177: 23 11399 262209: 3 87403 262273: 11 113 211 262401: 3 47 1861 262657: 262657 263169: 3^6 19^2 264193: 349 757 266241: 3 88747 270337: 270337 278529: 3 227 409 294913: 41 7193 327681: 3^2 23 1583 393217: 11 35747 524291: 29 101 179 524293: 7 11^2 619 524297: 17 30841 524305: 5 19 5519 524321: 7 74903 524353: 524353 524417: 61 8597 524545: 5 7^2 2141 524801: 524801 525313: 525313 526337: 7 17 4423 528385: 5 11 13 739 532481: 647 823 540673: 7 77239 557057: 557057 589825: 5^2 23593 655361: 7 251 373 786433: 786433 1048579: 7 163 919 1048581: 3^2 263 443 1048585: 5 209717 1048593: 3 7 13 23 167 1048609: 1048609 1048641: 3 11 43 739 1048705: 5 7 19^2 83 1048833: 3^2 116537 1049089: 1049089 1049601: 3 7 151 331 1050625: 5^4 41^2 1052673: 3 350891 1056769: 7 150967 1064961: 3^3 39443 1081345: 5 23 9403 1114113: 3 7^2 11 13 53 1179649: 1179649 1310721: 3 67 6521 1572865: 5 7 44939
The first few primes that don't appear are 31, 89, and 127, two of which are Mersenne primes. (Well, okay, 2 never appears, but only because I skipped all even numbers.)
Contrapositively speaking, you might enjoy proving the following: any multiple of the Mersenne prime 2^k-1 has at least k 1s.
Every number in the form 2^k-1, whether prime or not, consists of k adjacent one-bits. Whenever you multiply such a number by anything, you are adding shifted versions of that string of k adjacent one-bits. Due to carries, that results in a sequence of one-bits over all of the overlap region except the rightmost bit of the overlap. You also get one one-bit for each bit to the right of the overlap. And due to carries, you get at least one one-bit to the left of the overlap. So that totals at least k one-bits.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
--
On Sep 13, 2018, at 6:58 PM, Keith F. Lynch <kfl@KeithLynch.net> wrote:
Every number in the form 2^k-1, whether prime or not, consists of k adjacent one-bits.
I agree.
Whenever you multiply such a number by anything, you are adding shifted versions of that string of k adjacent one-bits. Due to carries, that results in a sequence of one-bits over all of the overlap region except the rightmost bit of the overlap. You also get one one-bit for each bit to the right of the overlap. And due to carries, you get at least one one-bit to the left of the overlap. So that totals at least k one-bits.
This isn’t how my proof goes — it’s not obvious to me that the carries can’t create some cancellations and end up with fewer 1s. - Cris
participants (3)
-
Cris Moore -
Keith F. Lynch -
Tom Karzes