Hi I was wondering if anyone has done Eulier Totient Function on Xcel at all?

Never heard "Eulier Totient Function". Is it the UDF Functions add in?


"David" wrote:

Hi I was wondering if anyone has done Eulier Totient Function on Xcel at all?

The OP misspelt Euler, so it is Euler's totient function
See http://en.wikipedia.org/wiki/Euler's_totient_function
best wishes
--
Bernard V Liengme
Microsoft Excel MVP
www.stfx.ca/people/bliengme
remove caps from email

"Teethless mama" wrote in message
...
Never heard "Eulier Totient Function". Is it the UDF Functions add in?


"David" wrote:

Hi I was wondering if anyone has done Eulier Totient Function on Xcel at
all?

Euler Totient Function, a.k.a Euler Phi Function Φ(N):

= $E$4 * PRODUCT(
IF(
($E$4-2=MMULT(--(0<MOD(ROW(INDIRECT("1:"&$E$4))*(0=MOD($E$4,
ROW(INDIRECT("1:"&$E$4)))), TRANSPOSE(ROW(INDIRECT("1:"&$E$4))))),
ROW(INDIRECT("1:"&$E$4))^0)) * ROW(INDIRECT("1:"&$E$4))*(0=MOD($E$4,
ROW(INDIRECT("1:"&$E$4))))
=0,
1,
1-1/(
($E$4-2=MMULT(--(0<MOD(ROW(INDIRECT("1:"&$E$4))*(0=MOD($E$4,
ROW(INDIRECT("1:"&$E$4)))), TRANSPOSE(ROW(INDIRECT("1:"&$E$4))))),
ROW(INDIRECT("1:"&$E$4))^0)) * ROW(INDIRECT("1:"&$E$4))*(0=MOD($E$4,
ROW(INDIRECT("1:"&$E$4))))
)))

Array-enter the above with Ctrl+Shift+Enter.

I would have replied sooner, but the implementation proved oilier than I
thought. It would actually have been easier to create a
user-defined-function with Visual Basic that would be faster and would
handle larger numbers.

Notes:
- Euler's totient function counts the number of coprimes to N that are
less than or equal to N.
- The formula used is N times the product of all 1-1/P, where the P's
are the distinct prime divisors of N.
- The number N in cell E4 mustn't be too large. N=1000 -- computing a
million-element array. This function may calculate slooowly.
- I broke up the lines to show that the comparison in the IF's first
argument uses the the same expression as the denominator in the last
argument. The expression is a list of primes interspersed with zeros.

:)

David


Bernard Liengme wrote:

The OP misspelt Euler, so it is Euler's totient function
See http://en.wikipedia.org/wiki/Euler's_totient_function
best wishes

Postscript: Some newsreaders may not be showing the exponentiation signs
in the formula. You should have:

ROW(INDIRECT("1:"&$E$4))^0

both times, and not:

ROW(INDIRECT("1:"&$E$4))0

- David

David Hilberg wrote:
Euler Totient Function, a.k.a Euler Phi Function Φ(N):

= $E$4 * PRODUCT(
IF(
($E$4-2=MMULT(--(0<MOD(ROW(INDIRECT("1:"&$E$4))*(0=MOD($E$4,
ROW(INDIRECT("1:"&$E$4)))), TRANSPOSE(ROW(INDIRECT("1:"&$E$4))))),
ROW(INDIRECT("1:"&$E$4))^0)) * ROW(INDIRECT("1:"&$E$4))*(0=MOD($E$4,
ROW(INDIRECT("1:"&$E$4))))
=0,
1,
1-1/(
($E$4-2=MMULT(--(0<MOD(ROW(INDIRECT("1:"&$E$4))*(0=MOD($E$4,
ROW(INDIRECT("1:"&$E$4)))), TRANSPOSE(ROW(INDIRECT("1:"&$E$4))))),
ROW(INDIRECT("1:"&$E$4))^0)) * ROW(INDIRECT("1:"&$E$4))*(0=MOD($E$4,
ROW(INDIRECT("1:"&$E$4))))
)))

Array-enter the above with Ctrl+Shift+Enter.

I would have replied sooner, but the implementation proved oilier than I
thought. It would actually have been easier to create a
user-defined-function with Visual Basic that would be faster and would
handle larger numbers.

Notes:
- Euler's totient function counts the number of coprimes to N that are
less than or equal to N.
- The formula used is N times the product of all 1-1/P, where the P's
are the distinct prime divisors of N.
- The number N in cell E4 mustn't be too large. N=1000 -- computing a
million-element array. This function may calculate slooowly.
- I broke up the lines to show that the comparison in the IF's first
argument uses the the same expression as the denominator in the last
argument. The expression is a list of primes interspersed with zeros.

:)

David


Bernard Liengme wrote:

The OP misspelt Euler, so it is Euler's totient function
See http://en.wikipedia.org/wiki/Euler's_totient_function
best wishes

It would actually have been easier to create a user-defined-function

Hi David. I could not find any identities where we could cut down the
number of loops.
Do you know of any? Hate to loop this many times on large n.

Function EulerPhi(n)
Dim T As Long
Dim j As Long
With WorksheetFunction
For j = 1 To n
T = T - (.Gcd(j, n) = 1)
Next j
End With
EulerPhi = T
End Function

Two easy checks:

?EulerPhi(10000)
4000
?EulerPhi(100000)
40000

--
Dana DeLouis
Windows XP & Excel 2007


"David Hilberg" wrote in message
news:aklFi.1232$rw3.513@trndny04...
Euler Totient Function, a.k.a Euler Phi Function ?(N):

= $E$4 * PRODUCT(
IF(
($E$4-2=MMULT(--(0<MOD(ROW(INDIRECT("1:"&$E$4))*(0=MOD($E$4,
ROW(INDIRECT("1:"&$E$4)))), TRANSPOSE(ROW(INDIRECT("1:"&$E$4))))),
ROW(INDIRECT("1:"&$E$4))^0)) * ROW(INDIRECT("1:"&$E$4))*(0=MOD($E$4,
ROW(INDIRECT("1:"&$E$4))))
=0,
1,
1-1/(
($E$4-2=MMULT(--(0<MOD(ROW(INDIRECT("1:"&$E$4))*(0=MOD($E$4,
ROW(INDIRECT("1:"&$E$4)))), TRANSPOSE(ROW(INDIRECT("1:"&$E$4))))),
ROW(INDIRECT("1:"&$E$4))^0)) * ROW(INDIRECT("1:"&$E$4))*(0=MOD($E$4,
ROW(INDIRECT("1:"&$E$4))))
)))

Array-enter the above with Ctrl+Shift+Enter.

I would have replied sooner, but the implementation proved oilier than I
thought. It would actually have been easier to create a
user-defined-function with Visual Basic that would be faster and would
handle larger numbers.

Notes:
- Euler's totient function counts the number of coprimes to N that are
less than or equal to N.
- The formula used is N times the product of all 1-1/P, where the P's are
the distinct prime divisors of N.
- The number N in cell E4 mustn't be too large. N=1000 -- computing a
million-element array. This function may calculate slooowly.
- I broke up the lines to show that the comparison in the IF's first
argument uses the the same expression as the denominator in the last
argument. The expression is a list of primes interspersed with zeros.

:)

David


Bernard Liengme wrote:

The OP misspelt Euler, so it is Euler's totient function
See http://en.wikipedia.org/wiki/Euler's_totient_function
best wishes

Hi David. I could not find any identities where we could cut down the
number of loops.

Oh! Never mind!! :(
Just call a Prime Factor routine, keeping just the prime numbers.
For example, if n=2,000,000, then just collect 2 & 5.

n = 2,000,000;
Hence:

n*(1 - 1/2)*(1 - 1/5)
800,000

Which checks:

EulerPhi(n)
800,000
--
Dana DeLouis
<snip

I thought I would refresh this with an updated version of your excellent formula that uses the new Let function

=LET(
x, SEQUENCE(N13),
y, (0=MOD(N13,x)),
z, MMULT(--(0<MOD(x*y, TRANSPOSE(x))),x^0),
p, (N13-2=z),
q, p*x*y,

N13 * PRODUCT(IF(q = 0, 1, 1 - 1 / (q) ) )

)

"David" wrote...
Hi I was wondering if anyone has done Eulier Totient Function on Xcel
at all?

You mean Euler's Totient function?

Anyway, Excel isn't a good choice for number theory.