Home |
Search |
Today's Posts |
#1
Posted to microsoft.public.excel.worksheet.functions
|
|||
|
|||
Eulier Totient Function
Hi I was wondering if anyone has done Eulier Totient Function on Xcel at all?
|
#2
Posted to microsoft.public.excel.worksheet.functions
|
|||
|
|||
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
Posted to microsoft.public.excel.worksheet.functions
|
|||
|
|||
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
Posted to microsoft.public.excel.worksheet.functions
|
|||
|
|||
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
Posted to microsoft.public.excel.worksheet.functions
|
|||
|
|||
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
Posted to microsoft.public.excel.worksheet.functions
|
|||
|
|||
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
Posted to microsoft.public.excel.worksheet.functions
|
|||
|
|||
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: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 |
#8
Posted to microsoft.public.excel.worksheet.functions
|
|||
|
|||
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
Posted to microsoft.public.excel.worksheet.functions
|
|||
|
|||
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
|
|||
|
|||
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 |
Display Modes | |
|
|
Similar Threads | ||||
Thread | Forum | |||
how do you write format results of a function within a function? | Excel Worksheet Functions | |||
LINKEDRANGE function - a complement to the PULL function (for getting values from a closed workbook) | Excel Worksheet Functions | |||
Offset function with nested match function not finding host ss. | Excel Worksheet Functions | |||
Emulate Index/Match combo function w/ VBA custom function | Excel Worksheet Functions | |||
Nested IF Function, Date Comparing, and NetworkDays Function | Excel Worksheet Functions |