Reply
 
LinkBack Thread Tools Search this Thread Display Modes
  #1   Report Post  
Old August 10th 07, 04:20 PM posted to microsoft.public.excel.worksheet.functions
external usenet poster
 
First recorded activity by ExcelBanter: Jul 2006
Posts: 1,560
Default Eulier Totient Function

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

  #2   Report Post  
Old August 10th 07, 04:32 PM posted to microsoft.public.excel.worksheet.functions
external usenet poster
 
First recorded activity by ExcelBanter: Sep 2006
Posts: 3,718
Default Eulier Totient Function

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?

  #3   Report Post  
Old August 10th 07, 04:47 PM posted to microsoft.public.excel.worksheet.functions
external usenet poster
 
First recorded activity by ExcelBanter: Mar 2007
Posts: 1,231
Default Eulier Totient Function

"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.


  #4   Report Post  
Old August 10th 07, 04:55 PM posted to microsoft.public.excel.worksheet.functions
external usenet poster
 
First recorded activity by ExcelBanter: Jul 2006
Posts: 4,393
Default Eulier Totient Function

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?



  #5   Report Post  
Old September 11th 07, 01:29 AM posted to microsoft.public.excel.worksheet.functions
external usenet poster
 
First recorded activity by ExcelBanter: Jul 2007
Posts: 84
Default Eulier Totient Function

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



  #6   Report Post  
Old September 11th 07, 01:37 AM posted to microsoft.public.excel.worksheet.functions
external usenet poster
 
First recorded activity by ExcelBanter: Jul 2007
Posts: 84
Default Eulier Totient Function

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

  #7   Report Post  
Old September 11th 07, 03:14 PM posted to microsoft.public.excel.worksheet.functions
external usenet poster
 
First recorded activity by ExcelBanter: Jul 2006
Posts: 947
Default Eulier Totient Function

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:[email protected]
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



  #8   Report Post  
Old September 11th 07, 04:25 PM posted to microsoft.public.excel.worksheet.functions
external usenet poster
 
First recorded activity by ExcelBanter: Jul 2006
Posts: 947
Default Eulier Totient Function

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


  #9   Report Post  
Old September 11th 07, 11:02 PM posted to microsoft.public.excel.worksheet.functions
external usenet poster
 
First recorded activity by ExcelBanter: Jul 2007
Posts: 84
Default Eulier Totient Function

Dana,

OT and for fun: Do you know how to collect the prime factors geometrically?

This is the Squarest Rectangle Method:

Take Int(Sqrt(n)) as the side length of the largest square of area <= n.
If the square's area = n exactly, each side is a divisor of n.
But if area < n, take the difference and consider it as bricks laid on
top of the square (left to right) forming one or more extra rows and/or
a partial row.
If the top row is complete, this is the squarest rectangle of area n,
and both sides are divisors.
But if the top row is incomplete, remove the rightmost column of bricks,
distribute on top as before, and if it's not a solid rectangle, keep
removing the remaining columns from the right until the top row is
complete. Then each side is a divisor of n.
Eventually, you always end up with a solid rectangle, which gives you
two divisors to break down further by the same method, or else a single
column of bricks whose height must be prime (by exhaustion), which gives
you a prime factor.
In this way, you can collect all prime divisors of n.

- David

Dana DeLouis wrote:
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

  #10   Report Post  
Old January 20th 21, 03:30 PM
Junior Member
 
First recorded activity by ExcelBanter: Jan 2021
Posts: 4
Default

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) ) )

)


Reply
Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
how do you write format results of a function within a function? sangee Excel Worksheet Functions 3 June 14th 07 12:45 AM
LINKEDRANGE function - a complement to the PULL function (for getting values from a closed workbook) [email protected] Excel Worksheet Functions 0 September 5th 06 03:44 PM
Offset function with nested match function not finding host ss. MKunert Excel Worksheet Functions 1 March 21st 06 10:46 PM
Emulate Index/Match combo function w/ VBA custom function Spencer Hutton Excel Worksheet Functions 2 May 2nd 05 05:26 PM
Nested IF Function, Date Comparing, and NetworkDays Function carl Excel Worksheet Functions 2 December 29th 04 09:57 PM


All times are GMT +1. The time now is 09:47 PM.

Powered by vBulletin® Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
Copyright 2004-2021 ExcelBanter.
The comments are property of their posters.
 

About Us

"It's about Microsoft Excel"

 

Copyright © 2017