4
$\begingroup$

I want to evaluate $\phi(50!)$, where $\phi$ is the Euler totient function, so i take the factorization in primes of $50!$ $$2^{47}\times 3^{22}\times 5^{12}\times 7^8\times 11^4\times 13^3\times 17^2\times 19^2\times 23^2\times 29\times 31\times 37\times 41\times 43\times 47$$ then i use multiplicativity of $\phi$ and the properties $\phi(p)=p-1$ and $\phi(p^k)=p^{k-1}(p-1)$ for every prime $p$ and i get $$\phi(50!)=4218559200885839042679312107816703841788854953574400000000000000$$

I'm asking for some smarter way to compute values of $\phi$ for great numbers, possibly not involving prime factorization

$\endgroup$
  • $\begingroup$ I would say that factorizing is a pretty strong way to do this. If you look only for a fast calculator, Pari/GP does it fast. $\endgroup$ – Beni Bogosel Mar 18 '13 at 22:02
  • $\begingroup$ No one knows a better way to get $\phi$ than by factorization. Indeed, in many contexts the two problems are equivalent, in that if you can do either one then you can do the other just as fast. $\endgroup$ – Gerry Myerson Mar 18 '13 at 23:28
  • $\begingroup$ Saying you need factorization of $n!$ suggests something worse than it really is; there are only prime factors${}\leq n$ and there is a pretty simple formula for the multiplicity of such prime factors. But as the answer by DonAntonio shows, you don't even need that formula if you are willing to do a few divisions in addition to multiplications. $\endgroup$ – Marc van Leeuwen Mar 19 '13 at 11:03
4
$\begingroup$

$$\phi(50!)=50!\prod_{p\le 50\,,\,\,p\text{ a prime}}\left(1-\frac{1}{p}\right)$$

The above is based on the following lemma:

Lemma: If

$$\Bbb N\ni n=\prod_{i=1}^kp_i^{a_i}\;\;,\;\;0<a_i\in\Bbb N\;,\;\;p_i\,\,\text{primes}$$

is the prime decomposition of $\,n\,$ , then

$$\phi(n)=n\prod_{i=1}^k\left(1-\frac{1}{p_i}\right)$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ in the last $\displaystyle\prod$, do you mean $i$ from 1 to $k$? $\endgroup$ – bateman Mar 19 '13 at 7:59
  • $\begingroup$ Indeed, so, thanks. $\endgroup$ – DonAntonio Mar 19 '13 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.