Problems & Puzzles: Puzzles

Puzzle 515. Phi(Phi(x)) Fred Schneider poses the following nice puzzle: phi(x) is the Euler totient function, the number of positive integers relatively prime to positive integer x. Define phi(phi(x)) as p2(x). There exist chains of 4 consecutive numbers such that: p2(n) = p2(n+1)= p2(n+2) = p2(n+3) Chain of 4 found at 1: p2(1) = 1 Chain of 4 found at 7: p2(2) = 2 Chain of 4 found at 31: p2(31) = 8 [Note: This is actually a chain of 5] Chain of 4 found at 32: p2(32) = 8 Chain of 4 found at 2694: p2(2694)= 384 Chain of 4 found at 131071: p2(131071) = 32768 Q1) Are there any other chains of 4 beyond 131071. Are there any other chains of 5 (or longer)? Q2) What is the largest chain of 3 that you can find? Doing a quick search I found a chain of 3 starting at x=1020571232: p2(x) = 116121600 Q3) Can you give any insight into constructing chains of length 3 or more? Can you show there is an infinite number of them?

---

Contribution came only from Farideh Firoozbakht:

Farideh wrote:

Q1. There is no other chain of length 4 up to 2*10^9. Also all numbers n such that
p2(n) = p2(n+1) & p2(n+2) = p2(n+3) up to 2*10^8 are :

1,7,31,32,1544,2694,4345,131071,269024,2499884,3057746,
4626193,6088214,26013374,37740482,47146627,96878072

So I guess that, there is no other chain of length greater than 3.

Q2. 1199570656 .

Q3. { n | n = 32*prime(m), p2(n) = p2(n+1) = p2(n+2) , m < 14*10^6 } = {117536,22846112, 35006432, 234668576, 244793504, 346052576, 1016256224, 1020571232, 1532735264, 1891448864, 2904927392, 2957608352, 4614685664, 8600192864, 11199570656}

{ prime(m) | m < 2*10^7 & If n = 32*prime(m) then p2(n) = p2(n+1) = p2(n+2) } = { 3673, 713941, 1093951, 7333393, 7649797, 10814143, 31758007, 31892851, 47897977,
59107777, 90778981, 92425261, 144208927, 268756027 }

{d(prime(m) - 1) | m < 2*10^7 & If n = 32*prime(m) then p2(n) = p2(n+1) = p2(n+2)}=
{ 32, 48, 144, 160, 96, 32, 64, 144, 128, 224, 96, 192, 48, 128, 96 }

So it seems that for finding chain of length 3 we can search between numbers of the
form (2^t) * prime(m), which t > 3 and prime(m) - 1 has a large number of divisors.

***

A few hours later came this from Farid Lian:

Q1) Are there any other chains of 4 beyond 131071. Are there any other chains of 5 (or longer)?

Q1. There is no other chain of length 4 up to 10^10.

Q2) What is the largest chain of 3 that you can find?

Q2=1020571232, Base line
Q2. 1199570656, Farideh
Q2. 200221390706, Farid

Q3) Can you give any insight into constructing chains of length 3 or more? Can you show there is an infinite number of them?

I can found values for p2(n+k), where k=1, 2, 3, …, Up to k=7000, and, applying different regresions model, lineal, exponencial,…, in all of them, the tendency is progressive and positive, this to do impossible that exist an infinite chain of the case p2(n)=p2(n+1)=p2(n+2)=p2(n+k)…

Example: p2(n+k) = 0.4997*(n+k) - 15.757
To: 1 <= k <= 7000...

***

Farideh added later:

Please update my answer to Q2 :
Instead of " n = 11199570656 " write " n = 764787513632 " .

***