Problems & Puzzles: Puzzles

Puzzle 590. P-1 & P+1 with the same quantity of prime factors. JM Bergot posed the following puzzle: Take 5,19,89, and 271.  These are the smallest primes P such that P-1 & P+1 has the same quantity of K prime factors (repetition allowed). K=2, 3, 4 & 5 for P= 5, 19, 89, and 271, respectively. Q1. Can you extend the sequence of primes 5, 19, 89, 271,...

---

Contributions came from Claudio Meller, Jan van Delden, Torbjörn Alm, Emmanuel Vantieghem, Robert D. Mohr & Hakan Summakoğlu.

***

Claudio Meller wrote:

Aqui va la respuesta para el último puzzle (calculé hasta 20000000): 5,19,89,271,1889,10529,75329,157951,3885569,11350529

***

Jan wrote:

I computed a few terms and checked Sloane’s, it can be found at:  A154598, apparently numbers above 2^54 have to be checked.

The total multiplicity of the prime factors of n is called big omega n; Ω(n).

 

If one is interested in equality of the number of distinct prime factors of p-1 and p+1, the answer is at: A088076. This function is called small omega; ω(n).

***

Torbjörn Alm wrote:

Here comes solutions for k=6...14.

1889  6
10529  7
75329  8
157951  9
3885569  10
11350529  11
65071999  13
98690561  12
652963841  14

Note that the solution for 13 came berore 12.

I have searched the first 50 000 000 primes up to about 10^9.

***

Emmanuel wrote:

About puzzle 590, the sougth for sequence is undoubtedly  A154598  of the OEIS (whose owner is JM Bergot) :

5, 19, 89, 271, 1889, 10529, 75329, 157951, 3885569, 11350529, 98690561, 65071999, 652963841, 6548416001, 253401579521, 160283668481, 1851643543553, 3450998226943, 23114453401601, 1194899749142527, 1101483715526657, 7093521158963201.

There it is stated that the next term is bigger than  2^54.

***

Robert wrote:

A stricter requirement would be that only the prime number 2 can be repeated (this must happen since either p-1 or p+1 will be divisible by multiple powers of 2).

 

I have found the sequence through k=8, the first three terms being 5, 29, 461, ...

 

k=2         p=5

k=3         p=29

k=4         p=461

k=5         p=2729

k=6         p=43889

k=7         p=1345889

k=8         p=11741729

***

Hakan Summakoğlu wrote:

k=6, p=1889
k=7, p=10529
k=8, p=75329
k=9, p=157951
k=10, p=3885569
k=11, p=11350529
k=12, p=98690561
k=13, p=65071999

***

 

---