Primes - Revision history

WikiSysop at 20:59, 17 July 2020

2020-07-17T20:59:30Z

← Older revision		Revision as of 16:59, 17 July 2020
Line 36:		Line 36:

	⍴π1		⍴π1
	0</pre></apll>		0
			c←×/(a b)←1π?2⍴10*25x ⍝ Create two random 25-digit primes and their product
			a b c
			213379889007584782100623 7822072437371562999056237 1669072948495632279507879309030439547039369735651
			πc ⍝ Factor the 50-digit number
			213379889007584782100623 7822072437371562999056237
			⎕T-(πc)⊢⊢⎕T ⍝ How many seconds of CPU time to factor a 50-digit number?
			0.6204937084112316</pre></apll>

Sudleyplace at 23:07, 15 April 2018

2018-04-15T23:07:53Z

← Older revision		Revision as of 19:07, 15 April 2018
Line 23:		Line 23:
	<p>For example,</p>		<p>For example,</p>

	<apll>~~      π120~~<~~br /~~>		<apll><pre>
	2 2 2 3 5~~<br />~~		π120
	~~<br />~~		2 2 2 3 5
	~~      ~~×/⎕←π⎕←¯1+2*62~~<br />~~
	4611686018427387903~~<br />~~		×/⎕←π⎕←¯1+2*62
	3 715827883 2147483647~~<br />~~		4611686018427387903
	4611686018427387903~~<br />~~		3 715827883 2147483647
	~~<br />~~		4611686018427387903
	~~      ~~π¯1+2*61~~<br />~~
	2305843009213693951~~<br />~~		π¯1+2*61
	~~<br />~~		2305843009213693951
	~~      ~~⍴π1<br />
	0</apll>		⍴π1
			0</pre></apll>


Line 118:		Line 119:
	<p>For example, how many primes are less then or equal to <apll>1000003</apll>?</p>		<p>For example, how many primes are less then or equal to <apll>1000003</apll>?</p>

	<apll>~~      ~~¯2π1000003<br />		<apll><pre>
	~~15485927~~</apll>		¯2π1000003
			15485927</pre></apll>

	== Previous Prime Function ==		== Previous Prime Function ==
Line 127:		Line 129:
	<p>For example, what is the prime that immediately precedes <apll>1000000</apll>?</p>		<p>For example, what is the prime that immediately precedes <apll>1000000</apll>?</p>

	<apll>~~      ~~¯1π1000000<br />		<apll><pre>
	~~999983~~</apll>		¯1π1000000
			999983</pre></apll>

	== Primality Test ==		== Primality Test ==
Line 136:		Line 139:
	<p>For example, is <apll>1000003</apll> a prime?</p>		<p>For example, is <apll>1000003</apll> a prime?</p>

	<apll>~~      ~~0π1000003<br />		<apll><pre>
	1</apll>		0π1000003
			1</pre></apll>

	<p>List the primes up to 100</p>		<p>List the primes up to 100</p>

	<apll>~~      ⍸0π⍳100~~<~~br /~~>		<apll><pre>
	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97</apll>		⍸0π⍳100
			2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97</pre></apll>

	== Next Prime Function ==		== Next Prime Function ==
Line 150:		Line 155:
	<p>For example, what is the next prime after <apll>1000000</apll>?</p>		<p>For example, what is the next prime after <apll>1000000</apll>?</p>

	<apll>~~      ~~1π1000000<br />		<apll><pre>
	~~1000003~~</apll>		1π1000000
			1000003</pre></apll>

	== Number Of Primes Function ==		== Number Of Primes Function ==
Line 159:		Line 165:
	<p>For example, what is the <apll>15485927</apll>th prime?</p>		<p>For example, what is the <apll>15485927</apll>th prime?</p>

	<apll>~~      ~~2π15485927<br />		<apll><pre>
	~~1000003~~</apll>		2π15485927
			1000003</pre></apll>

	== Divisor Count Function ==		== Divisor Count Function ==
Line 185:		Line 192:
	<p>The Rth prime function (<apll>¯2πR</apll>) gives the value of the Rth prime, as in</p>		<p>The Rth prime function (<apll>¯2πR</apll>) gives the value of the Rth prime, as in</p>

	<apll>~~      ~~¯2π100<br />		<apll><pre>
	~~541~~</apll>		¯2π100
			541</pre></apll>

	<p>The Index function (<apll>⍳R</apll>) produces a vector of integers of length <apll>R</apll>, as in</p>		<p>The Index function (<apll>⍳R</apll>) produces a vector of integers of length <apll>R</apll>, as in</p>

	<apll>~~      ⍳¯2π100~~<~~br /~~>		<apll><pre>
	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... 541<br /></apll>		⍳¯2π100
			1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... 541</pre></apll>

	<p>The Primality Test function (<apll>0πR</apll>) returns a <apll>1</apll> if the corresponding element in <apll>R</apll> is a prime, <apll>0</apll> otherwise, as in</p>		<p>The Primality Test function (<apll>0πR</apll>) returns a <apll>1</apll> if the corresponding element in <apll>R</apll> is a prime, <apll>0</apll> otherwise, as in</p>

	<apll>~~      0π⍳¯2π100~~<~~br /~~>		<apll><pre>
	0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 ... 1<br /></apll>		0π⍳¯2π100
			0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 ... 1</pre></apll>

	<p>The Indices function (<apll>⍸R</apll>) converts the argument <apll>R</apll> to indices (equivalent to <apll>(,R)/⍳×/⍴R</apll>), as in</p>		<p>The Indices function (<apll>⍸R</apll>) converts the argument <apll>R</apll> to indices (equivalent to <apll>(,R)/⍳×/⍴R</apll>), as in</p>

	<apll>~~      ⍸0π⍳¯2π100~~<~~br /~~>		<apll><pre>
	2 3 5 7 11 13 17 19 23 29 31 37 41 43 ... 541<br /></apll>		⍸0π⍳¯2π100
			2 3 5 7 11 13 17 19 23 29 31 37 41 43 ... 541</pre></apll>

	<p>Finally, those numbers may be added together using plus reduction (<apll>+/</apll>), as in</p>		<p>Finally, those numbers may be added together using plus reduction (<apll>+/</apll>), as in</p>

	<apll>~~      ~~+/⍸0π⍳¯2π100<br />		<apll><pre>
	~~24133~~</apll>		+/⍸0π⍳¯2π100
			24133</pre></apll>

	== Notes ==		== Notes ==

	<sup>1</sup> [https://en.wikipedia.org/wiki/Divisor_function Formula for sum of divisors]		<sup>1</sup> [https://en.wikipedia.org/wiki/Divisor_function Formula for sum of divisors]

WikiSysop at 00:29, 31 July 2015

2015-07-31T00:29:22Z

← Older revision		Revision as of 20:29, 30 July 2015
Line 58:		Line 58:
	<tr>		<tr>
	<td><apll>¯2</apll></td>		<td><apll>¯2</apll></td>
	<td>  ~~Nth~~ prime function</td>		<td>  Rth prime function</td>
	</tr>		</tr>

Line 112:		Line 112:
	<br />		<br />

	== ~~Nth~~ Prime Function ==		== Rth Prime Function ==

	<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>		<p>The Rth 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>

	<p>For example, how many primes are less then or equal to <apll>1000003</apll>?</p>		<p>For example, how many primes are less then or equal to <apll>1000003</apll>?</p>

WikiSysop: /* Examples */

2015-07-31T00:27:07Z

Examples

← Older revision		Revision as of 20:27, 30 July 2015
Line 193:		Line 193:
	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... 541<br /></apll>		1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... 541<br /></apll>

	<p>The ~~Prime~~ Test function (<apll>0πR</apll>) returns a <apll>1</apll> if the corresponding element in <apll>R</apll> is a prime, <apll>0</apll> otherwise, as in</p>		<p>The Primality Test function (<apll>0πR</apll>) returns a <apll>1</apll> if the corresponding element in <apll>R</apll> is a prime, <apll>0</apll> otherwise, as in</p>

	<apll>      0π⍳¯2π100<br />		<apll>      0π⍳¯2π100<br />

WikiSysop: /* Examples */

2015-07-31T00:24:46Z

Examples

← Older revision		Revision as of 20:24, 30 July 2015
Line 198:		Line 198:
	0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 ... 1<br /></apll>		0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 ... 1<br /></apll>

	<p>The Indices function (<apll>⍸R</apll>) converts the argument <apll>R</apll> to indices (equivalent to <apll>(,R)/~~,⍳⍴R~~</apll>), as in</p>		<p>The Indices function (<apll>⍸R</apll>) converts the argument <apll>R</apll> to indices (equivalent to <apll>(,R)/⍳×/⍴R</apll>), as in</p>

	<apll>      ⍸0π⍳¯2π100<br />		<apll>      ⍸0π⍳¯2π100<br />

WikiSysop at 00:22, 31 July 2015

2015-07-31T00:22:56Z

@@ Line 178: / Line 178: @@
 <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>
 == Notes ==
-<sup>1</sup> [http://planetmath.org/encyclopedia/FormulaForSumOfDivisors.html Formula for sum of divisors]
+<sup>1</sup> [https://en.wikipedia.org/wiki/Divisor_function Formula for sum of divisors]

WikiSysop: /* Primality Test */

2015-05-07T19:10:30Z

Primality Test

← Older revision		Revision as of 15:10, 7 May 2015
Line 138:		Line 138:
	<apll>      0π1000003<br />		<apll>      0π1000003<br />
	1</apll>		1</apll>

			<p>List the primes up to 100</p>

			<apll>      ⍸0π⍳100<br />
			2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97</apll>

	== Next Prime Function ==		== Next Prime Function ==

WikiSysop at 15:55, 8 March 2013

2013-03-08T15:55:10Z

← Older revision		Revision as of 11:55, 8 March 2013
Line 48:		Line 48:
	<td></td>		<td></td>
	<td></td>		<td></td>
	<td>returns an ~~integer scalar~~ whose ~~value depends~~ upon which number-theoretic function is chosen by <apll>L</apll> ~~to be~~ applied to <apll>R</apll>.</td>		<td>returns an array whose values depend upon which number-theoretic function chosen by <apll>L</apll> is applied to <apll>R</apll>.</td>
	</tr>		</tr>
	</table>		</table>
Line 104:		Line 104:
	</tr>		</tr>
	<tr>		<tr>
	<td><apll>R</apll> is ~~a scalar~~ consisting of a positive ~~integer~~ to which one of the above functions is applied.</td>		<td><apll>R</apll> is an array consisting of positive integers to which one of the above functions is applied, element by element.</td>
	</tr>		</tr>
	<tr>		<tr>
	<td><apll>Z</apll> is an integer.</td>		<td><apll>Z</apll> is an integer array of the same shape as <apll>R</apll>.</td>
	</tr>		</tr>
	</table>		</table>
Line 115:		Line 115:

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

			<p>For example, how many primes are less then or equal to <apll>1000003</apll>?</p>

			<apll>      ¯2π1000003<br />
			15485927</apll>

	== Previous Prime Function ==		== Previous Prime Function ==

	<p>The previous prime function (<apll>¯1πR</apll>) returns the prime that immediately precedes <apll>R</apll>.</p>		<p>The previous prime function (<apll>¯1πR</apll>) returns the prime that immediately precedes <apll>R</apll>.</p>

			<p>For example, what is the prime that immediately precedes <apll>1000000</apll>?</p>

			<apll>      ¯1π1000000<br />
			999983</apll>

	== Primality Test ==		== Primality Test ==

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

			<p>For example, is <apll>1000003</apll> a prime?</p>

			<apll>      0π1000003<br />
			1</apll>

	== Next Prime Function ==		== Next Prime Function ==

	<p>The next prime function (<apll>1π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>

			<p>For example, what is the next prime after <apll>1000000</apll>?</p>

			<apll>      1π1000000<br />
			1000003</apll>

	== Number Of Primes Function ==		== Number Of Primes Function ==

	<p>The number of primes function (<apll>2πR</apll>) returns number of primes less than or equal to <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>

			<p>For example, what is the <apll>15485927</apll>th prime?</p>

			<apll>      2π15485927<br />
			1000003</apll>

	== Divisor Count Function ==		== Divisor Count Function ==

WikiSysop at 03:44, 26 February 2012

2012-02-26T03:44:26Z

← Older revision		Revision as of 23:44, 25 February 2012
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>  ~~Divisor count~~ function</td>		<td>  Nth prime function</td>
	</tr>		</tr>

	<tr>		<tr>
	<td><apll>1</apll></td>		<td><apll>¯1</apll></td>
	<td>  ~~Divisor sum~~ function</td>		<td>  Previous prime function</td>
	</tr>		</tr>

	<tr>		<tr>
	<td><apll>2</apll></td>		<td><apll> 0</apll></td>
	<td>  Primality test function</td>		<td>  Primality test function</td>
	</tr>		</tr>

	<tr>		<tr>
	<td><apll>3</apll></td>		<td><apll> 1</apll></td>
	<td>  Next prime function</td>		<td>  Next prime function</td>
	</tr>		</tr>

	<tr>		<tr>
	<td><apll>4</apll></td>		<td><apll> 2</apll></td>
	<td>  ~~Previous prime~~ function</td>		<td>  Number of primes function</td>
	</tr>		</tr>

	<tr>		<tr>
	<td><apll>5</apll></td>		<td><apll>10</apll></td>
	<td>  ~~Nth prime~~ function</td>		<td>  Divisor count function</td>
	</tr>		</tr>

	<tr>		<tr>
	<td><apll>6</apll></td>		<td><apll>11</apll></td>
	<td>  ~~Number of primes~~ function</td>		<td>  Divisor sum function</td>
	</tr>		</tr>

	<tr>		<tr>
	<td><apll>7</apll></td>		<td><apll>12</apll></td>
	<td>  Möbius function function</td>		<td>  Möbius function function</td>
	</tr>		</tr>

	<tr>		<tr>
	<td><apll>8</apll></td>		<td><apll>13</apll></td>
	<td>  Euler totient function</td>		<td>  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 prime. This 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>

WikiSysop: /* Möbius Function */

2011-04-07T13:54:22Z

Möbius Function

← Older revision		Revision as of 09:54, 7 April 2011
Line 142:		Line 142:
	== Möbius Function ==		== Möbius Function ==

	<p>The 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>.		<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>

	== Totient Function ==		== Totient Function ==