{-
Generates Gaussian primes, demonstrates multiplication of Gaussian integers.

Copyright 2026 Ken Takusagawa

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or (at
your option) any later version.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <https://www.gnu.org/licenses/>.
-}
{-# LANGUAGE ScopedTypeVariables, LambdaCase, PackageImports #-}
module Main where {
import System.Environment(getArgs);
import Control.Exception(assert);
import Debug.Trace(trace);
import Data.Function((&));
import Control.Category((>>>));
import Prelude hiding((.),(>>));
--import qualified Prelude;
import System.IO(hSetBuffering,stdout,BufferMode(LineBuffering));
--import System.IO(stderr,hPutStrLn);
import qualified Data.List as List;
--import qualified Control.Monad as Monad;
import Control.Monad(guard);
--import qualified Data.Maybe as Maybe;
import qualified Data.Map as Map; import Data.Map(Map);
import qualified Data.Set as Set; import Data.Set(Set);
--import Data.Tuple(swap);
--import Control.Monad.GenericReplicate(genericReplicateM); -- igenericReplicateM
import qualified Data.Bifunctor as Bifunctor;  -- (first, second)
--import Control.Monad(MonadPlus);


main :: IO();
main = getArgs >>= \case{
["smallgaussianprimes"] -> smallgaussianprimes;

-- test the wikipedia algorithm for gaussian primality
["testwikipedia",n] -> testwikipedia (Sidehalf $ read n);

-- entire multiplication table 6849 entries
["everything"] -> allcomplex digit9 & unsortedallmults digit9 & map (showmult smallstr) & printlines;

-- multiplication by pure real or pure imaginary is boring
["fullycomplex"] -> allcomplex digit9 & filter fullycomplex & unsortedallmults digit9 & latefilter & map (showmult smallstr) & printlines;
_ -> undefined;
};

olderexperiments :: [String] -> IO();
olderexperiments = \case{
-- multiplication table positive left hand side
["niceportion"] -> allcomplex digit9 & filter niceportion & unsortedallmults digit9 & map (showmult smallstr >>> sentenceperiod ) & unwords & putStrLn;
---- removing duplicates from niceportion by commutivity
["nice"] -> allcomplex digit9 & filter nice & allmults digit9 & map (showmult smallstr) & printlines;
-- removing some from everything
["cards"] -> allcomplex digit9 & filter someimaginary & allmults digit9 & map (showmult smallstr) & printlines;
-- similar to everything but removing commutativity
["full"] -> allcomplex digit9 & allmults digit9 & map (showmult smallstr) & printlines;
_ -> undefined;
};

type Ii = Integer;

-- Endomorphism. useful for (id :: Endo Integer) to assert a type in a pipeline
type Endo a = a->a;

-- to avoid the redundancy warning
trace_placeholder :: ();
trace_placeholder = (trace,assert,printlines,id :: Endo Integer) & (id >>> error) "trace_placeholder";
-- ghc -O2 -fno-ignore-asserts

printlines :: [String] -> IO();
printlines l = do {
hSetBuffering stdout LineBuffering;
mapM_ putStrLn l;
};

showlines :: (Show a) => [a] -> IO();
showlines = map show >>> printlines;

data Complex = C Ii Ii deriving (Show,Eq,Ord);

multiply :: Complex -> Complex -> Complex;
multiply (C a b) (C c d) = C (a*c-b*d) (a*d+b*c);

magnitudesquared :: Complex -> Squaredmagnitude;
magnitudesquared (C a b) = a*a + b*b & Squaredmagnitude;

sortkey :: Complex -> [Ii];
sortkey (C a b) = [max (abs a) (abs b),abs a, abs b, negate a, negate b];

digit9 :: Sidehalf;
digit9 = Sidehalf 9;

newtype Sidehalf = Sidehalf Ii deriving (Show);

allcomplex :: Sidehalf -> [Complex];
allcomplex (Sidehalf lim) = do {
a <- [negate lim..lim];
-- guard $ a /= 0;
b <- [negate lim..lim];
-- guard $ b /= 0;
return $ C a b;
};

testnoequal :: Sidehalf -> [(Complex,Complex)];
testnoequal lim = do {
x <- allcomplex lim;
y <- allcomplex lim;
guard $ x/=y;
guard $ sortkey x == sortkey y;
return (x,y);
};

inrange :: Sidehalf -> Complex -> Bool;
inrange (Sidehalf lim) (C a b) = (abs a <= lim) && (abs b <= lim);

sortedcomplex :: Sidehalf -> [Complex];
sortedcomplex lim = allcomplex lim & filter nonzero & List.sortOn sortkey;

-- removes approximately half of unsortedmults by commutativity
allmults :: Sidehalf -> [Complex] -> [(Complex,Complex)];
allmults lim l = do {
xlist <- List.inits $ List.sortOn sortkey l;
let {x = last xlist}; -- if xlist is empty, the next line prevents this line from executing
y <- xlist;
guard $ (multiply x y & inrange lim);  -- only multiply big * small (by sortkey)
return (x,y);
};

unsortedallmults :: Sidehalf -> [Complex] -> [(Complex,Complex)];
unsortedallmults lim l = do {
x <- l;
y <- l;
guard $ (multiply x y & inrange lim);
return (x,y);
};

bigstr :: Complex -> String;
bigstr (C a b) = concat ["(", show a , " + ", show b,"i)"];

showmult :: (Complex->String) -> (Complex,Complex) -> String;
showmult myshow (x,y) = concat [myshow x,"*",myshow y,"=",multiply x y & myshow];

nonzero :: Complex -> Bool;
nonzero (C 0 0) = False;
nonzero _ = True;

niceportion :: Complex -> Bool;
niceportion (C a b) = a>=0 && b>0;

moreimaginary :: Complex -> Bool;
moreimaginary (C a b) = b >= a;

someimaginary :: Complex -> Bool;
someimaginary (C _ b) = b/=0;

smallstr :: Complex -> String;
smallstr (C a b) = concat [show a,show b];

nice :: Complex -> Bool;
nice x = niceportion x && nonzero x {- & filter moreimaginary -};

sentenceperiod :: String -> String;
sentenceperiod x = x ++ "";

---- primes continuing aborted work in gaussianprimes.hs

newtype Squaredmagnitude = Squaredmagnitude Ii deriving (Show,Eq,Ord);

allnormlimit :: Squaredmagnitude -> [Complex];

allnormlimit big@(Squaredmagnitude normlimit) = enumFrom 0 & takeWhile (\x-> x*x <= normlimit) & last & Sidehalf & allcomplex & filter (\x -> magnitudesquared x <= big);

-- this is inefficient by the square
--allnormlimit normlimit = allcomplex normlimit & filter (\x -> norm x <= normlimit);

-- mathematical definition: division comes out even by these
unit :: Complex -> Bool;
unit (C a b) = [0,1] == List.sort [abs a, abs b];

nonunits :: Squaredmagnitude -> [Complex];
nonunits = allnormlimit >>> filter (unit >>> not);

-- productlist 4 & Set.fromList & Set.toList & showlines
productlist :: Squaredmagnitude -> [(Complex,(Complex,Complex))];
productlist normlimit = do{
x <- nonunits normlimit;
y <- nonunits normlimit;
let{z=multiply x y};
guard $ magnitudesquared z <= normlimit;
return $ (z,(x,y))
};

productset :: Squaredmagnitude -> Set Complex;
productset = productlist >>> map fst >>> Set.fromList;

primes1 :: Squaredmagnitude -> [Complex];
primes1 normlimit = let{
composites = productset normlimit
} in nonunits normlimit & filter (flip Set.notMember composites);

primesinasquare :: Sidehalf -> [Complex];
primesinasquare sidehalf@(Sidehalf internalsidehalf) = let{
-- the factor of 2 is because we need to get to the opposite corner of the square
composites = 2*internalsidehalf*internalsidehalf & Squaredmagnitude & productset
}in allcomplex sidehalf & filter (unit >>> not) & filter (flip Set.notMember composites);

canonicalize :: Complex -> Complex;
canonicalize z = let{
((p,q),_) = alphabeticalish z
} in C q p;

combinesingle :: (Show a) => [a] -> [a] -> [a];
combinesingle [new] old = new:old;
combinesingle x y = error $ (show x ++ show y);

groupbycanonical :: [Complex] -> Map Complex [Complex];
groupbycanonical = map (\x -> (canonicalize x,[x])) >>> Map.fromListWith combinesingle;

alphabeticalish :: Complex -> ((Ii,Ii),(Ii,Ii,Ii,Ii));
alphabeticalish (C a b) = let{
x=abs a;
y=abs b;
} in case List.sort [x,y]of{
[p,q] -> ((p,q),(x,y,a,b));
_ -> undefined
};

-- [C 2 1,C 2 (-1),C (-2) 1,C (-2) (-1),C 1 2,C 1 (-2),C (-1) 2,C (-1) (-2)])
mysort :: [Complex] -> [Complex];
mysort = List.sortOn alphabeticalish >>> reverse;

listprimesinasquare :: Sidehalf -> [(Complex,[Complex])];
listprimesinasquare = primesinasquare >>> groupbycanonical >>> Map.assocs >>> map (Bifunctor.second mysort);

{- *Main> length$ listprimesinasquare $ Sidehalf 26
82
(47.37 secs, 45,190,549,216 bytes)
7.8s after compile
2.7s after -O2
-}

-- easy to parse, compatible with Pari/GP
showcomplex :: Complex -> String;
showcomplex (C a b) = concat[show a," + ",show b,"*I"];

-- a=1 .. z=26
codeletter :: Ii -> Char;
codeletter i = assert (0<i) $ assert (i<=26) $ 96+fromInteger i & toEnum;

-- assume already canonicalize
code :: Complex -> String;
code (C x 0) = [codeletter x];
code (C a b) = map codeletter [a,b];

showprimeandreflections :: (Complex,[Complex]) -> String;
showprimeandreflections (canonical,l) = "code="++code canonical++", "++(magnitudesquared canonical&show)++", ["++(map showcomplex l & List.intersperse", "&concat)++"]";

smallgaussianprimes :: IO();
smallgaussianprimes = listprimesinasquare (Sidehalf 26) & map showprimeandreflections & printlines;

isprime :: Ii -> Bool;
isprime n = if n<0 then undefined
else if n<2 then False
else enumFrom 2 & takeWhile (\x -> x*x <= n) & map (\x -> mod n x /= 0) & and;

-- primality test from Wikipedia article Gaussian Integer
isgaussianprime :: Complex -> Bool;
isgaussianprime z = case alphabeticalish z&fst of
{ (0,x) -> case mod x 4 of
  { 3 -> isprime x
  ; _ -> False
  }
; _ -> magnitudesquared z & (\(Squaredmagnitude x)->x) & isprime
};

verify :: Sidehalf -> Bool;
verify x = primesinasquare x == (allcomplex x & filter isgaussianprime);

-- test the wikipedia definition within a square.
-- time for i in `seq 1 60` ; do echo $i ; command time ./a.out testwikipediaipedia $i ; sleep 0.1 ;  done
-- 14m20s
testwikipedia :: Sidehalf -> IO();
testwikipedia x = if verify x then return()
else error $ show x;

fullycomplex :: Complex -> Bool;
fullycomplex = alphabeticalish >>> fst >>> fst >>> (\x -> x/=0);

applytuple2 :: (a -> b) -> (a,a) -> [b];
applytuple2 f (x,y) = map f [x,y];

negativereal :: Complex -> Bool;
negativereal (C a _) = a<0;

bothnegativereal :: (Complex,Complex) -> Bool;
bothnegativereal = applytuple2 negativereal >>> and;

latefilter :: Endo[(Complex,Complex)];
latefilter = filter (fst >>> negativereal >>> not) -- avoid initial negative sign because ugly
>>> filter ifinterestingcase
>>> List.sortOn sorttwo;

-- this is in Extra but not in anything more standard
both :: (a -> b) -> (a,a) -> (b,b);
both f (x,y) = (f x, f y);

-- this combinator surprisingly does not exist in hoogle
fboth :: (a->b,a->c) -> a -> (b,c);
fboth (f,g) x = (f x, g x);

ifinterestingcase :: (Complex,Complex) -> Bool;
ifinterestingcase =fboth
(applytuple2 negativereal >>> or -- if either has negative real, then pass
, both sortkey >>> uncurry (>=) -- if both positive real, this is the interesting case.  require the weirder one first.
)>>> uncurry (||);

-- a compromise between being able to find an entry by the digits involved on the left-hand side, and increasing magnitude of products on the right hand side
sorttwo :: (Complex,Complex) -> [Ii];
sorttwo xy = let{
tolist (C a b) = [a,b];
flat :: [Ii];
flat = applytuple2 tolist xy & concat;
theproduct :: Complex;
theproduct = uncurry multiply xy;
smallstufffirst :: Endo[Ii];
smallstufffirst = map abs >>> List.sort >>> reverse;
}in[]
++ (flat & smallstufffirst) -- having big numbers anywhere is weirder
++ [theproduct & magnitudesquared & \(Squaredmagnitude s) -> s] -- group similar products
++ (theproduct & tolist & smallstufffirst) -- group similar products -- relevant for 112[234]
++ map abs flat -- bigger numbers early are weirder
++ map negate flat -- negative numbers are weirder
;
} --end
