mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Question about number of the form 2^n + 1 (https://www.mersenneforum.org/showthread.php?t=26041)

jshort 2020-10-03 23:11

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_{n-1})}[/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]).

Dr Sardonicus 2020-10-04 16:43

[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_{n-1})}[/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

jshort 2020-10-06 18:20

[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 non-primitive 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!

Dr Sardonicus 2020-10-07 11:51

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.

bur 2020-10-14 12:14

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.

kruoli 2020-10-14 12:35

[QUOTE="A[OEIS]019434[/OEIS]"]It is conjectured that there are only 5 terms.[/QUOTE]
:smile:

henryzz 2020-10-14 12:37

[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.

bur 2020-10-14 13:02

Ok, thanks. So 2^n+1 is proven to only be prime if it is a Fermat number.

Nick 2020-10-14 15:02

[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]

bur 2020-10-14 17:20

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(b-1)}-2^{a(b-2)}+...)[/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.

Nick 2020-10-14 17:49

[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.