Erdös-Selfridge categorization of primes

Revision as of 09:33, 15 April 2022 by Petelomax (talk | contribs) (→‎{{header|Phix}}: fixed the performance issue under p2js)

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.

Erdös-Selfridge categorization of primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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.

F#

This task uses Extensible Prime Generator (F#) <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 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) ( </lang>

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

Works with: Factor version 0.99 2022-04-03

<lang 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.</lang>

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

Julia

Translation of: Raku

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

</lang>

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

Phix

Library: Phix/online

You can run this online here (but expect a blank screen for about 20s)

with javascript_semantics -- (severely cut-down)
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] -- (sadly not p2js compatible...[yet])
        sequence ec = es[category]
        es[category] = 0
        ec &= p[i] 
        es[category] = ec
    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

<lang perl6>use Prime::Factor; use Math::Primesieve; my $sieve = Math::Primesieve.new;

sub Erdös-Selfridge ($n) {

   my @factors = unique grep * > 3, prime-factors $n + 1;
   my $category = 1;
   while @factors.elems {
       @factors = unique grep * > 3, flat @factors.map: { prime-factors $_ + 1 };
       ++$category
   }
   $category

}

say "First 200 primes; Erdös-Selfridge categorized:"; .say for sort $sieve.n-primes(200).categorize: &Erdös-Selfridge;

say "\nFirst million primes; Erdös-Selfridge categorized:"; printf "Category %2d: first: %7d, last: %8d, total: %d\n", ++$, .[0], .[*-1], .elems for $sieve.n-primes(1_000_000).categorize( &Erdös-Selfridge ).sort(+*.key)».value;</lang>

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]

First million primes; Erdös-Selfridge categorized:
Category  1: first:       2, last: 10616831, total: 46
Category  2: first:      13, last: 15482669, total: 10497
Category  3: first:      37, last: 15485863, total: 201987
Category  4: first:      73, last: 15485849, total: 413891
Category  5: first:    1021, last: 15485837, total: 263109
Category  6: first:    2917, last: 15485857, total: 87560
Category  7: first:   15013, last: 15484631, total: 19389
Category  8: first:   49681, last: 15485621, total: 3129
Category  9: first:  532801, last: 15472811, total: 363
Category 10: first: 1065601, last: 15472321, total: 28
Category 11: first: 8524807, last:  8524807, total: 1

Wren

Library: Wren-math
Library: Wren-fmt

Runs in about 23.5 seconds. <lang ecmascript>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)
   }

}</lang>

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