Primes: Difference between revisions
From NARS2000
Jump to navigationJump to search
No edit summary |
|||
| Line 57: | Line 57: | ||
<table border="0" cellpadding="1" cellspacing="0" rules="none" summary="" style="margin-left: 20px;"> | <table border="0" cellpadding="1" cellspacing="0" rules="none" summary="" style="margin-left: 20px;"> | ||
<tr> | <tr> | ||
<td><apll> | <td><apll>¯2</apll></td> | ||
<td> | <td> Nth prime function</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td><apll> | <td><apll>¯1</apll></td> | ||
<td> | <td> Previous prime function</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td><apll> | <td><apll> 0</apll></td> | ||
<td> Primality test function</td> | <td> Primality test function</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td><apll> | <td><apll> 1</apll></td> | ||
<td> Next prime function</td> | <td> Next prime function</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td><apll> | <td><apll> 2</apll></td> | ||
<td> | <td> Number of primes function</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td><apll> | <td><apll>10</apll></td> | ||
<td> | <td> Divisor count function</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td><apll> | <td><apll>11</apll></td> | ||
<td> | <td> Divisor sum function</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td><apll> | <td><apll>12</apll></td> | ||
<td> Möbius function function</td> | <td> Möbius function function</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td><apll> | <td><apll>13</apll></td> | ||
<td> Euler totient function</td> | <td> Euler totient function</td> | ||
</tr> | </tr> | ||
| Line 112: | Line 112: | ||
<br /> | <br /> | ||
== | == Nth Prime Function == | ||
<p>The | <p>The Nth prime function (<apll>¯2πR</apll>) returns the <apll>R</apll><sup>th</sup> prime where <apll>2</apll> is the first prime. This function is sensitive to the index origin.</p> | ||
== | == Previous Prime Function == | ||
<p>The | <p>The previous prime function (<apll>¯1πR</apll>) returns the prime that immediately precedes <apll>R</apll>.</p> | ||
== Primality Test == | == Primality Test == | ||
<p>The primality test function (<apll> | <p>The primality test function (<apll>0πR</apll>) returns a <apll>1</apll> if <apll>R</apll> is a prime and <apll>0</apll> if not.</p> | ||
== Next Prime Function == | == Next Prime Function == | ||
<p>The next prime function (<apll> | <p>The next prime function (<apll>1πR</apll>) returns the prime that immediately follows <apll>R</apll>.</p> | ||
== | == Number Of Primes Function == | ||
<p>The | <p>The number of primes function (<apll>2πR</apll>) returns number of primes less than or equal to <apll>R</apll>.</p> | ||
== | == Divisor Count Function == | ||
<p>The | <p>The divisor count function (<apll>10πR</apll>) returns the number of divisors of a number. It is the same as <apll>×/1+∪⍦πR</apll> where <apll>πR</apll> returns the prime factors of <apll>R</apll> and <apll>∪⍦</apll> counts the number of occurrences of unique elements (in this case, the exponent vector of the unique primes). A divisor then consists of the product of zero or more of the unique primes which is why <apll>×/1+</apll> counts them.</p> | ||
== | == Divisor Sum Function == | ||
<p>The | <p>The divisor sum function (<apll>11πR</apll>) returns the sum of the divisors of a number. It is the same as <apll>×/(¯1+(∪f)*1+∪⍦f)÷¯1+∪f←πR</apll><sup>1</sup>. This function is used to recognize [http://en.wikipedia.org/wiki/Deficient_number deficient], [http://en.wikipedia.org/wiki/Perfect_number perfect], and [http://en.wikipedia.org/wiki/Abundant_number abundant] numbers.</p> | ||
== Möbius Function == | == Möbius Function == | ||
<p>The [http://en.wikipedia.org/wiki/M%C3%B6bius_function Möbius function] (<apll> | <p>The [http://en.wikipedia.org/wiki/M%C3%B6bius_function Möbius function] (<apll>12πR</apll>) returns information about the square free properties of <apll>R</apll>. If <apll>R</apll> is [http://en.wikipedia.org/wiki/Square-free_integer square free], the function returns <apll>1</apll> if <apll>R</apll> has an even number of prime factors, and <apll>¯1</apll> if it has an odd number of prime factors. If the argument is not square free, the function returns <apll>0</apll>. It is used in the [http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula Möbius Inversion Formula] to invert general arithmetic functions.</p> | ||
== Totient Function == | == Totient Function == | ||
<p>The totient function (<apll> | <p>The totient function (<apll>13πR</apll>) (also called [http://en.wikipedia.org/wiki/Euler_phi Euler's Totient Function]) returns the number of positive integers less than or equal to <apll>R</apll> that are relatively prime to it (i.e., having no common positive factors other than 1). | ||
</p> | </p> | ||
Revision as of 22:44, 25 February 2012
|
||||
| R is a scalar or one-element vector consisting of a positive integer to be factored. | ||||
| Z is an integer vector whose values are the prime factors of R. |
For example,
π120
2 2 2 3 5
×/⎕←π⎕←¯1+2*62
4611686018427387903
3 715827883 2147483647
4611686018427387903
π¯1+2*61
2305843009213693951
⍴π1
0
|
||||||||||||||||||
L is an integer scalar whose meaning is as follows
|
||||||||||||||||||
| R is a scalar consisting of a positive integer to which one of the above functions is applied. | ||||||||||||||||||
| Z is an integer. |
Nth Prime Function
The Nth prime function (¯2πR) returns the Rth prime where 2 is the first prime. This function is sensitive to the index origin.
Previous Prime Function
The previous prime function (¯1πR) returns the prime that immediately precedes R.
Primality Test
The primality test function (0πR) returns a 1 if R is a prime and 0 if not.
Next Prime Function
The next prime function (1πR) returns the prime that immediately follows R.
Number Of Primes Function
The number of primes function (2πR) returns number of primes less than or equal to R.
Divisor Count Function
The divisor count function (10πR) returns the number of divisors of a number. It is the same as ×/1+∪⍦πR where πR returns the prime factors of R and ∪⍦ counts the number of occurrences of unique elements (in this case, the exponent vector of the unique primes). A divisor then consists of the product of zero or more of the unique primes which is why ×/1+ counts them.
Divisor Sum Function
The divisor sum function (11πR) returns the sum of the divisors of a number. It is the same as ×/(¯1+(∪f)*1+∪⍦f)÷¯1+∪f←πR1. This function is used to recognize deficient, perfect, and abundant numbers.
Möbius Function
The Möbius function (12πR) returns information about the square free properties of R. If R is square free, the function returns 1 if R has an even number of prime factors, and ¯1 if it has an odd number of prime factors. If the argument is not square free, the function returns 0. It is used in the Möbius Inversion Formula to invert general arithmetic functions.
Totient Function
The totient function (13πR) (also called Euler's Totient Function) returns the number of positive integers less than or equal to R that are relatively prime to it (i.e., having no common positive factors other than 1).
