mersenneforum.org > Math Question about number of the form 2^n + 1
 Register FAQ Search Today's Posts Mark Forums Read

 2020-10-03, 23:11 #1 jshort   "James Short" Mar 2019 Canada 17 Posts 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).
2020-10-04, 16:43   #2
Dr Sardonicus

Feb 2017
Nowhere

24×271 Posts

Quote:
 Originally Posted by jshort 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

2020-10-06, 18:20   #3
jshort

"James Short"
Mar 2019

218 Posts

Quote:
 Originally Posted by Dr Sardonicus 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!

 2020-10-07, 11:51 #4 Dr Sardonicus     Feb 2017 Nowhere 103608 Posts 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.
 2020-10-14, 12:14 #5 bur   Aug 2020 2·33 Posts 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.
2020-10-14, 12:35   #6
kruoli

"Oliver"
Sep 2017
Porta Westfalica, DE

22·109 Posts

Quote:
 Originally Posted by A019434 It is conjectured that there are only 5 terms.

2020-10-14, 12:37   #7
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

2×2,909 Posts

Quote:
 Originally Posted by bur 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.

 2020-10-14, 13:02 #8 bur   Aug 2020 2·33 Posts Ok, thanks. So 2^n+1 is proven to only be prime if it is a Fermat number.
2020-10-14, 15:02   #9
Nick

Dec 2012
The Netherlands

65516 Posts

Quote:
 Originally Posted by henryzz 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

 2020-10-14, 17:20 #10 bur   Aug 2020 3616 Posts 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
2020-10-14, 17:49   #11
Nick

Dec 2012
The Netherlands

1,621 Posts

Quote:
 Originally Posted by bur 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post enzocreti enzocreti 55 2019-04-27 11:10 michael Math 31 2015-09-04 05:57 Raman Math 1 2012-09-12 13:21 jinydu Lounge 14 2012-07-13 06:23 mpenguin Factoring 10 2005-09-29 07:46

All times are UTC. The time now is 10:37.

Thu Mar 4 10:37:36 UTC 2021 up 91 days, 6:48, 1 user, load averages: 1.27, 1.43, 1.53