 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 be the nth Highly Composite Integer* and . If , will 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

74538 Posts Quote:
 Originally Posted by jshort Let be the nth Highly Composite Integer* and . If , will 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

17 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 . My mistake was in assuming that the non-primitive part of must contain many factors from smaller where is another highly composite integer. However just because is highly composite, doesn't mean that .

In this case, even considering only the primitive part of which is 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 must be of the form , which greatly restricts the possible number of "eligible" prime factors to nearly 1% of all primes that the are in the range from . However when , we get which is a factor lol!   2020-10-07, 11:51 #4 Dr Sardonicus   Feb 2017 Nowhere 11·353 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 25 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

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

167816 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 25 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

101111100012 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 25 Posts Having looked at the proof, what I don't get is, why is ? Wolfram expressed it differently as . For that proof, I don't understand why 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

27618 Posts Quote:
 Originally Posted by bur Having looked at the proof, what I don't get is, why is ?
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.   Thread Tools Show Printable Version Email this Page 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 03:39.

Wed Dec 2 03:39:17 UTC 2020 up 83 days, 50 mins, 1 user, load averages: 1.73, 1.72, 1.68