{- Try to find a more compact representation of a prime number than merely listing its digits or bits.

Copyright 2017 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 <http://www.gnu.org/licenses/>.
-}
{-# LANGUAGE ScopedTypeVariables, LambdaCase #-}
module Main(main) where {
import System.Environment(getArgs);
import Control.Exception(assert);
import Debug.Trace(trace);
import Data.Function((&));
import Control.Category((>>>));
import Prelude hiding((.),(>>));
import System.IO(hSetBuffering,stdout,BufferMode(LineBuffering));
-- import Data.List;
--import Control.Monad;
--import Data.Maybe;
--import qualified Data.Map as Map;
--import Data.Map(Map);
--import qualified Data.Set as Set;
--import Data.Set(Set);
import Primality2;

-- to avoid the redundancy warning
trace_placeholder :: ();
trace_placeholder = (trace,assert) & (id >>> error) "trace_placeholder";

main :: IO();
main = getArgs >>= \case
{ [n] -> read n & calc
; _ -> getContents >>= (words >>> head >>> read >>> calc)
};


calc :: Integer -> IO ();
calc n = do
{ hSetBuffering stdout LineBuffering
; putStrLn $ "input " ++ show n
; generate_records n & mapM_ (show_record n >>> putStrLn)
};


nn :: Integer;
nn = 1476564251485392778927857721313837180933869708288569663932077079002031653266328641356763872492873429131586567699
-- 3^233+176     ;
-- one in 256 numbers is prime in this region, so we could save up to 8 bits.
-- perhaps not worth it

{-
a-th prime number of the form (b*x+c) larger than d*e^f

probably best is
a-th prime number larger than d*2^f
-}

primes_before :: Integer -> [Integer];
primes_before n = filter isPrime_small $ enumFromThen (pred n) (pred$ pred n);

primes_after :: Integer -> [Integer];
primes_after = enumFrom >>> filter isPrime_small;

bracket_pow2 :: Integer -> Integer -> Integer;
bracket_pow2 start end = go 0 start end where
{ go n p q = let
{ p2 = div p 2
; q2 = div q 2
} in if p2 == q2
then n else go (succ n) p2 q2
};

get_pow2_floor :: Integer -> Integer -> Integer;
get_pow2_floor n pp = (2^pp) * div n (2^pp);

brackets_primes_before :: Integer -> [Integer];
brackets_primes_before n = primes_before n & map (bracket_pow2 n);

record :: (Int, Integer) -> (Int, Integer) -> (Int, Integer);
record old@(_,bestx) new@(_,newx) = if newx>bestx then new else old;

ignore_repeats :: (Eq a) => [a] -> [a];
ignore_repeats [] = [];
ignore_repeats (x:rest) = x: go x rest where
{ go _ [] = []
; go t (y:more) = if t==y then go t more
else y: go y more
};

show_record :: Integer -> (Int,Integer) -> String;
show_record n (i,pp) = "prime # " ++ show (i+1) ++ " after 2^ " ++ show pp ++ " * " ++ show (div n (2^pp));

generate_records :: Integer -> [(Int,Integer)];
generate_records = brackets_primes_before >>> zip [0..] >>> scanl1 record >>> ignore_repeats;

} --end