{-
   Copyright 2014 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/>.

-}

module Main where{
import Data.Ratio((%),Rational);

-- look up the sequence for the fractional part of pi on OEIS to discover what it is called.

main = print$engelExpansion (1415926535897932384626433832795028841971693993751058209749445923078164%(10^70));

main1=do{
{- print$f (18%23) 1;
print$f (13%46) 2;
print$f (3%92) 4;
print$f (1%736) 32;
-}
{-
print$f (31%311) 1;
print$f (30%3421) 11;
print$f (19%37631) 121;
print$f (12 % 639727) 2057;
print$f (1 % 16632902) 53482;
-}
-- sequence_ $ do { i<-[2..310]; return$print$ engelExpansion (i%311) };

--print$f (2%15) 3;
putStrLn "done";
return();
};

-- f :: Rational -> Integer -> (Integer,(Integer,Integer),Integer);
f target multiple = let {
i = ceiling $ recip target;
(j,r)=divMod i multiple;
jbig = case r of { 0-> j ; _ -> 1+j};
newm=jbig*multiple;
} in newm;
--(i,(j,r),newm,target-1%newm);

gof target multiple = let {
newm= f target multiple;
} in newm:case target-1%newm of
{0 -> [];
left -> gof left newm;
};

divcollapse _ [] = [];
divcollapse a (b:c) = (div b a):divcollapse b c;

-- actually Pierce expansion
engelExpansion target = divcollapse 1 $ gof target 1;
}