Difference between revisions of "Primes"

From NARS2000
Jump to navigationJump to search
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>0</apll></td>
+
         <td><apll>¯2</apll></td>
         <td>&nbsp;&nbsp;Divisor count function</td>
+
         <td>&nbsp;&nbsp;Nth prime function</td>
 
       </tr>
 
       </tr>
  
 
       <tr>
 
       <tr>
         <td><apll>1</apll></td>
+
         <td><apll>¯1</apll></td>
         <td>&nbsp;&nbsp;Divisor sum function</td>
+
         <td>&nbsp;&nbsp;Previous prime function</td>
 
       </tr>
 
       </tr>
  
 
       <tr>
 
       <tr>
         <td><apll>2</apll></td>
+
         <td><apll>&nbsp;0</apll></td>
 
         <td>&nbsp;&nbsp;Primality test function</td>
 
         <td>&nbsp;&nbsp;Primality test function</td>
 
       </tr>
 
       </tr>
  
 
       <tr>
 
       <tr>
         <td><apll>3</apll></td>
+
         <td><apll>&nbsp;1</apll></td>
 
         <td>&nbsp;&nbsp;Next prime function</td>
 
         <td>&nbsp;&nbsp;Next prime function</td>
 
       </tr>
 
       </tr>
  
 
       <tr>
 
       <tr>
         <td><apll>4</apll></td>
+
         <td><apll>&nbsp;2</apll></td>
         <td>&nbsp;&nbsp;Previous prime function</td>
+
         <td>&nbsp;&nbsp;Number of primes function</td>
 
       </tr>
 
       </tr>
  
 
       <tr>
 
       <tr>
         <td><apll>5</apll></td>
+
         <td><apll>10</apll></td>
         <td>&nbsp;&nbsp;Nth prime function</td>
+
         <td>&nbsp;&nbsp;Divisor count function</td>
 
       </tr>
 
       </tr>
  
 
       <tr>
 
       <tr>
         <td><apll>6</apll></td>
+
         <td><apll>11</apll></td>
         <td>&nbsp;&nbsp;Number of primes function</td>
+
         <td>&nbsp;&nbsp;Divisor sum function</td>
 
       </tr>
 
       </tr>
  
 
       <tr>
 
       <tr>
         <td><apll>7</apll></td>
+
         <td><apll>12</apll></td>
 
         <td>&nbsp;&nbsp;Möbius function function</td>
 
         <td>&nbsp;&nbsp;Möbius function function</td>
 
       </tr>
 
       </tr>
  
 
       <tr>
 
       <tr>
         <td><apll>8</apll></td>
+
         <td><apll>13</apll></td>
 
         <td>&nbsp;&nbsp;Euler totient function</td>
 
         <td>&nbsp;&nbsp;Euler totient function</td>
 
       </tr>
 
       </tr>
Line 112: Line 112:
 
<br />
 
<br />
  
== Divisor Count Function ==
+
== Nth Prime Function ==
  
<p>The divisor count function (<apll>0π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>
+
<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 primeThis function is sensitive to the index origin.</p>
  
== Divisor Sum Function ==
+
== Previous Prime Function ==
  
<p>The divisor sum function (<apll>1π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>
+
<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>2πR</apll>) returns a <apll>1</apll> if <apll>R</apll> is a prime and <apll>0</apll> if not.</p>
+
<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>3πR</apll>) returns the prime that immediately follows <apll>R</apll>.</p>
+
<p>The next prime function (<apll>1πR</apll>) returns the prime that immediately follows <apll>R</apll>.</p>
  
== Previous Prime Function ==
+
== Number Of Primes Function ==
  
<p>The previous prime function (<apll>4πR</apll>) returns the prime that immediately precedes <apll>R</apll>.</p>
+
<p>The number of primes function (<apll>2πR</apll>) returns number of primes less than or equal to <apll>R</apll>.</p>
  
== Nth Prime Function ==
+
== Divisor Count Function ==
  
<p>The Nth prime function (<apll>5πR</apll>) returns the <apll>R</apll><sup>th</sup> prime where <apll>2</apll> is the first prime.</p>
+
<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>
  
== Number Of Primes Function ==
+
== Divisor Sum Function ==
  
<p>The number of primes function (<apll>6πR</apll>) returns number of primes less than or equal to <apll>R</apll>.</p>
+
<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>7π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>
+
<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>8π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>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 03:44, 26 February 2012

Z←πR returns an integer vector consisting of the prime factors of R.
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



Z←LπR returns an integer scalar whose value depends upon which number-theoretic function is chosen by L to be applied to R.
L is an integer scalar whose meaning is as follows
¯2   Nth prime function
¯1   Previous prime function
 0   Primality test function
 1   Next prime function
 2   Number of primes function
10   Divisor count function
11   Divisor sum function
12   Möbius function function
13   Euler totient function
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).

Notes

1 Formula for sum of divisors