Erdös-Selfridge categorization of primes

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.

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

Wren

Library: Wren-math

Library: Wren-fmt

Second part takes a while. <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 cat // recursive cat = Fn.new { |p|

   var pf = Int.primeFactors(p+1)
   if (pf.all { |f| f == 2 || f == 3 }) return 1
   for (c in 2..11) {
       if (pf.all { |f| cat.call(f) < 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