Rosetta Code

Erdös-Selfridge categorization of primes: Difference between revisions

Page Discussion

Erdös-Selfridge categorization of primes (view source)

Revision as of 15:17, 6 April 2024

18,316 bytes added ,  1 month ago
added RPL
(added RPL)
 
(7 intermediate revisions by 5 users not shown)
Line 7:
=={{header|C++}}==
{{libheader|Primesieve}}
<langsyntaxhighlight lang="cpp">#include <algorithm>
#include <cassert>
#include <iomanip>
Line 101:
<< " count = " << v.size() << '\n';
}
}</langsyntaxhighlight>
 
{{out}}
Line 149:
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)]
<langsyntaxhighlight lang="fsharp">
// Erdös-Selfridge categorization of primes. Nigel Galloway: April 12th., 2022
let rec fG n g=match n,g with ((_,1),_)|(_,[])->n |((_,p),h::_) when h>p->n |((p,q),h::_) when q%h=0->fG (p,q/h) g |(_,_::g)->fG n g
Line 155:
fN 200|>Seq.iteri(fun n g->printfn "Category %d: %A" (n+1) g)
fN 1000000|>Seq.iteri(fun n g->printfn "Category %d: first->%d last->%d count->%d" (n+1) (List.head g) (List.last g) (
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 191:
=={{header|Factor}}==
{{works with|Factor|0.99 2022-04-03}}
<langsyntaxhighlight lang="factor">USING: assocs combinators formatting grouping grouping.extras io
kernel math math.primes math.primes.factors math.statistics
prettyprint sequences sequences.deep ;
Line 224:
 
200 categories categories... nl
1,000,000 categories categories.</langsyntaxhighlight>
{{out}}
<pre>
Line 266:
{{trans|Wren}}
{{libheader|Go-rcu}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 345:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 351:
Same as Wren example.
</pre>
 
=={{header|J}}==
 
Implementation: <syntaxhighlight lang="j">pcat=: {{ assert. 1 p: y
1+>./0,pcat(q:1+y)-.2 3
}}M."0</syntaxhighlight>
 
Explanation: this is a recursive function defined only on primes. We memoize it for good performance.
 
To find the prime category of a prime, we find the prime factorization of the next larger integer, and find the category of each of those factors other than 2 or 3. The prime's category is one greater than the maximum of these factor categories (with an explicit 0 for the maximum when there are factors greater than 3)
 
First 200 primes -- category is in left box, primes are in right box:
<syntaxhighlight lang="j"> (,.~<@#\) (</.~ pcat) p:i.200
┌─┬───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│1│2 3 5 7 11 17 23 31 47 53 71 107 127 191 383 431 647 863 971 1151 │
├─┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│2│13 19 29 41 43 59 61 67 79 83 89 97 101 109 131 137 139 149 167 179 197 199 211 223 229 239 241 251 263 269 271 281 283 293 307 317 349 359 367 373 419 433 439 449 461 479 499 503 509 557 563 577 587 593 599 619 641 643 659 709 719 743 751 761 769 809 827 839 881 919 929 953 967 991 1019 1033 1049 1069 1087 1103 1187 1223│
├─┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│3│37 103 113 151 157 163 173 181 193 227 233 257 277 311 331 337 347 353 379 389 397 401 409 421 457 463 467 487 491 521 523 541 547 569 571 601 607 613 631 653 683 701 727 733 773 787 797 811 821 829 853 857 859 877 883 911 937 947 983 997 1009 1013 1031 1039 1051 1061 1063 1091 1097 1117 1123 1153 1163 1171 1181 1193 1217│
├─┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│4│73 313 443 617 661 673 677 691 739 757 823 887 907 941 977 1093 1109 1129 1201 1213 │
├─┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│5│1021 │
└─┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘</syntaxhighlight>
 
First million primes, first column is category, second column is first prime in that category, third column is last prime in that category, final column is count of primes in that category:
 
<syntaxhighlight lang="j"> (,.~#\) (({.,{:,#)/.~ pcat) p:i.1e6
1 2 10616831 46
2 13 15482669 10497
3 37 15485863 201987
4 73 15485849 413891
5 1021 15485837 263109
6 2917 15485857 87560
7 15013 15484631 19389
8 49681 15485621 3129
9 532801 15472811 363
10 1065601 15472321 28
11 8524807 8524807 1</syntaxhighlight>
 
=={{header|Java}}==
Uses the PrimeGenerator class from [[Extensible prime generator#Java]].
<langsyntaxhighlight lang="java">import java.util.*;
 
public class ErdosSelfridge {
Line 430 ⟶ 469:
return Arrays.binarySearch(primes, prime);
}
}</langsyntaxhighlight>
 
{{out}}
Line 478 ⟶ 517:
=={{header|Julia}}==
{{trans|Raku}}
<langsyntaxhighlight lang="julia">using Primes
 
primefactors(n) = collect(keys(factor(n)))
Line 516 ⟶ 555:
 
testES(200, 1_000_000)
</langsyntaxhighlight>{{out}}
<pre>
First 200 primes by Erdös-Selfridge categories:
Line 540 ⟶ 579:
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
===Imperative implementation===
<lang Mathematica>ClearAll[SpecialPrimeFactors]
<syntaxhighlight lang="mathematica">ClearAll[SpecialPrimeFactors]
SpecialPrimeFactors[p_Integer] := FactorInteger[p + 1][[All, 1]]
 
Line 586 ⟶ 626:
TableForm[{First[#], Last[#], Length[#]} & /@ Rest[cs],
TableHeadings -> {Automatic, {"First", "Last", "Count"}},
TableAlignments -> Right]</langsyntaxhighlight>
{{out}}
<pre>
Line 636 ⟶ 676:
10 1065601 15472321 28
11 8524807 8524807 1</pre>
 
===Functional implementation===
<syntaxhighlight lang="mathematica">ClearAll[ErdosSelfridgeCategory, CategorySizesTable, categories];
 
ErdosSelfridgeCategory[n_] := ErdosSelfridgeCategory[n] =
If[ Last[primesToCheck = FactorInteger[n + 1][[All, 1]]] <= 3,
1,
1 + Max[ErdosSelfridgeCategory /@ primesToCheck]
];
 
(* Display the first 200 primes allocated to their category *)
 
categories = GatherBy[Prime[Range[200]], ErdosSelfridgeCategory];
 
Print["First 200 primes by Erdös-Selfridge category:\n"]
 
Do[
Print["Class ", i, ":"];
Print[
TableForm[
Partition[
Map[StringPadLeft[ToString[#], 5] &, categories[[i]]], UpTo[12]],
TableAlignments -> Right]
],
{i, Length[categories]}
];
 
(* Show the number of primes in each category for the first million primes *)
 
Print["Calculating Erdős-Selfridge categories for the first million primes...."]
 
{seconds, categories} =
AbsoluteTiming[GatherBy[Prime[Range[10^6]], ErdosSelfridgeCategory]];
 
Print["Calculation took ", seconds " seconds."];
 
CategorySizesTable[categories_List] :=
TableForm[
Table[{Min[categories[[n]]], Max[categories[[n]]],
Length[categories[[n]]]}, {n, Length[categories]}],
TableHeadings -> {Automatic, {"First", "Last", "Count"}},
TableAlignments -> Right];
 
Print[CategorySizesTable[categories]]</syntaxhighlight>
 
{{out}}
<pre>
First 200 primes by Erdös-Selfridge category:
 
Class 1:
2 3 5 7 11 17 23 31 47 53 71 107
127 191 383 431 647 863 971 1151
 
Class 2:
13 19 29 41 43 59 61 67 79 83 89 97
101 109 131 137 139 149 167 179 197 199 211 223
229 239 241 251 263 269 271 281 283 293 307 317
349 359 367 373 419 433 439 449 461 479 499 503
509 557 563 577 587 593 599 619 641 643 659 709
719 743 751 761 769 809 827 839 881 919 929 953
967 991 1019 1033 1049 1069 1087 1103 1187 1223
 
Class 3:
37 103 113 151 157 163 173 181 193 227 233 257
277 311 331 337 347 353 379 389 397 401 409 421
457 463 467 487 491 521 523 541 547 569 571 601
607 613 631 653 683 701 727 733 773 787 797 811
821 829 853 857 859 877 883 911 937 947 983 997
1009 1013 1031 1039 1051 1061 1063 1091 1097 1117 1123 1153
1163 1171 1181 1193 1217
 
Class 4:
73 313 443 617 661 673 677 691 739 757 823 887
907 941 977 1093 1109 1129 1201 1213
 
Class 5:
1021
 
Calculating Erdős-Selfridge categories for the first million primes....
Calculation took 10.2376 seconds.
 
First Last Count
1 2 10616831 46
2 13 15482669 10497
3 37 15485863 201987
4 73 15485849 413891
5 1021 15485837 263109
6 2917 15485857 87560
7 15013 15484631 19389
8 49681 15485621 3129
9 532801 15472811 363
10 1065601 15472321 28
11 8524807 8524807 1
</pre>
 
=={{header|Nim}}==
{{trans|Wren}}
Translation of Wren program with some modifications. As we don’t use a library to find the prime factors, we defined our own function to return the list without duplicates.
The program runs in about 2.5 seconds.
<syntaxhighlight lang="Nim">import std/[bitops, math, sequtils, strformat, strutils, tables]
 
type Sieve = object
data: seq[byte]
 
func `[]`(sieve: Sieve; idx: Positive): bool =
## Return value of element at index "idx".
let idx = idx shr 1
let iByte = idx shr 3
let iBit = idx and 7
result = sieve.data[iByte].testBit(iBit)
 
func `[]=`(sieve: var Sieve; idx: Positive; val: bool) =
## Set value of element at index "idx".
let idx = idx shr 1
let iByte = idx shr 3
let iBit = idx and 7
if val: sieve.data[iByte].setBit(iBit)
else: sieve.data[iByte].clearBit(iBit)
 
func newSieve(lim: Positive): Sieve =
## Create a sieve with given maximal index.
result.data = newSeq[byte]((lim + 16) shr 4)
 
func initPrimes(lim: Positive): seq[Natural] =
## Initialize the list of primes from 2 to "lim".
var composite = newSieve(lim)
composite[1] = true
for n in countup(3, sqrt(lim.toFloat).int, 2):
if not composite[n]:
for k in countup(n * n, lim, 2 * n):
composite[k] = true
result.add 2
for n in countup(3, lim, 2):
if not composite[n]:
result.add n
 
const Limit = int(ln(1e6) * 1e6 * 1.2)
let primes = initPrimes(Limit)
 
func primeFactors(n: Positive): seq[Positive] =
## Return the list of prime factors of "n".
## Duplicate primes are excluded.
var n = n
var last = 0
while (n and 1) == 0:
if last != 2:
result.add 2
last = 2
n = n shr 1
var d = 3
while d * d <= n:
while n mod d == 0:
if last != d:
result.add d
last = d
n = n div d
inc d, 2
if n > 1: result.add n
 
type Category = 1..12
var prevCats: Table[int, int]
 
proc cat(p: Natural): Category =
## Recursive procedure to compute the catagory of "p".
if p in prevCats: return prevCats[p]
let pf = primeFactors(p + 1)
if pf.allIt(it == 2 or it == 3):
return 1
for c in 2..11:
if pf.allIt(cat(it) < c):
prevCats[p] = c
return c
result = 12
 
 
var es: array[Category, seq[Positive]]
 
echo "First 200 primes:\n"
for p in primes[0..199]:
es[p.cat].add p
for c in 1..6:
if es[c].len > 0:
echo &"Category {c}:"
echo es[c].join(" ")
echo()
 
echo "First million primes:\n"
for p in primes[200..999_999]:
es[p.cat].add p
for c in 1..12:
let e = es[c]
if e.len > 0:
echo &"Category {c:>2}: first = {e[0]:>7} last = {e[^1]:>8} count = {e.len:>6}"
</syntaxhighlight>
 
{{out}}
<pre>First 200 primes:
 
Category 1:
2 3 5 7 11 17 23 31 47 53 71 107 127 191 383 431 647 863 971 1151
 
Category 2:
13 19 29 41 43 59 61 67 79 83 89 97 101 109 131 137 139 149 167 179 197 199 211 223 229 239 241 251 263 269 271 281 283 293 307 317 349 359 367 373 419 433 439 449 461 479 499 503 509 557 563 577 587 593 599 619 641 643 659 709 719 743 751 761 769 809 827 839 881 919 929 953 967 991 1019 1033 1049 1069 1087 1103 1187 1223
 
Category 3:
37 103 113 151 157 163 173 181 193 227 233 257 277 311 331 337 347 353 379 389 397 401 409 421 457 463 467 487 491 521 523 541 547 569 571 601 607 613 631 653 683 701 727 733 773 787 797 811 821 829 853 857 859 877 883 911 937 947 983 997 1009 1013 1031 1039 1051 1061 1063 1091 1097 1117 1123 1153 1163 1171 1181 1193 1217
 
Category 4:
73 313 443 617 661 673 677 691 739 757 823 887 907 941 977 1093 1109 1129 1201 1213
 
Category 5:
1021
 
First million primes:
 
Category 1: first = 2 last = 10616831 count = 46
Category 2: first = 13 last = 15482669 count = 10497
Category 3: first = 37 last = 15485863 count = 201987
Category 4: first = 73 last = 15485849 count = 413891
Category 5: first = 1021 last = 15485837 count = 263109
Category 6: first = 2917 last = 15485857 count = 87560
Category 7: first = 15013 last = 15484631 count = 19389
Category 8: first = 49681 last = 15485621 count = 3129
Category 9: first = 532801 last = 15472811 count = 363
Category 10: first = 1065601 last = 15472321 count = 28
Category 11: first = 8524807 last = 8524807 count = 1
</pre>
 
=={{header|Perl}}==
{{trans|Raku}}
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use strict;
use warnings;
use feature 'say';
Line 675 ⟶ 942:
printf "Category %2d: first: %9s last: %10s count: %s\n",
map { comma $_ } $_, (sort {$a <=> $b} @{$es{$_}})[0, -1], scalar @{$es{$_}}
for sort {$a <=> $b} keys %es;</langsyntaxhighlight>
{{out}}
<pre>First 200 primes, Erdös-Selfridge categorized:
Line 700 ⟶ 967:
{{libheader|Phix/online}}
You can run this online [http://phix.x10.mx/p2js/esprimes.htm here] (but expect a blank screen for about 20s)
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">escache</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
Line 752 ⟶ 1,019:
<span style="color: #000000;">categorise</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1e6</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 781 ⟶ 1,048:
=={{header|Raku}}==
 
<syntaxhighlight lang="raku" perl6line>use Prime::Factor;
use Lingua::EN::Numbers;
use Math::Primesieve;
Line 807 ⟶ 1,074:
say "\nSummary of first { cardinal $upto } primes; Erdös-Selfridge categorized:";
printf "Category %2d: first: %9s last: %10s count: %s\n", ++$, |(.[0], .[*-1], .elems).map: &comma
for $sieve.n-primes($upto).categorize( &Erdös-Selfridge ).sort(+*.key)».value;</langsyntaxhighlight>
{{out}}
<pre>First two hundred primes; Erdös-Selfridge categorized:
Line 828 ⟶ 1,095:
Category 10: first: 1,065,601 last: 15,472,321 count: 28
Category 11: first: 8,524,807 last: 8,524,807 count: 1</pre>
 
=={{header|RPL}}==
{{works with|RPL|HP49-C}}
« 5 { { 2 3 } } 0 → catg f
« 1 ROT '''START'''
DUP 1 + FACTORS 0.
1 PICK3 SIZE '''FOR''' j
OVER j GET
'''IF''' DUP 3 ≤ '''THEN''' NOT
'''ELSE'''
'f' STO
catg 1. « f POS » DOLIST 0. > 1. POS
'''END'''
MAX
2 '''STEP'''
NIP 1 +
'''IF''' DUP catg SIZE ≤
'''THEN''' catg SWAP DUP2 GET 4 PICK + PUT 'catg' STO
'''ELSE''' DROP 'catg' OVER 1. →LIST 1. →LIST STO+ '''END'''
NEXTPRIME
'''NEXT'''
DROP catg
» » '<span style="color:blue">→ESCLASS</span>' STO
 
200 <span style="color:blue">→ESCLASS</span>'
{{out}}
<pre>
1: { { 2 3 5 7 11 17 23 31 47 53 71 107 127 191 383 431 647 863 971 1151 } { 13 19 29 41 43 59 61 67 79 83 89 97 101 109 131 137 139 149 167 179 197 199 211 223 229 239 241 251 263 269 271 281 283 293 307 317 349 359 367 373 419 433 439 449 461 479 499 503 509 557 563 577 587 593 599 619 641 643 659 709 719 743 751 761 769 809 827 839 881 919 929 953 967 991 1019 1033 1049 1069 1087 1103 1187 1223 1231 } { 37 103 113 151 157 163 173 181 193 227 233 257 277 311 331 337 347 353 379 389 397 401 409 421 457 463 467 487 491 521 523 541 547 569 571 601 607 613 631 653 683 701 727 733 773 787 797 811 821 829 853 857 859 877 883 911 937 947 983 997 1009 1013 1031 1039 1051 1061 1063 1091 1097 1117 1123 1153 1163 1171 1181 1193 1217 1229 } { 73 313 443 617 661 673 677 691 739 757 823 887 907 941 977 1093 1109 1129 1201 1213 } { 1021 } }
</pre>
 
=={{header|Rust}}==
<langsyntaxhighlight lang="rust">// [dependencies]
// primal = "0.3"
 
Line 927 ⟶ 1,223:
);
}
}</langsyntaxhighlight>
 
{{out}}
Line 974 ⟶ 1,270:
 
=={{header|Sidef}}==
<langsyntaxhighlight lang="ruby">func Erdös_Selfridge_class(n, s=1) is cached {
var f = factor_exp(n+s)
f.last.head > 3 || return 1
Line 988 ⟶ 1,284:
1e6.pn_primes.group_by(Erdös_Selfridge_class).sort_by{.to_i}.each_2d {|k,v|
printf("Category %2d: first: %9s last: %10s count: %s\n", k, v.first, v.last, v.len)
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,016 ⟶ 1,312:
{{libheader|Wren-fmt}}
Runs in about 23.5 seconds.
<langsyntaxhighlight ecmascriptlang="wren">import "./math" for Int
import "./fmt" for Fmt
 
Line 1,069 ⟶ 1,365:
Fmt.print("Category $-2d: First = $7d Last = $8d Count = $6d", c, e[0], e[-1], e.count)
}
}</langsyntaxhighlight>
 
{{out}}
Aerobar
1,150

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/320499...363330"