1
$\begingroup$

From this article on Sum of Euler totient function we have the following tree:

enter image description here

We know that if $p$ is prime, $\phi(p) = p - 1$, that is, $\phi(11) = 11 - 1 = 10$.

It's obvious that the above tree has a main stem and the $\phi$ branches finally reach this stem. The important number to obtain is the power of $2$ at which the $\phi$ of a number reach to the stem. This would help to determine the $\phi(n)$ for arbitrary n, specifically if it becomes possible, it would lead to prime numbers identification.

Another important note can be the reverse scan of tree. As an example, consider the number $4$ in the main stem. The numbers ${5, 13, 11}$ reach to main stem on number $4$. What if we could obtain that list for arbitrary $2^n$?

Any solution to these problems?

  • 0
    Sorry, I don't see what that has to do with my first comment on this question.2012-12-06

1 Answers 1

3

Factoring and computing the Euler totient function are known to be equivalent for arbitrary numbers, not just semiprimes. See the response here: https://mathoverflow.net/questions/3274/how-hard-is-it-to-compute-the-euler-totient-function

You can see some approaches and algorithms here: http://en.wikipedia.org/wiki/Euler's_totient_function or http://mathworld.wolfram.com/TotientFunction.html

This might also be useful in exploring the problem more: http://oeis.org/A000010

Here is a calculator for up to 20 digit numbers: http://www.javascripter.net/math/calculators/eulertotientfunction.htm

You could always use a Computer Algebra System (CAS) or use WA: http://www.wolframalpha.com/input/?i=euler+totient+function+of+1234567890

Lastly, you could type things like this in WA: Table[{k, EulerPhi[k]}, {k,0,100}].

Regards - A

  • 0
    Recall that this problem is equivalent to the Factoring problem. Does that make sense?2012-12-05