## Simple group order candidates among the odd integers less than 10000

Write and execute a computer program which

1. gives for each odd integer $n < 10000$ that is not a power of a prime and with the property that for each prime divisor $p$ of $n$ the corresponding $n_p$ is not forced to be 1 for all groups of order $n$ by the congruence condition of Sylow's Theorem, and
2. gives for each $n$ in part (1) the factorization of $n$ into prime powers and gives the list of all permissible values of $n_p$ for all primes $p$ dividing $n$. (I.e. those values not ruled out by Sylow’s Theorem.)

As usual, I’ll be writing in Haskell.

First, we will need a function that generates a list of the prime numbers. Since this is not strictly necessary for solving the problem, and since others have written far better prime sieves than I can hope to, I feel no shame in taking the following code from the Haskell wiki.

{- This prime sieve is cribbed shamelessly from the internet. -}
primes, nonprimes :: [Integer]
primes    = [2, 3, 5] ++ (diff [7, 9 ..] nonprimes)
nonprimes = foldr1 f . map g . tail $primes where f (x:xt) ys = x : (merge xt ys) g p = [ n * p | n &lt;- [p, p + 2 ..]] merge :: (Ord a) =&gt; [a] -&gt; [a] -&gt; [a] merge xs@(x:xt) ys@(y:yt) = case compare x y of LT -&gt; x : (merge xt ys) EQ -&gt; x : (merge xt yt) GT -&gt; y : (merge xs yt) diff :: (Ord a) =&gt; [a] -&gt; [a] -&gt; [a] diff xs@(x:xt) ys@(y:yt) = case compare x y of LT -&gt; x : (diff xt ys) EQ -&gt; diff xt yt GT -&gt; diff xs yt  Next we need a function that factors an integer into primes; this one will return a list of pairs $[(p_1,k_1),(p_2,k_2),\ldots,(p_n,k_n)]$ corresponding to the factorization $p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}$. {- factor n returns a list of pairs (p,k) such that k is the largest power of p dividing n; results are sorted on p -} factor :: Integer -&gt; [(Integer,Integer)] factor n = reverse$ filter (\(p,i) -&gt; i /= 0) $factor' n [] primes where factor' m qs (p:ps) = if (abs m) == 1 then qs else factor' (m div (p^i)) ((p,i):qs) ps where i = maxpow m p {- A utility which gives the largest power of b dividing a. -} maxpow :: Integer -&gt; Integer -&gt; Integer maxpow a b = maxpow' a 0 where maxpow' n k = if (nremb) /= 0 then k else maxpow' (ndivb) (k+1)  Now for some miscellaneous utilities for use later. import Data.List {- Returns a sorted list of the divisors of n. -} divisors :: Integer -&gt; [Integer] divisors n = sort$ foo (factor n) [1]
where foo [] ds = ds
foo ((p,i):ps) ds = foo ps [a*b | a &lt;- map (p^) [0..i], b &lt;- ds]

{- Determine whether or not a number is a prime power. -}
isPrimePower :: Integer -&gt; Bool
isPrimePower n = (length $factor n) == 1  These are the pieces we need to finish this program. First, to help keep our type signatures readable, I will introduce a new type synonym. We’d like to write a function sylow that takes an integer and returns all of the information the problem requests: namely, its factorization and some representation of the possible $n_p$ values for each $p$. We’ll call this information SylowData, and wrap it up in a type synonym. Because not just any triple of type SylowData represents a valid set of constraints, we will only allow a single function to return this type. {- Given an integer n (assumed to be positive), SylowData is a triple representing the following data: 1) n, 2) the factorization of n into a product of prime powers, and 3) for each prime p dividing n, the possible values of n_p in a group G of order n as allowed by Sylow's Theorem. We will assume that only one function ever returns SylowData. -} newtype SylowData = SylowData (Integer, [(Integer,Integer)], [(Integer,[Integer])]) deriving Show  The deriving Show line tells your Haskell interpreter how to display data of this type. Now the function sylow is fairly straightforward (although it could definitely be rewritten to be more efficient, this is good enough for now.) {- This function populates SylowData for a given number n. -} sylow :: Integer -&gt; SylowData sylow n = SylowData (n, factor n, foo (factor n) []) where foo [] cs = reverse cs foo ((p,i):ps) cs = foo ps ((p, filter (\k -&gt; (kremp) == 1)$ divisors (ndiv(p^i))):cs)


Now we can write a utility that detects when a set of SylowData forces any group of order $n$ to have a normal subgroup.

forcedNormal :: SylowData -&gt; Bool
forcedNormal (SylowData (_, _, cs)) = any (\(p,ds) -&gt; ds == [1]) cs


Last but not least, the following line implements the program the problem asked for. This is definitely not the most efficient solution; for instance, each number gets factored at least twice. (I am too lazy at the moment to fix this or think about whether memoization makes this moot.)

{- This function implements problems 47 and 48 in section 4.5 of D&amp;F. -}
prob = (filter (not . forcedNormal)) . (map sylow) . (filter (not . isPrimePower))


To solve the problem at hand, we simply call prob [3,5..10000].

For good measure, we’ll also bang out a couple of functions that format the results for WordPress.

pretty :: SylowData -&gt; String
pretty (SylowData (n, ps, cs)) = &quot;if $latex n = &quot; ++ show n ++ &quot; = &quot; ++ foo ps ++ &quot;$, then &quot; ++ bar cs
where foo [(p,1)] = show p
foo [(p,k)] = show p ++ &quot;^{&quot; ++ show k ++ &quot;}&quot;
foo ((p,1):ps) = show p ++ &quot; \\cdot &quot; ++ foo ps
foo ((p,k):ps) = show p ++ &quot;^{&quot; ++ show k ++ &quot;} \\cdot &quot; ++ foo ps
bar cs = unwords $intersperse &quot;, &quot;$ map baz cs
baz (p,cs) = &quot;$latex n_{&quot; ++ show p ++ &quot;} \\in \\{&quot; ++ unwords (intersperse &quot;,&quot; (map show cs)) ++ &quot;\\}$&quot;

pretty2 :: [SylowData] -&gt; String
pretty2 ds = &quot;&lt;ol&gt;&quot; ++ (unwords \$ map foo ds) ++ &quot;&lt;/ol&gt;&quot;
where foo d = &quot;&lt;li&gt;&quot; ++ pretty d ++ &quot;&lt;/li&gt;&quot;


Running the program, we see that there are 60 such numbers.

Here they are.

1. if $n = 105 = 3 \cdot 5 \cdot 7$, then $n_{3} \in \{1 , 7\}$ , $n_{5} \in \{1 , 21\}$ , $n_{7} \in \{1 , 15\}$
2. if $n = 315 = 3^{2} \cdot 5 \cdot 7$, then $n_{3} \in \{1 , 7\}$ , $n_{5} \in \{1 , 21\}$ , $n_{7} \in \{1 , 15\}$
3. if $n = 351 = 3^{3} \cdot 13$, then $n_{3} \in \{1 , 13\}$ , $n_{13} \in \{1 , 27\}$
4. if $n = 495 = 3^{2} \cdot 5 \cdot 11$, then $n_{3} \in \{1 , 55\}$ , $n_{5} \in \{1 , 11\}$ , $n_{11} \in \{1 , 45\}$
5. if $n = 525 = 3 \cdot 5^{2} \cdot 7$, then $n_{3} \in \{1 , 7 , 25 , 175\}$ , $n_{5} \in \{1 , 21\}$ , $n_{7} \in \{1 , 15\}$
6. if $n = 735 = 3 \cdot 5 \cdot 7^{2}$, then $n_{3} \in \{1 , 7 , 49\}$ , $n_{5} \in \{1 , 21\}$ , $n_{7} \in \{1 , 15\}$
7. if $n = 945 = 3^{3} \cdot 5 \cdot 7$, then $n_{3} \in \{1 , 7\}$ , $n_{5} \in \{1 , 21\}$ , $n_{7} \in \{1 , 15\}$
8. if $n = 1053 = 3^{4} \cdot 13$, then $n_{3} \in \{1 , 13\}$ , $n_{13} \in \{1 , 27\}$
9. if $n = 1365 = 3 \cdot 5 \cdot 7 \cdot 13$, then $n_{3} \in \{1 , 7 , 13 , 91\}$ , $n_{5} \in \{1 , 21 , 91\}$ , $n_{7} \in \{1 , 15\}$ , $n_{13} \in \{1 , 105\}$
10. if $n = 1485 = 3^{3} \cdot 5 \cdot 11$, then $n_{3} \in \{1 , 55\}$ , $n_{5} \in \{1 , 11\}$ , $n_{11} \in \{1 , 45\}$
11. if $n = 1575 = 3^{2} \cdot 5^{2} \cdot 7$, then $n_{3} \in \{1 , 7 , 25 , 175\}$ , $n_{5} \in \{1 , 21\}$ , $n_{7} \in \{1 , 15 , 225\}$
12. if $n = 1755 = 3^{3} \cdot 5 \cdot 13$, then $n_{3} \in \{1 , 13\}$ , $n_{5} \in \{1 , 351\}$ , $n_{13} \in \{1 , 27\}$
13. if $n = 1785 = 3 \cdot 5 \cdot 7 \cdot 17$, then $n_{3} \in \{1 , 7 , 85 , 595\}$ , $n_{5} \in \{1 , 21 , 51\}$ , $n_{7} \in \{1 , 15 , 85\}$ , $n_{17} \in \{1 , 35\}$
14. if $n = 2025 = 3^{4} \cdot 5^{2}$, then $n_{3} \in \{1 , 25\}$ , $n_{5} \in \{1 , 81\}$
15. if $n = 2205 = 3^{2} \cdot 5 \cdot 7^{2}$, then $n_{3} \in \{1 , 7 , 49\}$ , $n_{5} \in \{1 , 21 , 441\}$ , $n_{7} \in \{1 , 15\}$
16. if $n = 2457 = 3^{3} \cdot 7 \cdot 13$, then $n_{3} \in \{1 , 7 , 13 , 91\}$ , $n_{7} \in \{1 , 351\}$ , $n_{13} \in \{1 , 27\}$
17. if $n = 2475 = 3^{2} \cdot 5^{2} \cdot 11$, then $n_{3} \in \{1 , 25 , 55\}$ , $n_{5} \in \{1 , 11\}$ , $n_{11} \in \{1 , 45\}$
18. if $n = 2625 = 3 \cdot 5^{3} \cdot 7$, then $n_{3} \in \{1 , 7 , 25 , 175\}$ , $n_{5} \in \{1 , 21\}$ , $n_{7} \in \{1 , 15\}$
19. if $n = 2775 = 3 \cdot 5^{2} \cdot 37$, then $n_{3} \in \{1 , 25 , 37 , 925\}$ , $n_{5} \in \{1 , 111\}$ , $n_{37} \in \{1 , 75\}$
20. if $n = 2835 = 3^{4} \cdot 5 \cdot 7$, then $n_{3} \in \{1 , 7\}$ , $n_{5} \in \{1 , 21 , 81\}$ , $n_{7} \in \{1 , 15\}$
21. if $n = 2907 = 3^{2} \cdot 17 \cdot 19$, then $n_{3} \in \{1 , 19\}$ , $n_{17} \in \{1 , 171\}$ , $n_{19} \in \{1 , 153\}$
22. if $n = 3159 = 3^{5} \cdot 13$, then $n_{3} \in \{1 , 13\}$ , $n_{13} \in \{1 , 27\}$
23. if $n = 3393 = 3^{2} \cdot 13 \cdot 29$, then $n_{3} \in \{1 , 13\}$ , $n_{13} \in \{1 , 261\}$ , $n_{29} \in \{1 , 117\}$
24. if $n = 3465 = 3^{2} \cdot 5 \cdot 7 \cdot 11$, then $n_{3} \in \{1 , 7 , 55 , 385\}$ , $n_{5} \in \{1 , 11 , 21 , 231\}$ , $n_{7} \in \{1 , 15 , 99\}$ , $n_{11} \in \{1 , 45\}$
25. if $n = 3675 = 3 \cdot 5^{2} \cdot 7^{2}$, then $n_{3} \in \{1 , 7 , 25 , 49 , 175 , 1225\}$ , $n_{5} \in \{1 , 21\}$ , $n_{7} \in \{1 , 15\}$
26. if $n = 3875 = 5^{3} \cdot 31$, then $n_{5} \in \{1 , 31\}$ , $n_{31} \in \{1 , 125\}$
27. if $n = 4095 = 3^{2} \cdot 5 \cdot 7 \cdot 13$, then $n_{3} \in \{1 , 7 , 13 , 91\}$ , $n_{5} \in \{1 , 21 , 91\}$ , $n_{7} \in \{1 , 15\}$ , $n_{13} \in \{1 , 105\}$
28. if $n = 4125 = 3 \cdot 5^{3} \cdot 11$, then $n_{3} \in \{1 , 25 , 55 , 1375\}$ , $n_{5} \in \{1 , 11\}$ , $n_{11} \in \{1 , 375\}$
29. if $n = 4389 = 3 \cdot 7 \cdot 11 \cdot 19$, then $n_{3} \in \{1 , 7 , 19 , 133\}$ , $n_{7} \in \{1 , 57\}$ , $n_{11} \in \{1 , 133\}$ , $n_{19} \in \{1 , 77\}$
30. if $n = 4455 = 3^{4} \cdot 5 \cdot 11$, then $n_{3} \in \{1 , 55\}$ , $n_{5} \in \{1 , 11 , 81 , 891\}$ , $n_{11} \in \{1 , 45\}$
31. if $n = 4563 = 3^{3} \cdot 13^{2}$, then $n_{3} \in \{1 , 13 , 169\}$ , $n_{13} \in \{1 , 27\}$
32. if $n = 4725 = 3^{3} \cdot 5^{2} \cdot 7$, then $n_{3} \in \{1 , 7 , 25 , 175\}$ , $n_{5} \in \{1 , 21\}$ , $n_{7} \in \{1 , 15 , 225\}$
33. if $n = 4851 = 3^{2} \cdot 7^{2} \cdot 11$, then $n_{3} \in \{1 , 7 , 49\}$ , $n_{7} \in \{1 , 99\}$ , $n_{11} \in \{1 , 441\}$
34. if $n = 5103 = 3^{6} \cdot 7$, then $n_{3} \in \{1 , 7\}$ , $n_{7} \in \{1 , 729\}$
35. if $n = 5145 = 3 \cdot 5 \cdot 7^{3}$, then $n_{3} \in \{1 , 7 , 49 , 343\}$ , $n_{5} \in \{1 , 21\}$ , $n_{7} \in \{1 , 15\}$
36. if $n = 5265 = 3^{4} \cdot 5 \cdot 13$, then $n_{3} \in \{1 , 13\}$ , $n_{5} \in \{1 , 81 , 351\}$ , $n_{13} \in \{1 , 27\}$
37. if $n = 5313 = 3 \cdot 7 \cdot 11 \cdot 23$, then $n_{3} \in \{1 , 7 , 253 , 1771\}$ , $n_{7} \in \{1 , 253\}$ , $n_{11} \in \{1 , 23\}$ , $n_{23} \in \{1 , 231\}$
38. if $n = 5355 = 3^{2} \cdot 5 \cdot 7 \cdot 17$, then $n_{3} \in \{1 , 7 , 85 , 595\}$ , $n_{5} \in \{1 , 21 , 51 , 1071\}$ , $n_{7} \in \{1 , 15 , 85\}$ , $n_{17} \in \{1 , 35\}$
39. if $n = 5445 = 3^{2} \cdot 5 \cdot 11^{2}$, then $n_{3} \in \{1 , 55 , 121\}$ , $n_{5} \in \{1 , 11 , 121\}$ , $n_{11} \in \{1 , 45\}$
40. if $n = 6075 = 3^{5} \cdot 5^{2}$, then $n_{3} \in \{1 , 25\}$ , $n_{5} \in \{1 , 81\}$
41. if $n = 6375 = 3 \cdot 5^{3} \cdot 17$, then $n_{3} \in \{1 , 25 , 85 , 2125\}$ , $n_{5} \in \{1 , 51\}$ , $n_{17} \in \{1 , 375\}$
42. if $n = 6435 = 3^{2} \cdot 5 \cdot 11 \cdot 13$, then $n_{3} \in \{1 , 13 , 55 , 715\}$ , $n_{5} \in \{1 , 11\}$ , $n_{11} \in \{1 , 45\}$ , $n_{13} \in \{1 , 495\}$
43. if $n = 6545 = 5 \cdot 7 \cdot 11 \cdot 17$, then $n_{5} \in \{1 , 11\}$ , $n_{7} \in \{1 , 85\}$ , $n_{11} \in \{1 , 595\}$ , $n_{17} \in \{1 , 35\}$
44. if $n = 6615 = 3^{3} \cdot 5 \cdot 7^{2}$, then $n_{3} \in \{1 , 7 , 49\}$ , $n_{5} \in \{1 , 21 , 441\}$ , $n_{7} \in \{1 , 15\}$
45. if $n = 6669 = 3^{3} \cdot 13 \cdot 19$, then $n_{3} \in \{1 , 13 , 19 , 247\}$ , $n_{13} \in \{1 , 27\}$ , $n_{19} \in \{1 , 39\}$
46. if $n = 6825 = 3 \cdot 5^{2} \cdot 7 \cdot 13$, then $n_{3} \in \{1 , 7 , 13 , 25 , 91 , 175 , 325 , 2275\}$ , $n_{5} \in \{1 , 21 , 91\}$ , $n_{7} \in \{1 , 15\}$ , $n_{13} \in \{1 , 105\}$
47. if $n = 7371 = 3^{4} \cdot 7 \cdot 13$, then $n_{3} \in \{1 , 7 , 13 , 91\}$ , $n_{7} \in \{1 , 351\}$ , $n_{13} \in \{1 , 27\}$
48. if $n = 7425 = 3^{3} \cdot 5^{2} \cdot 11$, then $n_{3} \in \{1 , 25 , 55\}$ , $n_{5} \in \{1 , 11\}$ , $n_{11} \in \{1 , 45\}$
49. if $n = 7875 = 3^{2} \cdot 5^{3} \cdot 7$, then $n_{3} \in \{1 , 7 , 25 , 175\}$ , $n_{5} \in \{1 , 21\}$ , $n_{7} \in \{1 , 15 , 225\}$
50. if $n = 8325 = 3^{2} \cdot 5^{2} \cdot 37$, then $n_{3} \in \{1 , 25 , 37 , 925\}$ , $n_{5} \in \{1 , 111\}$ , $n_{37} \in \{1 , 75\}$
51. if $n = 8505 = 3^{5} \cdot 5 \cdot 7$, then $n_{3} \in \{1 , 7\}$ , $n_{5} \in \{1 , 21 , 81 , 1701\}$ , $n_{7} \in \{1 , 15\}$
52. if $n = 8721 = 3^{3} \cdot 17 \cdot 19$, then $n_{3} \in \{1 , 19\}$ , $n_{17} \in \{1 , 171\}$ , $n_{19} \in \{1 , 153\}$
53. if $n = 8775 = 3^{3} \cdot 5^{2} \cdot 13$, then $n_{3} \in \{1 , 13 , 25 , 325\}$ , $n_{5} \in \{1 , 351\}$ , $n_{13} \in \{1 , 27\}$
54. if $n = 8883 = 3^{3} \cdot 7 \cdot 47$, then $n_{3} \in \{1 , 7\}$ , $n_{7} \in \{1 , 141\}$ , $n_{47} \in \{1 , 189\}$
55. if $n = 8925 = 3 \cdot 5^{2} \cdot 7 \cdot 17$, then $n_{3} \in \{1 , 7 , 25 , 85 , 175 , 595\}$ , $n_{5} \in \{1 , 21 , 51\}$ , $n_{7} \in \{1 , 15 , 85 , 1275\}$ , $n_{17} \in \{1 , 35\}$
56. if $n = 9045 = 3^{3} \cdot 5 \cdot 67$, then $n_{3} \in \{1 , 67\}$ , $n_{5} \in \{1 , 201\}$ , $n_{67} \in \{1 , 135\}$
57. if $n = 9405 = 3^{2} \cdot 5 \cdot 11 \cdot 19$, then $n_{3} \in \{1 , 19 , 55 , 1045\}$ , $n_{5} \in \{1 , 11 , 171 , 1881\}$ , $n_{11} \in \{1 , 45\}$ , $n_{19} \in \{1 , 495\}$
58. if $n = 9477 = 3^{6} \cdot 13$, then $n_{3} \in \{1 , 13\}$ , $n_{13} \in \{1 , 27 , 729\}$
59. if $n = 9555 = 3 \cdot 5 \cdot 7^{2} \cdot 13$, then $n_{3} \in \{1 , 7 , 13 , 49 , 91 , 637\}$ , $n_{5} \in \{1 , 21 , 91 , 1911\}$ , $n_{7} \in \{1 , 15\}$ , $n_{13} \in \{1 , 105\}$
60. if $n = 9765 = 3^{2} \cdot 5 \cdot 7 \cdot 31$, then $n_{3} \in \{1 , 7 , 31 , 217\}$ , $n_{5} \in \{1 , 21 , 31 , 651\}$ , $n_{7} \in \{1 , 15 , 155\}$ , $n_{31} \in \{1 , 63\}$