Erdös-Selfridge categorization of primes

From Rosetta Code
Task
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++[edit]

Library: Primesieve
#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#[edit]

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[edit]

Works with: Factor version 0.99 2022-04-03
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[edit]

Translation of: Wren
Library: Go-rcu
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[edit]

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
┌─┬───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
12 3 5 7 11 17 23 31 47 53 71 107 127 191 383 431 647 863 971 1151                                                                                                                                                                                                                                                                  
├─┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
213 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
├─┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
337 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
├─┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
473 313 443 617 661 673 677 691 739 757 823 887 907 941 977 1093 1109 1129 1201 1213                                                                                                                                                                                                                                                
├─┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
51021                                                                                                                                                                                                                                                                                                                               
└─┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘

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[edit]

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[edit]

Translation of: Raku
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[edit]

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

Perl[edit]

Translation of: Raku
Library: ntheory
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[edit]

Library: Phix/online

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[edit]

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

Rust[edit]

// [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[edit]

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[edit]

Library: Wren-math
Library: Wren-fmt

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