Problems & Puzzles: Puzzles

Puzzle 352. φ(n!)

Sebastián Martín Ruiz found empirically that:

φ(n!) = n.φ((n-1)!) or (n-1).φ((n-1)!), if n is composite or prime, respectively...................(1)

As a matter of fact I have proved, by deduction, the following expression:

φ(n!) = Π(i-k(i)); i=1 to n; k(i)=0 if i is composite or k(i)=1 is i is prime; k(1)=0.........................(2)

from which are generated the expressions discovered by SMR.

From (2), here is an illustration:

     10!=10.9.8.7.6.5.4.3.2.1
φ(10!)=10.9.8.6.6.4.4.2.1.1

 

Question: Can you send your own proof of (2)?

 

 

Contributions came from Joseph L. Pe, Farideh Firoozbakht, Rudolph Knjzek, Salvatore Ingala, Dan Dima.

***

Only Dan Dima proved directly (2). His solution will be posted soon. The other puzzlers first proved (1) and then (2) by induction.

***

 


Records   |  Conjectures  |  Problems  |  Puzzles