Question about number of the form 2^n + 1
Let [TEX]a_{n}[/TEX] be the nth Highly Composite Integer* and [TEX]b_{n} = lcm(2^{a_{1}} + 1, 2^{a_{2}} + 1, ...,2^{a_{n}} + 1)[/TEX]. If [TEX]c_{n} = \frac{2^{a_{n}} + 1}{gcd(2^{a_{n}} + 1,b_{n1})}[/TEX], will [TEX]c_{n}[/TEX] always be equal to either 1 or a prime number?
*[url]https://en.wikipedia.org/wiki/Highly_composite_number#:~:text=Highly%20composite%20numbers%20whose%20number,sequence%20A189394%20in%20the%20OEIS[/url]). 
[QUOTE=jshort;558808]Let [TEX]a_{n}[/TEX] be the nth Highly Composite Integer* and [TEX]b_{n} = lcm(2^{a_{1}} + 1, 2^{a_{2}} + 1, ...,2^{a_{n}} + 1)[/TEX]. If [TEX]c_{n} = \frac{2^{a_{n}} + 1}{gcd(2^{a_{n}} + 1,b_{n1})}[/TEX], will [TEX]c_{n}[/TEX] always be equal to either 1 or a prime number?
*[url]https://en.wikipedia.org/wiki/Highly_composite_number#:~:text=Highly%20composite%20numbers%20whose%20number,sequence%20A189394%20in%20the%20OEIS[/url]).[/QUOTE]No. The first six highly composite numbers are 1, 2, 4, 6, 12, and 24. We have b[sub]5[/sub] = lcm([3,5,17,65,4097]) = 3*5*13*17*241, and 2[sup]24[/sup] + 1 = 16777217 = 97*257*673. Thus c[sub]6[/sub] = (2[sup]24[/sup] + 1)/gcd(3*5*13*17*241,97*257*673) = (2[sup]24[/sup] + 1)/1 = 97*257*673 
[QUOTE=Dr Sardonicus;558862]No. The first six highly composite numbers are 1, 2, 4, 6, 12, and 24.
We have b[sub]5[/sub] = lcm([3,5,17,65,4097]) = 3*5*13*17*241, and 2[sup]24[/sup] + 1 = 16777217 = 97*257*673. Thus c[sub]6[/sub] = (2[sup]24[/sup] + 1)/gcd(3*5*13*17*241,97*257*673) = (2[sup]24[/sup] + 1)/1 = 97*257*673[/QUOTE] Thanks Dr Sardonicus. I didn't think a counter example could be found for such small [TEX]n[/TEX]. My mistake was in assuming that the nonprimitive part of [TEX]2^{n} + 1[/TEX] must contain many factors from smaller [TEX]2^{m} + 1[/TEX] where [TEX]m < n[/TEX] is another highly composite integer. However just because [TEX]m[/TEX] is highly composite, doesn't mean that [TEX]m  n[/TEX]. In this case, even considering only the primitive part of [TEX]2^{24} + 1[/TEX] which is [TEX]65281 = 97 \cdot 673[/TEX] 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 [TEX]2^{24} + 1[/TEX] must be of the form [TEX]1 + 4 \cdot 24k = 1 + 96k[/TEX], which greatly restricts the possible number of "eligible" prime factors to nearly 1% of all primes that the are in the range from [TEX](2, \sqrt{65281})[/TEX]. However when [TEX]k=1[/TEX], we get [TEX]97[/TEX] which is a factor lol! 
I considered the algebraic factorization of 2^m + 1. Write m = k*2^t where k is [i]odd[/i]. 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. 
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. 
[QUOTE="A[OEIS]019434[/OEIS]"]It is conjectured that there are only 5 terms.[/QUOTE]
:smile: 
[QUOTE=bur;559847]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.[/QUOTE] For 2^n+1 to be prime n must be a power of 2 [url]https://mathworld.wolfram.com/FermatNumber.html[/url] has a proof of this. 
Ok, thanks. So 2^n+1 is proven to only be prime if it is a Fermat number.

[QUOTE=henryzz;559850]For 2^n+1 to be prime n must be a power of 2 [URL]https://mathworld.wolfram.com/FermatNumber.html[/URL] has a proof of this.[/QUOTE]
So do we!: proposition 16 [URL="https://www.mersenneforum.org/showthread.php?t=21658"]here[/URL] 
Having looked at the proof, what I don't get is, why is [TEX]2^{(2r+1)s}=(2^s + 1)(...)[/TEX]?
Wolfram expressed it differently as [TEX](2^a)^b = (2^a + 1)(2^{a(b1)}2^{a(b2)}+...)[/TEX]. For that proof, I don't understand why [TEX]2^n = (2^a)^b[/TEX] if n = a*b with b being an odd integer. That it's equivalent to the product, I also don't get. 
[QUOTE=bur;559892]Having looked at the proof, what I don't get is, why is [TEX]2^{(2r+1)s}=(2^s + 1)(...)[/TEX]?[/QUOTE]
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. 
All times are UTC. The time now is 10:27. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.