With the risk of closure by the duplicate zombies ( this one might do: How can I write the natural numbers less than $n$ that are coprime to $n$? ) I dare to ask the following question.

My hobby project is the development of an interactive Elementary Number Theory Course ( tutorial ) written in Mathematica Wolfram Language.

Now, assume that Mathematica did not have EulerPhi as a native Function then what would be the shortest ( in characters ) way to calculate EulerPhi ?

To start with I have the following two examples:

53: s[n_] := Length[Select[Range[n], GCD[#, n] == 1 &]]

36: s[n_] := Sum[Floor[1/GCD[k, n]], {k, 1, n}]

What is the shortest way??

  • 1
    $\begingroup$ DirichletConvolve[n, MoebiusMu[n], n, m]? $\endgroup$ – J. M.'s technical difficulties Apr 8 '17 at 9:40
  • $\begingroup$ I don't understand the m. EulerPhi is a function of n. $\endgroup$ – nilo de roock Apr 8 '17 at 9:43
  • 2
    $\begingroup$ Not really a golfer, sorry; anyway: Count[CoprimeQ[n, Range[n]], True] (or Range @ n ~CoprimeQ~ n ~Count~ True in the Wizard-ian style), or Total @ Boole @ CoprimeQ[n, Range[n]]. $\endgroup$ – J. M.'s technical difficulties Apr 8 '17 at 9:50
  • 2
    $\begingroup$ Maybe Range@n~GCD~n~Count~1 $\endgroup$ – Simon Woods Apr 8 '17 at 10:57
  • 3
    $\begingroup$ Small LeafCount: Exponent[Cyclotomic[n, x], x] $\endgroup$ – Michael E2 Apr 8 '17 at 20:41

Your Answer

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

Browse other questions tagged or ask your own question.