## Poll

2 votes (66.66%) | |||

No votes (0%) | |||

No votes (0%) | |||

No votes (0%) | |||

1 vote (33.33%) | |||

No votes (0%) |

**3 members have voted**

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

Ex: Given that 24 = 2

^{3}*3; then NPF(24) == 4.

Defining, as usual, that p

_{i}is the ith prime number then I notice that for any p

_{i}the NPF of (p

_{i}

^{2}-1) is always unusually large, and for example, seems to be always larger than (p

_{i}

^{2}+1).

Ex.: The number 17 is prime. 17

^{2}+1 =290 and 290 =2*5*29 and thus has three prime factors. But 17

^{2}-1 =288 and 288= 2

^{5}*3

^{2}and thus has 7 prime factors.

Here is a table of the number of prime factors of (p

^{2}-1) and (p

^{2}+1) for the first 60 prime numbers and for one larger prime number of interest.

Prime, p | NPF of (p ^{2}-1) | NPF of (p ^{2}+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(p

_{i}

^{2}-1) is always larger than NPF(p

_{i}

^{2}+1) -for primes >2. I have no idea why.

2. I notice that NPF(p

^{2}-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 (=2

^{4}+1) is the lowest prime to for which NPF(p

^{2}-1) > 5: it has 7 prime factors.

Ex: 31 (=2

^{5}-1) and the NPF(31

^{2}-1) = 8

Ex: 127 (=2

^{7}-1) and the NPF(127

^{2}-1) = 11

Ex: 257 (=2

^{8}+1) and the NPF(257

^{2}-1) = 11

Ex: 8191 (=2

^{15}-1) and the NPF(8191

^{2}-1) = 19. 8191

^{2}-1 = 2

^{14}*3

^{2}*5*7*13

Comments, please!!!!!

Quote:rsactuary(sorry, not figuring out sub and superscripts)

To do p

_{i}, use p[sub]i[/sub]

To do p

^{2}, 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 = p

^{2}

Quote:gordonm8882. I notice that NPF(p

^{2}-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 k

^{2}+ 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 k

^{2}- 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

^{2}-1=3 and p

^{2}+1=5.

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

Quote:DocI must be missing something. Looking just at your first data row (p=2), I think p

^{2}-1=3 and p^{2}+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.

Quote:ThatDonGuyQuote:gordonm8882. I notice that NPF(p

^{2}-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 k^{2}+ 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 k^{2}- 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 n

^{2}-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 n

^{2}-1 will have at least 6 prime factors.

And, I imagine that if n= 2

^{m}+/- 1 there is some analogous analysis that would imply large numbers of prime factors for n

^{2}-1. I'll try to puzzle it out.

Quote:rsactuaryNot 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 p

^{2}-1 must have at least 6 prime factors, and rsactuary points out that p

^{2}-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 2

^{2}. 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 p

^{2}-1 must have a minimum of six prime factors because p

^{2}-1 must be divisible by 2^3*3 and by at least two additional prime numbers. Which is basically what Don said.

Quote:gordonm888And, this implies that for any non-prime of the form n=6k +/- 1 -such as 25 or 35, that n

^{2}-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 n^{2}-1 will have at least 6 prime factors.

Yes.

Quote:gordonm888And, I imagine that if n= 2

^{m}+/- 1 there is some analogous analysis that would imply large numbers of prime factors for n^{2}-1.

If n = 2

^{m}+ 1, then n

^{2}- 1 = (n + 1)(n - 1) = (2

^{m}+ 2) 2

^{m}= 2

^{m+1}(2

^{m-1}+ 1)

If n = 2

^{m}- 1, then n

^{2}- 1 = (n + 1)(n - 1) = 2

^{m}(2

^{m}- 2) = 2

^{m+1}(2

^{m-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, 2

^{m-1}- 1 is a multiple of 3.

Quote:gordonm888And, I imagine that if n= 2

^{m}+/- 1 there is some analogous analysis that would imply large numbers of prime factors for n^{2}-1.

Quote:ThatDonGuyIf n = 2

^{m}+ 1, then n^{2}- 1 = (n + 1)(n - 1) = (2^{m}+ 2) 2^{m}= 2^{m+1}(2^{m-1}+ 1)

If n = 2^{m}- 1, then n^{2}- 1 = (n + 1)(n - 1) = 2^{m}(2^{m}- 2) = 2^{m+1}(2^{m-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, 2^{m-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= 2

^{m}+/- a

^{2k}, with a =an integer?