## Poll

 Hmmm. Very interesting 2 votes (66.66%) Meh. I learned this in school No votes (0%) I thought this thread would be about Amazon Prime No votes (0%) Is nerdiness contagious? No votes (0%) Next, will Gordon start riding unicycles? 1 vote (33.33%) This is less interesting than sex No votes (0%)

3 members have voted

gordonm888 Joined: Feb 18, 2015
• Posts: 2855
November 8th, 2020 at 11:52:26 AM permalink
I have noticed something about the "number of prime factors" of certain numbers. I was not a math major in college and don't have formal education in number theory, so I thought I would present it to the math wizards in the forum here and see what you-all think.

Define NPF(n) as being the number of prime factors of the integer n.

Ex: Given that 24 = 23*3; then NPF(24) == 4.

Defining, as usual, that pi is the ith prime number then I notice that for any pi the NPF of (pi2-1) is always unusually large, and for example, seems to be always larger than (pi2+1).

Ex.: The number 17 is prime. 172+1 =290 and 290 =2*5*29 and thus has three prime factors. But 172-1 =288 and 288= 25*32 and thus has 7 prime factors.

Here is a table of the number of prime factors of (p2 -1) and (p2 +1) for the first 60 prime numbers and for one larger prime number of interest.

Prime, p
NPF of (p2-1)
NPF of (p2+1)
2
1
1
3
3
2
5
4
2
7
5
3
11
5
2
13
5
3
17
7
3
19
6
2
29
6
2
31
8
3
37
6
3
41
7
3
43
6
4
47
7
4
53
7
3
59
6
2
61
6
2
67
6
3
71
8
2
73
7
4
79
8
2
83
6
4
89
8
3
97
9
3
101
7
2
103
7
3
107
7
4
109
8
3
113
8
3
127
11
3
131
7
2
137
7
3
139
7
2
149
7
3
151
8
3
157
6
5
163
8
3
167
7
3
173
6
4
179
7
3
181
8
2
191
10
4
193
9
5
197
8
3
199
9
2
211
7
3
223
9
3
227
6
3
229
7
3
233
8
4
239
10
5
241
9
3
251
8
4
257
11
4
263
7
3
269
9
3
271
10
2
277
6
3
281
8
3
8191
19
4

I know this is not a large number of primes that I have looked at so far, but. . . .

1. I conjecture that NPF(pi2-1) is always larger than NPF(pi2+1) -for primes >2. I have no idea why.

2. I notice that NPF(p2-1) is always 6 or greater for primes that are higher than 13 -at least for the sample that I have investigated. I wonder if that continues.

3. I also notice that any prime number that is one off from a power of 2 has an anomalously large number of prime factors.

Ex: 17 (=24+1) is the lowest prime to for which NPF(p2-1) > 5: it has 7 prime factors.
Ex: 31 (=25-1) and the NPF(312-1) = 8
Ex: 127 (=27-1) and the NPF(1272-1) = 11
Ex: 257 (=28+1) and the NPF(2572-1) = 11
Ex: 8191 (=215-1) and the NPF(81912-1) = 19. 81912-1 = 214*32*5*7*13

Last edited by: gordonm888 on Nov 8, 2020
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
rsactuary Joined: Sep 6, 2014
• Posts: 1807
Thanks for this post from: November 8th, 2020 at 12:02:19 PM permalink
Not much to add here, but note that in your first conjecture that p-i squared minus 1 (sorry, not figuring out sub and superscripts) is a difference of squares with factors p-1 and p+1. Not sure how that works into anything, but noticed that.
ThatDonGuy Joined: Jun 22, 2011
• Posts: 4678
Thanks for this post from: November 8th, 2020 at 12:45:22 PM permalink
Quote: rsactuary

(sorry, not figuring out sub and superscripts)

To do pi, use p[sub]i[/sub]

To do p2, use p[sup]2[/sup]

You can also use ^ as an equivalent for superscripts when referring to raising a numbe to a power - i.e. p^2 = p2
ThatDonGuy Joined: Jun 22, 2011
• Posts: 4678
Thanks for this post from: November 8th, 2020 at 12:52:18 PM permalink
Quote: gordonm888

2. I notice that NPF(p2-1) is always 6 or greater for primes that are higher than 13 -at least for the sample that I have investigated. I wonder if that continues.

Notice that all primes > 3 are either one more than a multiple of 6 or one less than a multiple of 6.
(Proof: every integer = one of 0, 1, 2, 3, 4, or 5 modulo 6; numbers = 0, 2, or 4 modulo 6 are multiples of 2; numbers = 3 modulo 6 are multiples of 3)

If p is one more than a multiple of 6, (6k + 1)2 - 1 = 36 k2 + 12 k = 2 x 2 x 3 x k x (3k + 1)
If p is one less than a multiple of 6, (6k - 1)2 - 1 = 36 k2 - 12 k = 2 x 2 x 3 x k x (3k - 1)
Either k is even or 3k +/- 1 is even, so there is another prime factor 2, which means there must be at least 6 prime factors.

...unless k = 2, 3k - 1 = 2 (in which case, k =1), or 3k + 1 = 2 (which is impossible as k = 1/3)
If k = 2, then (6k + 1)2 - 1 = 168 = 2 x 2 x 2 x 3 x 7, and (6k - 1)2 - 1 = 120 = 2 x 2 x 2 x 3 x 5, both of which have only 5 prime factors
If k + 1 = 2, then (6k - 1)2 - 1 = 24 = 2 x 2 x 2 x 3, which is only 4 prime factors
However, if p > 13, then k >= 3
Last edited by: ThatDonGuy on Nov 8, 2020
Doc Joined: Feb 27, 2010
• Posts: 7071
Thanks for this post from: November 8th, 2020 at 12:57:26 PM permalink
I must be missing something. Looking just at your first data row (p=2), I think p2-1=3 and p2+1=5.

Why are your NPF for these 1 and 0 rather than 1 and 1?
gordonm888 Joined: Feb 18, 2015
• Posts: 2855
November 8th, 2020 at 1:11:07 PM permalink
Quote: Doc

I must be missing something. Looking just at your first data row (p=2), I think p2-1=3 and p2+1=5.

Why are your NPF for these 1 and 0 rather than 1 and 1?

That's a typo. I will fix that. Thanks.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
gordonm888 Joined: Feb 18, 2015
• Posts: 2855
November 8th, 2020 at 1:22:29 PM permalink
Quote: ThatDonGuy

Quote: gordonm888

2. I notice that NPF(p2-1) is always 6 or greater for primes that are higher than 13 -at least for the sample that I have investigated. I wonder if that continues.

Notice that all primes > 3 are either one more than a multiple of 6 or one less than a multiple of 6.
(Proof: every integer = one of 0, 1, 2, 3, 4, or 5 modulo 6; numbers = 0, 2, or 4 modulo 6 are multiples of 2; numbers = 3 modulo 6 are multiples of 3)

If p is one more than a multiple of 6, (6k + 1)- 1 = 36 k2 + 12 k = 2 x 2 x 3 x k x (3k + 1)
If p is one less than a multiple of 6, (6k - 1)2 - 1 = 36 k2 - 12 k = 2 x 2 x 3 x k x (3k - 1)
Either k is even or 3k +/- 1 is even, so there is another prime factor 2, which means there must be at least 6 prime factors.

...unless k = 2, 3k - 1 = 2 (in which case, k =1), or 3k + 1 = 2 (which is impossible as k = 1/3)
If k = 2, then (6k + 1)2 - 1 = 168 = 2 x 2 x 2 x 3 x 7, and (6k - 1)2 - 1 = 120 = 2 x 2 x 2 x 3 x 5, both of which have only 5 prime factors
If k + 1 = 2, then (6k - 1)2 - 1 = 24 = 2 x 2 x 2 x 3, which is only 4 prime factors
However, if p > 13, then k >= 3

Yes, I see. Simple, but brilliant. So, this observation is pretty pedestrian?

And, this implies that for any non-prime of the form n=6k +/- 1 -such as 25 or 35, that n2 -1 will also have at least 6 prime factors. So, it really has nothing to do with whether n is a prime. It means that at least 1/3 of all numbers of the form n2 -1 will have at least 6 prime factors.

And, I imagine that if n= 2m +/- 1 there is some analogous analysis that would imply large numbers of prime factors for n2 -1. I'll try to puzzle it out.
Last edited by: gordonm888 on Nov 8, 2020
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
gordonm888 Joined: Feb 18, 2015
• Posts: 2855
November 8th, 2020 at 2:01:33 PM permalink
Quote: rsactuary

Not much to add here, but note that in your first conjecture that p-i squared minus 1 (sorry, not figuring out sub and superscripts) is a difference of squares with factors p-1 and p+1. Not sure how that works into anything, but noticed that.

Well this is interesting too. Don has worked out that p2 -1 must have at least 6 prime factors, and rsactuary points out that p2 -1 = (p+1)*(p-1). So this means that the numbers immediately above or below a prime (i.e, p+1 and p-1) cannot both be semiprimes.

I guess that's sensible. Both p+1 and p-1 must be divisible by 2 and one of them must be divisible by 3. So, assuming that neither p=1 or p-1 is exactly equal to 6, one of them must have a third factor - thus both p+1 and p-1 cannot be semiprimes.

Edit: Aha! Given p+1 and p-1, both numbers must be divisible by 2 and at least one of those numbers must be divisible by 22. Also either p+1 or p-1 must be divisible by 3, so if p-1 > 2*2*3 (or p>13) then both p+1 and p-1 must each have at least one additional prime factor, so that p2-1 must have a minimum of six prime factors because p2-1 must be divisible by 2^3*3 and by at least two additional prime numbers. Which is basically what Don said.
Last edited by: gordonm888 on Nov 8, 2020
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
ThatDonGuy Joined: Jun 22, 2011
• Posts: 4678
November 8th, 2020 at 2:08:04 PM permalink
Quote: gordonm888

And, this implies that for any non-prime of the form n=6k +/- 1 -such as 25 or 35, that n2 -1 will also have at least 6 prime factors. So, it really has nothing to do with whether n is a prime. It means that at least 1/3 of all numbers of the form n2 -1 will have at least 6 prime factors.

Yes.

Quote: gordonm888

And, I imagine that if n= 2m +/- 1 there is some analogous analysis that would imply large numbers of prime factors for n2 -1.

If n = 2m + 1, then n2 - 1 = (n + 1)(n - 1) = (2m + 2) 2m = 2m+1 (2m-1 + 1)

If n = 2m - 1, then n2 - 1 = (n + 1)(n - 1) = 2m (2m - 2) = 2m+1 (2m-1 - 1)

In both cases, there are at least m + 2 prime factors, m + 1 of which are 2. Note that, in the second case, if m is odd and > 1, 2m-1 - 1 is a multiple of 3.
gordonm888 Joined: Feb 18, 2015
• Posts: 2855
November 8th, 2020 at 2:45:26 PM permalink
Quote: gordonm888

And, I imagine that if n= 2m +/- 1 there is some analogous analysis that would imply large numbers of prime factors for n2 -1.

Quote: ThatDonGuy

If n = 2m + 1, then n2 - 1 = (n + 1)(n - 1) = (2m + 2) 2m = 2m+1 (2m-1 + 1)

If n = 2m - 1, then n2 - 1 = (n + 1)(n - 1) = 2m (2m - 2) = 2m+1 (2m-1 - 1)

In both cases, there are at least m + 2 prime factors, m + 1 of which are 2. Note that, in the second case, if m is odd and > 1, 2m-1 - 1 is a multiple of 3.

Yes, yes. I agree. Got it.

Thinking out loud: Does this apply to all integers of the form n= 2m +/- a2k, with a =an integer?
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.