Erdös-Selfridge categorization of primes
You are encouraged to solve this task according to the task description, using any language you may know.
A prime p is in category 1 if the prime factors of p+1 are 2 and or 3. p is in category 2 if all the prime factors of p+1 are in category 1. p is in category g if all the prime factors of p+1 are in categories 1 to g-1.
The task is first to display the first 200 primes allocated to their category, then assign the first million primes to their category, displaying the smallest prime, the largest prime, and the count of primes allocated to each category.
C++
#include <algorithm>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <map>
#include <vector>
#include <primesieve.hpp>
class erdos_selfridge {
public:
explicit erdos_selfridge(int limit);
uint64_t get_prime(int index) const { return primes_[index].first; }
int get_category(int index);
private:
std::vector<std::pair<uint64_t, int>> primes_;
size_t get_index(uint64_t prime) const;
};
erdos_selfridge::erdos_selfridge(int limit) {
primesieve::iterator iter;
for (int i = 0; i < limit; ++i)
primes_.emplace_back(iter.next_prime(), 0);
}
int erdos_selfridge::get_category(int index) {
auto& pair = primes_[index];
if (pair.second != 0)
return pair.second;
int max_category = 0;
uint64_t n = pair.first + 1;
for (int i = 0; n > 1; ++i) {
uint64_t p = primes_[i].first;
if (p * p > n)
break;
int count = 0;
for (; n % p == 0; ++count)
n /= p;
if (count != 0) {
int category = (p <= 3) ? 1 : 1 + get_category(i);
max_category = std::max(max_category, category);
}
}
if (n > 1) {
int category = (n <= 3) ? 1 : 1 + get_category(get_index(n));
max_category = std::max(max_category, category);
}
pair.second = max_category;
return max_category;
}
size_t erdos_selfridge::get_index(uint64_t prime) const {
auto it = std::lower_bound(primes_.begin(), primes_.end(), prime,
[](const std::pair<uint64_t, int>& p,
uint64_t n) { return p.first < n; });
assert(it != primes_.end());
assert(it->first == prime);
return std::distance(primes_.begin(), it);
}
auto get_primes_by_category(erdos_selfridge& es, int limit) {
std::map<int, std::vector<uint64_t>> primes_by_category;
for (int i = 0; i < limit; ++i) {
uint64_t prime = es.get_prime(i);
int category = es.get_category(i);
primes_by_category[category].push_back(prime);
}
return primes_by_category;
}
int main() {
const int limit1 = 200, limit2 = 1000000;
erdos_selfridge es(limit2);
std::cout << "First 200 primes:\n";
for (const auto& p : get_primes_by_category(es, limit1)) {
std::cout << "Category " << p.first << ":\n";
for (size_t i = 0, n = p.second.size(); i != n; ++i) {
std::cout << std::setw(4) << p.second[i]
<< ((i + 1) % 15 == 0 ? '\n' : ' ');
}
std::cout << "\n\n";
}
std::cout << "First 1,000,000 primes:\n";
for (const auto& p : get_primes_by_category(es, limit2)) {
const auto& v = p.second;
std::cout << "Category " << std::setw(2) << p.first << ": "
<< "first = " << std::setw(7) << v.front()
<< " last = " << std::setw(8) << v.back()
<< " count = " << v.size() << '\n';
}
}
- Output:
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 1,000,000 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
F#
This task uses Extensible Prime Generator (F#)
// 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
let fN g=Seq.unfold(fun(n,g)->let n,g=n|>List.map(fun n->fG n g)|>List.partition(fun(_,n)->n<>1) in let g=g|>List.map fst in if g=[] then None else Some(g,(n,g)))(primes32()|>Seq.take g|>Seq.map(fun n->(n,n+1))|>List.ofSeq,[2;3])
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) (
- Output:
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] 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
Factor
USING: assocs combinators formatting grouping grouping.extras io
kernel math math.primes math.primes.factors math.statistics
prettyprint sequences sequences.deep ;
PREDICATE: >3 < integer 3 > ;
GENERIC: depth ( seq -- n )
M: sequence depth
0 swap [ flatten1 [ 1 + ] dip ] to-fixed-point drop ;
M: integer depth drop 1 ;
MEMO: pfactors ( n -- seq ) 1 + factors ;
: category ( m -- n )
[ dup >3? [ pfactors ] when ] deep-map depth ;
: categories ( n -- assoc ) nprimes [ category ] collect-by ;
: table. ( seq n -- )
[ "" pad-groups ] keep group simple-table. ;
: categories... ( assoc -- )
[ [ "Category %d:\n" printf ] dip 15 table. ] assoc-each ;
: row. ( category first last count -- )
"Category %d: first->%d last->%d count->%d\n" printf ;
: categories. ( assoc -- )
[ [ minmax ] keep length row. ] assoc-each ;
200 categories categories... nl
1,000,000 categories categories.
- Output:
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 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
Go
package main
import (
"fmt"
"math"
"rcu"
)
var limit = int(math.Log(1e6) * 1e6 * 1.2) // should be more than enough
var primes = rcu.Primes(limit)
var prevCats = make(map[int]int)
func cat(p int) int {
if v, ok := prevCats[p]; ok {
return v
}
pf := rcu.PrimeFactors(p + 1)
all := true
for _, f := range pf {
if f != 2 && f != 3 {
all = false
break
}
}
if all {
return 1
}
if p > 2 {
len := len(pf)
for i := len - 1; i >= 1; i-- {
if pf[i-1] == pf[i] {
pf = append(pf[:i], pf[i+1:]...)
}
}
}
for c := 2; c <= 11; c++ {
all := true
for _, f := range pf {
if cat(f) >= c {
all = false
break
}
}
if all {
prevCats[p] = c
return c
}
}
return 12
}
func main() {
es := make([][]int, 12)
fmt.Println("First 200 primes:\n")
for _, p := range primes[0:200] {
c := cat(p)
es[c-1] = append(es[c-1], p)
}
for c := 1; c <= 6; c++ {
if len(es[c-1]) > 0 {
fmt.Println("Category", c, "\b:")
fmt.Println(es[c-1])
fmt.Println()
}
}
fmt.Println("First million primes:\n")
for _, p := range primes[200:1e6] {
c := cat(p)
es[c-1] = append(es[c-1], p)
}
for c := 1; c <= 12; c++ {
e := es[c-1]
if len(e) > 0 {
format := "Category %-2d: First = %7d Last = %8d Count = %6d\n"
fmt.Printf(format, c, e[0], e[len(e)-1], len(e))
}
}
}
- Output:
Same as Wren example.
J
Implementation:
pcat=: {{ assert. 1 p: y
1+>./0,pcat(q:1+y)-.2 3
}}M."0
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:
(,.~<@#\) (</.~ 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 │
└─┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
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:
(,.~#\) (({.,{:,#)/.~ 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
Java
Uses the PrimeGenerator class from Extensible prime generator#Java.
import java.util.*;
public class ErdosSelfridge {
private int[] primes;
private int[] category;
public static void main(String[] args) {
ErdosSelfridge es = new ErdosSelfridge(1000000);
System.out.println("First 200 primes:");
for (var e : es.getPrimesByCategory(200).entrySet()) {
int category = e.getKey();
List<Integer> primes = e.getValue();
System.out.printf("Category %d:\n", category);
for (int i = 0, n = primes.size(); i != n; ++i)
System.out.printf("%4d%c", primes.get(i), (i + 1) % 15 == 0 ? '\n' : ' ');
System.out.printf("\n\n");
}
System.out.println("First 1,000,000 primes:");
for (var e : es.getPrimesByCategory(1000000).entrySet()) {
int category = e.getKey();
List<Integer> primes = e.getValue();
System.out.printf("Category %2d: first = %7d last = %8d count = %d\n", category,
primes.get(0), primes.get(primes.size() - 1), primes.size());
}
}
private ErdosSelfridge(int limit) {
PrimeGenerator primeGen = new PrimeGenerator(100000, 200000);
List<Integer> primeList = new ArrayList<>();
for (int i = 0; i < limit; ++i)
primeList.add(primeGen.nextPrime());
primes = new int[primeList.size()];
for (int i = 0; i < primes.length; ++i)
primes[i] = primeList.get(i);
category = new int[primes.length];
}
private Map<Integer, List<Integer>> getPrimesByCategory(int limit) {
Map<Integer, List<Integer>> result = new TreeMap<>();
for (int i = 0; i < limit; ++i) {
var p = result.computeIfAbsent(getCategory(i), k -> new ArrayList<Integer>());
p.add(primes[i]);
}
return result;
}
private int getCategory(int index) {
if (category[index] != 0)
return category[index];
int maxCategory = 0;
int n = primes[index] + 1;
for (int i = 0; n > 1; ++i) {
int p = primes[i];
if (p * p > n)
break;
int count = 0;
for (; n % p == 0; ++count)
n /= p;
if (count != 0) {
int category = (p <= 3) ? 1 : 1 + getCategory(i);
maxCategory = Math.max(maxCategory, category);
}
}
if (n > 1) {
int category = (n <= 3) ? 1 : 1 + getCategory(getIndex(n));
maxCategory = Math.max(maxCategory, category);
}
category[index] = maxCategory;
return maxCategory;
}
private int getIndex(int prime) {
return Arrays.binarySearch(primes, prime);
}
}
- Output:
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 1,000,000 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
Julia
using Primes
primefactors(n) = collect(keys(factor(n)))
function ErdösSelfridge(n)
highfactors = filter(>(3), primefactors(n + 1))
category = 1
while !isempty(highfactors)
highfactors = unique(reduce(vcat, [filter(>(3), primefactors(a + 1)) for a in highfactors]))
category += 1
end
return category
end
function testES(numshowprimes, numtotalprimes)
println("First $numshowprimes primes by Erdös-Selfridge categories:")
dict = Dict{Int, Vector{Int}}(i => [] for i in 1:5)
for p in primes(prime(numshowprimes))
push!(dict[ErdösSelfridge(p)], p)
end
for cat in 1:5
println("$cat => ", dict[cat])
end
dict2 = Dict{Int, Tuple{Int, Int, Int}}(i => (0, 0, 0) for i in 1:11)
println("\nTotals for first $numtotalprimes primes by Erdös-Selfridge categories:")
for p in primes(prime(numtotalprimes))
cat = ErdösSelfridge(p)
fir, tot, las = dict2[cat]
fir == 0 && (fir = p)
dict2[cat] = (fir, tot + 1, p)
end
for cat in 1:11
first, total, last = dict2[cat]
println("Category", lpad(cat, 3), " => first:", lpad(first, 8), ", total:", lpad(total, 7), ", last:", last)
end
end
testES(200, 1_000_000)
- Output:
First 200 primes by Erdös-Selfridge categories: 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] Totals for first 1000000 primes by Erdös-Selfridge categories: Category 1 => first: 2, total: 46, last:10616831 Category 2 => first: 13, total: 10497, last:15482669 Category 3 => first: 37, total: 201987, last:15485863 Category 4 => first: 73, total: 413891, last:15485849 Category 5 => first: 1021, total: 263109, last:15485837 Category 6 => first: 2917, total: 87560, last:15485857 Category 7 => first: 15013, total: 19389, last:15484631 Category 8 => first: 49681, total: 3129, last:15485621 Category 9 => first: 532801, total: 363, last:15472811 Category 10 => first: 1065601, total: 28, last:15472321 Category 11 => first: 8524807, total: 1, last:8524807
Mathematica /Wolfram Language
Imperative implementation
ClearAll[SpecialPrimeFactors]
SpecialPrimeFactors[p_Integer] := FactorInteger[p + 1][[All, 1]]
ps = Prime[Range[200]];
cs = {{2, 3}};
Do[
If[Length[ps] > 0,
newc =
Select[ps,
Complement[SpecialPrimeFactors[#], Catenate[cs]] === {} &];
AppendTo[cs, newc];
ps = Complement[ps, newc];
,
Break[]
]
,
{n, 1, \[Infinity]}
];
Do[
Print["Category: ", i - 1];
Print@Multicolumn[cs[[i]], {Automatic, 10}]
,
{i, Length[cs]}
]
ps = Prime[Range[1000000]];
ps = Parallelize[{#, SpecialPrimeFactors[#]} & /@ ps];
cs = {{2, 3}};
Do[
If[Length[ps] > 0,
newcs = Last[cs];
ps[[All, 2]] = ps[[All, 2]] /. Dispatch[Thread[newcs -> Nothing]];
newc = Select[ps, Last/*Length/*EqualTo[0]];
ps = Complement[ps, newc];
newc = newc[[All, 1]];
AppendTo[cs, newc];
,
Break[]
]
,
{n, 1, \[Infinity]}
];
TableForm[{First[#], Last[#], Length[#]} & /@ Rest[cs],
TableHeadings -> {Automatic, {"First", "Last", "Count"}},
TableAlignments -> Right]
- Output:
Category: 0 2 3 Category: 1 2 5 11 23 47 71 127 383 647 971 3 7 17 31 53 107 191 431 863 1151 Category: 2 13 83 167 251 349 479 599 761 967 1223 19 89 179 263 359 499 619 769 991 29 97 197 269 367 503 641 809 1019 41 101 199 271 373 509 643 827 1033 43 109 211 281 419 557 659 839 1049 59 131 223 283 433 563 709 881 1069 61 137 229 293 439 577 719 919 1087 67 139 239 307 449 587 743 929 1103 79 149 241 317 461 593 751 953 1187 Category: 3 37 193 347 457 547 683 821 937 1051 1163 103 227 353 463 569 701 829 947 1061 1171 113 233 379 467 571 727 853 983 1063 1181 151 257 389 487 601 733 857 997 1091 1193 157 277 397 491 607 773 859 1009 1097 1217 163 311 401 521 613 787 877 1013 1117 173 331 409 523 631 797 883 1031 1123 181 337 421 541 653 811 911 1039 1153 Category: 4 73 443 661 677 739 823 907 977 1109 1201 313 617 673 691 757 887 941 1093 1129 1213 Category: 5 1021 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
Functional implementation
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]]
- Output:
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
Nim
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.
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}"
- Output:
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
Perl
use strict;
use warnings;
use feature 'say';
use List::Util 'max';
use ntheory qw/factor/;
use Primesieve qw(generate_primes);
my @primes = (0, generate_primes (1, 10**8));
my %cat = (2 => 1, 3 => 1);
sub comma { reverse ((reverse shift) =~ s/(.{3})/$1,/gr) =~ s/^,//r }
sub ES {
my ($n) = @_;
my @factors = factor $n + 1;
my $category = max map { defined $cat{$_} and $cat{$_} } @factors;
unless (defined $cat{ $factors[-1] }) {
$category = max $category, (1 + max map { $cat{$_} } factor 1 + $factors[-1]);
$cat{ $factors[-1] } = $category;
}
$category
}
my %es;
my $upto = 200;
push @{$es{ES($_)}}, $_ for @primes[1..$upto];
say "First $upto primes, Erdös-Selfridge categorized:";
say "$_: " . join ' ', sort {$a <=> $b} @{$es{$_}} for sort keys %es;
%es = ();
$upto = 1_000_000;
say "\nSummary of first @{[comma $upto]} primes, Erdös-Selfridge categorized:";
push @{$es{ES($_)}}, $_ for @primes[1..$upto];
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;
- Output:
First 200 primes, Erdös-Selfridge categorized: 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 Summary of first 1,000,000 primes, Erdös-Selfridge categorized: Category 1: first: 2 last: 10,616,831 count: 46 Category 2: first: 13 last: 15,482,669 count: 10,497 Category 3: first: 37 last: 15,485,863 count: 201,987 Category 4: first: 73 last: 15,485,849 count: 413,891 Category 5: first: 1,021 last: 15,485,837 count: 263,109 Category 6: first: 2,917 last: 15,485,857 count: 87,560 Category 7: first: 15,013 last: 15,484,631 count: 19,389 Category 8: first: 49,681 last: 15,485,621 count: 3,129 Category 9: first: 532,801 last: 15,472,811 count: 363 Category 10: first: 1,065,601 last: 15,472,321 count: 28 Category 11: first: 8,524,807 last: 8,524,807 count: 1
Phix
You can run this online here (but expect a blank screen for about 20s)
with javascript_semantics sequence escache = {} function es_cat(integer p) if p>length(escache) and platform()!=JS then escache &= repeat(0,p-length(escache)) end if integer category = escache[p] if not category then sequence f = filter(prime_factors(p+1,false,-1),">",3) category = 1 if length(f) then category += max(apply(f,es_cat)) end if escache[p] = category end if return category end function procedure categorise(integer n) sequence p = get_primes(n) printf(1,"First %,d primes:\n",n) atom t1 = time() sequence es = {} for i=1 to n do if time()>t1 then progress("categorising %d/%d...",{i,n}) t1 = time()+1 end if integer category = es_cat(p[i]) while length(es)<category do es = append(es,{}) end while es[category] &= p[i] end for progress("") for c=1 to length(es) do sequence e = es[c] if n=200 then printf(1,"Category %d: %s\n",{c,join(shorten(e,"primes",5,"%d"),",")}) else printf(1,"Category %2d: %7d .. %-8d Count: %d\n",{c,e[1],e[$],length(e)}) end if end for printf(1,"\n") end procedure atom t0 = time() categorise(200) categorise(1e6) ?elapsed(time()-t0)
- Output:
First 200 primes: Category 1: 2,3,5,7,11,...,431,647,863,971,1151, (20 primes) Category 2: 13,19,29,41,43,...,1069,1087,1103,1187,1223, (82 primes) Category 3: 37,103,113,151,157,...,1163,1171,1181,1193,1217, (77 primes) Category 4: 73,313,443,617,661,...,1093,1109,1129,1201,1213, (20 primes) Category 5: 1021 First 1,000,000 primes: Category 1: 2 .. 10616831 Count: 46 Category 2: 13 .. 15482669 Count: 10497 Category 3: 37 .. 15485863 Count: 201987 Category 4: 73 .. 15485849 Count: 413891 Category 5: 1021 .. 15485837 Count: 263109 Category 6: 2917 .. 15485857 Count: 87560 Category 7: 15013 .. 15484631 Count: 19389 Category 8: 49681 .. 15485621 Count: 3129 Category 9: 532801 .. 15472811 Count: 363 Category 10: 1065601 .. 15472321 Count: 28 Category 11: 8524807 .. 8524807 Count: 1 "11.0s"
Takes about twice as long under pwa/p2js.
Raku
use Prime::Factor;
use Lingua::EN::Numbers;
use Math::Primesieve;
my $sieve = Math::Primesieve.new;
my %cat = 2 => 1, 3 => 1;
sub Erdös-Selfridge ($n) {
my @factors = prime-factors $n + 1;
my $category = max %cat{ @factors };
unless %cat{ @factors[*-1] } {
$category max= ( 1 + max %cat{ prime-factors 1 + @factors[*-1] } );
%cat{ @factors[*-1] } = $category;
}
$category
}
my $upto = 200;
say "First { cardinal $upto } primes; Erdös-Selfridge categorized:";
.say for sort $sieve.n-primes($upto).categorize: &Erdös-Selfridge;
$upto = 1_000_000;
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;
- Output:
First two hundred primes; Erdös-Selfridge categorized: 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] Summary of first one million primes; Erdös-Selfridge categorized: Category 1: first: 2 last: 10,616,831 count: 46 Category 2: first: 13 last: 15,482,669 count: 10,497 Category 3: first: 37 last: 15,485,863 count: 201,987 Category 4: first: 73 last: 15,485,849 count: 413,891 Category 5: first: 1,021 last: 15,485,837 count: 263,109 Category 6: first: 2,917 last: 15,485,857 count: 87,560 Category 7: first: 15,013 last: 15,484,631 count: 19,389 Category 8: first: 49,681 last: 15,485,621 count: 3,129 Category 9: first: 532,801 last: 15,472,811 count: 363 Category 10: first: 1,065,601 last: 15,472,321 count: 28 Category 11: first: 8,524,807 last: 8,524,807 count: 1
RPL
« 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
» » '→ESCLASS' STO
200 →ESCLASS'
- Output:
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 } }
Rust
// [dependencies]
// primal = "0.3"
use std::collections::BTreeMap;
struct ErdosSelfridge {
primes: Vec<usize>,
category: Vec<u32>,
}
impl ErdosSelfridge {
fn new(limit: usize) -> ErdosSelfridge {
let mut es = ErdosSelfridge {
primes: primal::Primes::all().take(limit).collect(),
category: Vec::new(),
};
es.category.resize(es.primes.len(), 0);
es
}
fn get_category(&mut self, index: usize) -> u32 {
if self.category[index] != 0 {
return self.category[index];
}
let mut max_category = 0;
let mut n = self.primes[index] + 1;
for i in 0.. {
let p = self.primes[i];
if p * p > n {
break;
}
let mut count = 0;
while n % p == 0 {
n /= p;
count += 1;
}
if count != 0 {
let category = if p <= 3 { 1 } else { 1 + self.get_category(i) };
max_category = std::cmp::max(max_category, category);
}
}
if n > 1 {
let i = self.get_index(n);
let category = if n <= 3 { 1 } else { 1 + self.get_category(i) };
max_category = std::cmp::max(max_category, category);
}
self.category[index] = max_category;
max_category
}
fn get_index(&self, prime: usize) -> usize {
self.primes.binary_search(&prime).unwrap()
}
fn get_primes_by_category(&mut self, limit: usize) -> BTreeMap<u32, Vec<usize>> {
let mut primes_by_category: BTreeMap<u32, Vec<usize>> = BTreeMap::new();
for i in 0..limit {
let category = self.get_category(i);
let prime = self.primes[i];
if let Some(primes) = primes_by_category.get_mut(&category) {
primes.push(prime);
} else {
let mut primes = Vec::new();
primes.push(prime);
primes_by_category.insert(category, primes);
}
}
primes_by_category
}
}
fn main() {
let mut es = ErdosSelfridge::new(1000000);
let primes_by_category = es.get_primes_by_category(200);
println!("First 200 primes:");
for (category, primes) in primes_by_category.iter() {
println!("Category {}:", category);
for i in 0..primes.len() {
print!(
"{:4}{}",
primes[i],
if (i + 1) % 15 == 0 { "\n" } else { " " }
);
}
print!("\n\n");
}
println!("First 1,000,000 primes:");
let primes_by_category = es.get_primes_by_category(1000000);
for (category, primes) in primes_by_category.iter() {
let first = primes[0];
let count = primes.len();
let last = primes[count - 1];
println!(
"Category {:2}: first = {:7} last = {:8} count = {}",
category, first, last, count
);
}
}
- Output:
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 1,000,000 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
Sidef
func Erdös_Selfridge_class(n, s=1) is cached {
var f = factor_exp(n+s)
f.last.head > 3 || return 1
f.map {|p| __FUNC__(p.head, s) }.max + 1
}
say "First two hundred primes; Erdös-Selfridge categorized:"
200.pn_primes.group_by(Erdös_Selfridge_class).sort_by{.to_i}.each_2d {|k,v|
say "#{k} => #{v}"
}
say "\nSummary of first 10^6 primes; Erdös-Selfridge categorized:";
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)
}
- Output:
First two hundred primes; Erdös-Selfridge categorized: 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] Summary of first 10^6 primes; Erdös-Selfridge categorized: 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
Wren
Runs in about 23.5 seconds.
import "./math" for Int
import "./fmt" for Fmt
var limit = (1e6.log * 1e6 * 1.2).floor // should be more than enough
var primes = Int.primeSieve(limit)
var prevCats = {}
var cat // recursive
cat = Fn.new { |p|
if (prevCats.containsKey(p)) return prevCats[p]
var pf = Int.primeFactors(p+1)
if (pf.all { |f| f == 2 || f == 3 }) return 1
if (p > 2) {
for (i in pf.count-1..1) {
if (pf[i-1] == pf[i]) pf.removeAt(i)
}
}
for (c in 2..11) {
if (pf.all { |f| cat.call(f) < c }) {
prevCats[p] = c
return c
}
}
return 12
}
var es = List.filled(12, null)
for (i in 0..11) es[i] = []
System.print("First 200 primes:\n ")
for (p in primes[0..199]) {
var c = cat.call(p)
es[c-1].add(p)
}
for (c in 1..6) {
if (es[c-1].count > 0) {
System.print("Category %(c):")
System.print(es[c-1])
System.print()
}
}
System.print("First million primes:\n")
for (p in primes[200...1e6]) {
var c = cat.call(p)
es[c-1].add(p)
}
for (c in 1..12) {
var e = es[c-1]
if (e.count > 0) {
Fmt.print("Category $-2d: First = $7d Last = $8d Count = $6d", c, e[0], e[-1], e.count)
}
}
- Output:
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