For the record (and later reference) ...
Euler's product formula for the totient of a number n with k
*distinct* prime factors p_i reads
phi(n) = n * (1 - 1/p_1) * (1 - 1/p_2) * ... * (1 - 1/p_k)
Rewriting this by replacing n with the product of prime factors one gains
Product (i=1 to k) over [ (p_i - 1) * p_i^(e_i - 1) ]
(J code)
*/ (p-1)*p^e-1
~-----~-----~
Andrew Nikitin's version is a fresh look at the same formula, as
illustrated by this example:
] n=. !7 NB. composite number
5040
q: n NB. listing prime factors
2 2 2 2 3 3 5 7
~: q: n NB. marking distinct prime factors
1 0 0 0 1 0 1 1
Subtracting the two lists gives
(q: n) - (~: q: n)
1 2 2 2 2 3 4 6
a result which may be looked at (grouped) like
1 2 2 2 | 2 3 | 4 | 6
Now the brilliant idea obviously is
that subtracting the 'Nub Sieve' of the list of prime factors from
that very list
'kills two birds with one stone' in as it
[1] subtracts 1 from each of the *distinct* prime factors and
[2] reduces the number of identical prime factors by 1 each
at the very *same* time.
Writing the difference as a 'Hook' and
(- ~:) q: n
1 2 2 2 2 3 4 6
building the product and
*/ (- ~:) q: n
1152
realizing that (*/) is the 'Inverse' of (q:)
using 'Under (Dual)' one gets the final expression
(- ~:) &. q: n
1152
~-----~-----~
-M
At 2017-04-02 14:26, you wrote:
Andrew Nikitin posted the expression to the forum 2009-11-03
http://www.jsoftware.com/pipermail/programming/2009-November/016746.html.
You can derive it by more conventional expressions for computing the
totient, such as the expression */(p-1)*p^e-1 which immediately precedes it
in the dictionary.
On Sun, Apr 2, 2017 at 12:39 AM, Martin Kreuzer <i...@airkreuzer.com> wrote:
> Hi all -
> In section 'Primes' of the Vocabul I found this line of code (at the very
> end, function no 5):
> (- ~:) &. q: y
> I do know that it is another way to calculate the totient of y, and
> I'm somehow familiar with the use of (~:) and (&.) and (q:), but
> have not yet found any documentation of this construct (- ~:)
> [btw, these seem to work too (+ ~:), (* ~:), (% ~:)]
> Where should I explore further..?
> -M
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
