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 (n`rem`b) /= 0 then k else maxpow' (n`div`b) (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; (k`rem`p) == 1) $ divisors (n`div`(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\}
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: