mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2020-10-03, 23:11   #1
jshort
 
"James Short"
Mar 2019
Canada

17 Posts
Default Question about number of the form 2^n + 1

Let a_{n} be the nth Highly Composite Integer* and b_{n} = lcm(2^{a_{1}} + 1, 2^{a_{2}} + 1, ...,2^{a_{n}} + 1). If c_{n} = \frac{2^{a_{n}} + 1}{gcd(2^{a_{n}} + 1,b_{n-1})}, will c_{n} always be equal to either 1 or a prime number?

*https://en.wikipedia.org/wiki/Highly...n%20the%20OEIS).
jshort is offline   Reply With Quote
Old 2020-10-04, 16:43   #2
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

11·353 Posts
Default

Quote:
Originally Posted by jshort View Post
Let a_{n} be the nth Highly Composite Integer* and b_{n} = lcm(2^{a_{1}} + 1, 2^{a_{2}} + 1, ...,2^{a_{n}} + 1). If c_{n} = \frac{2^{a_{n}} + 1}{gcd(2^{a_{n}} + 1,b_{n-1})}, will c_{n} always be equal to either 1 or a prime number?

*https://en.wikipedia.org/wiki/Highly...n%20the%20OEIS).
No. The first six highly composite numbers are 1, 2, 4, 6, 12, and 24.

We have b5 = lcm([3,5,17,65,4097]) = 3*5*13*17*241, and

224 + 1 = 16777217 = 97*257*673. Thus

c6 = (224 + 1)/gcd(3*5*13*17*241,97*257*673) = (224 + 1)/1 = 97*257*673
Dr Sardonicus is offline   Reply With Quote
Old 2020-10-06, 18:20   #3
jshort
 
"James Short"
Mar 2019
Canada

1116 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
No. The first six highly composite numbers are 1, 2, 4, 6, 12, and 24.

We have b5 = lcm([3,5,17,65,4097]) = 3*5*13*17*241, and

224 + 1 = 16777217 = 97*257*673. Thus

c6 = (224 + 1)/gcd(3*5*13*17*241,97*257*673) = (224 + 1)/1 = 97*257*673
Thanks Dr Sardonicus.

I didn't think a counter example could be found for such small n. My mistake was in assuming that the non-primitive part of 2^{n} + 1 must contain many factors from smaller 2^{m} + 1 where m < n is another highly composite integer. However just because m is highly composite, doesn't mean that m | n.

In this case, even considering only the primitive part of 2^{24} + 1 which is 65281 = 97 \cdot 673 we still get a composite integer, which is kind of surprising because we can also prove that any prime factor of the primitive part of 2^{24} + 1 must be of the form 1 + 4 \cdot 24k = 1 + 96k, which greatly restricts the possible number of "eligible" prime factors to nearly 1% of all primes that the are in the range from (2, \sqrt{65281}). However when k=1, we get 97 which is a factor lol!
jshort is offline   Reply With Quote
Old 2020-10-07, 11:51   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

11·353 Posts
Default

I considered the algebraic factorization of 2^m + 1. Write m = k*2^t where k is odd. Then we have (2^(2^t))^k + 1. If k > 1 this has 2^(2^t) + 1 as a proper factor. So I looked at

2^1 + 1 = 3, 2^2 + 1 = 5, 2^4 + 1 = 17, 2^6 + 1 (algebraic factor 2^2 + 1, cofactor 13 is prime), 2^12 + 1 (algebraic factor 2^4 + 1 which appears earlier on list; cofactor 241 is prime).

Then 2^24 + 1 = (2^8)^3 + 1.

Hmm. Algebraic factor, 2^8 + 1 = 257, prime, not a factor of any preceding 2^m + 1. I was pretty sure the cofactor would not divide the lcm, so I had a counterexample. It was then just a matter of working out the details.
Dr Sardonicus is offline   Reply With Quote
Old 2020-10-14, 12:14   #5
bur
 
Aug 2020

25 Posts
Default

Not really related to this specific question, but also a question about 2^n + 1:


Why aren't they researched in regard to being prime? It is basically a Proth number with k = 1. I just checked for n <= 200 and got primes only for n = 1, 2, 4, 8, 16 - or F(0) to F(4).

Is this sequence similar to Fermat and there are no known primes for 2^n + 1 other than those I mentioned above? If so, is it proven?

Googling didn't yield any results surprisingly, but looking up formulas can be hard.
bur is offline   Reply With Quote
Old 2020-10-14, 12:35   #6
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

2×5×37 Posts
Default

Quote:
Originally Posted by A019434
It is conjectured that there are only 5 terms.
kruoli is offline   Reply With Quote
Old 2020-10-14, 12:37   #7
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

23·719 Posts
Default

Quote:
Originally Posted by bur View Post
Not really related to this specific question, but also a question about 2^n + 1:


Why aren't they researched in regard to being prime? It is basically a Proth number with k = 1. I just checked for n <= 200 and got primes only for n = 1, 2, 4, 8, 16 - or F(0) to F(4).

Is this sequence similar to Fermat and there are no known primes for 2^n + 1 other than those I mentioned above? If so, is it proven?

Googling didn't yield any results surprisingly, but looking up formulas can be hard.
For 2^n+1 to be prime n must be a power of 2 https://mathworld.wolfram.com/FermatNumber.html has a proof of this.
henryzz is offline   Reply With Quote
Old 2020-10-14, 13:02   #8
bur
 
Aug 2020

25 Posts
Default

Ok, thanks. So 2^n+1 is proven to only be prime if it is a Fermat number.
bur is offline   Reply With Quote
Old 2020-10-14, 15:02   #9
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

32×132 Posts
Default

Quote:
Originally Posted by henryzz View Post
For 2^n+1 to be prime n must be a power of 2 https://mathworld.wolfram.com/FermatNumber.html has a proof of this.
So do we!: proposition 16 here
Nick is offline   Reply With Quote
Old 2020-10-14, 17:20   #10
bur
 
Aug 2020

2016 Posts
Default

Having looked at the proof, what I don't get is, why is 2^{(2r+1)s}=(2^s + 1)(...)?

Wolfram expressed it differently as (2^a)^b = (2^a + 1)(2^{a(b-1)}-2^{a(b-2)}+...). For that proof, I don't understand why 2^n = (2^a)^b if n = a*b with b being an odd integer. That it's equivalent to the product, I also don't get.

Last fiddled with by bur on 2020-10-14 at 17:24
bur is offline   Reply With Quote
Old 2020-10-14, 17:49   #11
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

32×132 Posts
Default

Quote:
Originally Posted by bur View Post
Having looked at the proof, what I don't get is, why is 2^{(2r+1)s}=(2^s + 1)(...)?
It's an example of what's called a telescopic sum: if you multiply out the brackets on the right hand side, then all terms cancel except for the first and the last.
If it's not clear, try writing it out with a small example such as r=3.
Nick is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A question about primes of a particular form enzocreti enzocreti 55 2019-04-27 11:10
Special Form of Mersenne and Fermat Number Factors michael Math 31 2015-09-04 05:57
Lucas-number prime factor form proofs Raman Math 1 2012-09-12 13:21
Statics Question, in the form of a storey jinydu Lounge 14 2012-07-13 06:23
Closed form solution of x^2 = 2 mod Fermat number mpenguin Factoring 10 2005-09-29 07:46

All times are UTC. The time now is 04:04.

Wed Dec 2 04:04:09 UTC 2020 up 83 days, 1:15, 1 user, load averages: 2.56, 2.41, 2.10

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.