Question about number of the form 2^n + 1

jshort · 2020-10-03, 23:11

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

Dr Sardonicus · 2020-10-04, 16:43

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 b₅ = lcm([3,5,17,65,4097]) = 3*5*13*17*241, and

2²⁴ + 1 = 16777217 = 97*257*673. Thus

c₆ = (2²⁴ + 1)/gcd(3*5*13*17*241,97*257*673) = (2²⁴ + 1)/1 = 97*257*673

jshort · 2020-10-06, 18:20

Quote:

Originally Posted by Dr Sardonicus

No. The first six highly composite numbers are 1, 2, 4, 6, 12, and 24.

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

2²⁴ + 1 = 16777217 = 97*257*673. Thus

c₆ = (2²⁴ + 1)/gcd(3*5*13*17*241,97*257*673) = (2²⁴ + 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!

Dr Sardonicus · 2020-10-07, 11:51

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.

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:

Originally Posted by A019434

It is conjectured that there are only 5 terms.

henryzz · 2020-10-14, 12:37

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.

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:

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

bur · 2020-10-14, 17:20

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.

Nick · 2020-10-14, 17:49

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.

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-14, 17:20	#10
bur Aug 2020 2×19 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 = ab 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*

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

2020-10-07, 11:51	#4
Dr Sardonicus Feb 2017 Nowhere 10123₈ Posts	I considered the algebraic factorization of 2^m + 1. Write m = k2^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×19 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, 13:02	#8
bur Aug 2020 2×19 Posts	Ok, thanks. So 2^n+1 is proven to only be prime if it is a Fermat number.