<table cellspacing="0" cellpadding="0" border="0" ><tr><td valign="top" style="font: inherit;">Thanks, all.<div><br></div><div>I have an evaluation copy of Mathematica and have been looking for problems to feed it.</div><div><br></div><div>Michael</div><div><br>--- On <b>Mon, 6/27/11, Brent Yorgey <i><byorgey@seas.upenn.edu></i></b> wrote:<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px;"><br>From: Brent Yorgey <byorgey@seas.upenn.edu><br>Subject: Re: [Haskell-cafe] Fwd: Re: Period of a sequence<br>To: haskell-cafe@haskell.org<br>Date: Monday, June 27, 2011, 9:56 AM<br><br><div class="plainMail">I've attached some code I wrote a while ago for playing with repeating<br>decimal expansions, perhaps you'll find some of it useful.<br><br>-Brent<br><br>On Mon, Jun 27, 2011 at 02:21:55PM +0200, Steffen Schuldenzucker wrote:<br>> <br>> Michael,<br>> <br>> On 06/27/2011 01:51 PM, Steffen
Schuldenzucker wrote:<br>> ><br>> > Forwarding to -cafe<br>> ><br>> > -------- Original Message --------<br>> > Subject: Re: [Haskell-cafe] Period of a sequence<br>> > Date: Mon, 27 Jun 2011 04:46:10 -0700 (PDT)<br>> > From: michael rice <<a ymailto="mailto:nowgate@yahoo.com" href="/mc/compose?to=nowgate@yahoo.com">nowgate@yahoo.com</a>><br>> > To: Steffen Schuldenzucker <<a ymailto="mailto:sschuldenzucker@uni-bonn.de" href="/mc/compose?to=sschuldenzucker@uni-bonn.de">sschuldenzucker@uni-bonn.de</a>><br>> ><br>> > Hi Steffen,<br>> ><br>> > Repeating decimals.<br>> ><br>> > 5/7 == 0.714285 714285 7142857 ... Period = 6<br>> ><br>> > It does seem like a difficult problem.<br>> ><br>> > This one is eventually repeating, with Period = 3<br>> ><br>> > 3227/555 = 5.8144 144 144…<br>> <br>> why not use the well-known
division algorithm: (I hope this is readable)<br>> <br>> 3227 / 555<br>> = 3227 `div` 555 + 3227 `mod` 555 / 555<br>> = 5 + 452 / 555<br>> = 5 + 0.1 * 4520 / 555<br>> = 5 + 0.1 * (4520 `div` 555 + (4520 `mod` 555) / 555)<br>> = 5 + 0.1 * (8 + 80 / 555)<br>> = 5 + 0.1 * (8 + 0.1 * (800 / 555))<br>> = 5 + 0.1 * (8 + 0.1 * (800 `div` 555 + (800 `mod` 555) / 555))<br>> = 5 + 0.1 * (8 + 0.1 * (1 + 245 / 555))<br>> = 5 + 0.1 * (8 + 0.1 * (1 + 0.1 * 2450 / 555))<br>> = 5 + 0.1 * (8 + 0.1 * (1 + 0.1 * (4 + 230 / 555)))<br>> = 5 + 0.1 * (8 + 0.1 * (1 + 0.1 * (4 + 0.1 * 2300 / 555)))<br>> = 5 + 0.1 * (8 + 0.1 * (1 + 0.1 * (4 + 0.1 * (4 + 80 / 555))))<br>> *whoops*, saw 80 already, namely in line 6. Would go on like that<br>> forever if I continued like this, so the final result has to be:<br>> <br>> vvv Part before the place where I saw the '80' first<br>> 5.8 144 144 144 ...<br>>
^^^ Part after I saw the '80'<br>> <br>> So you could write a recursive function that takes as an accumulating<br>> parameter containing the list of numbers already seen:<br>> <br>> -- periodOf n m gives the periodic part of n/m as a decimal fraction.<br>> -- (or an empty list if that number has finitely many decimal places)<br>> > periodOf :: (Integral a) => a -> a -> [a]<br>> > periodOf = periodOfWorker []<br>> > where<br>> > periodOfWorker seen n m<br>> > | n `mod` m == 0 = ...<br>> > | (n `mod` m) `elem` seen = ...<br>> > | otherwise = ...<br>> <br>> >--- On *Mon, 6/27/11, Steffen Schuldenzucker<br>> >/<<a ymailto="mailto:sschuldenzucker@uni-bonn.de"
href="/mc/compose?to=sschuldenzucker@uni-bonn.de">sschuldenzucker@uni-bonn.de</a>>/*wrote:<br>> ><br>> ><br>> >From: Steffen Schuldenzucker <<a ymailto="mailto:sschuldenzucker@uni-bonn.de" href="/mc/compose?to=sschuldenzucker@uni-bonn.de">sschuldenzucker@uni-bonn.de</a>><br>> >Subject: Re: [Haskell-cafe] Period of a sequence<br>> >To: "michael rice" <<a ymailto="mailto:nowgate@yahoo.com" href="/mc/compose?to=nowgate@yahoo.com">nowgate@yahoo.com</a>><br>> >Cc: <a ymailto="mailto:haskell-cafe@haskell.org" href="/mc/compose?to=haskell-cafe@haskell.org">haskell-cafe@haskell.org</a><br>> >Date: Monday, June 27, 2011, 4:32 AM<br>> ><br>> ><br>> ><br>> >On 06/26/2011 04:16 PM, michael rice wrote:<br>> > > MathWorks has the function seqperiod(x) to return the period of<br>> >sequence<br>> > > x. Is there an equivalent function in Haskell?<br>>
><br>> >Could you specify what exactly the function is supposed to do? I am<br>> >pretty sure that a function like<br>> ><br>> >seqPeriod :: (Eq a) => [a] -> Maybe Integer -- Nothing iff non-periodic<br>> ><br>> >cannot be written. If "sequences" are represented by the terms that<br>> >define them (or this information is at least accessible), chances<br>> >might be better, but I would still be interested how such a function<br>> >works. The problem seems undecidable to me in general.<br>> ><br>> >On finite lists (which may be produced from infinite ones via<br>> >'take'), a naive implementation could be this:<br>> ><br>> > ><br>> > > import Data.List (inits, cycle, isPrefixOf)<br>> > > import Debug.Trace<br>> > ><br>> > > -- Given a finite list, calculate its period.<br>> > > -- The first parameter controls what is
accepted as a generator.<br>> >See below.<br>> > > -- Set it to False when looking at chunks from an infinite sequence.<br>> > > listPeriod :: (Eq a) => Bool -> [a] -> Int<br>> > > listPeriod precisely xs = case filter (generates precisely xs)<br>> >(inits xs) of<br>> > > -- as (last $ init xs) == xs, this will always suffice.<br>> > > (g:_) -> length g -- length of the *shortest* generator<br>> > ><br>> > > -- @generates prec xs g@ iff @g@ generates @xs@ by repitition. If<br>> >@prec@, the<br>> > > -- lengths have to match, too. Consider<br>> > > --<br>> > > -- >>> generates True [1,2,3,1,2,1,2] [1,2,3,1,2]<br>> > > -- False<br>> > > --<br>> > > -- >>> generates False [1,2,3,1,2,1,2] [1,2,3,1,2]<br>> > > -- True<br>> > > generates :: (Eq a) => Bool -> [a] -> [a]
-> Bool<br>> > > generates precisely xs g = if null g<br>> > > then null xs<br>> > > else (not precisely || length xs `mod` length g == 0)<br>> > > && xs `isPrefixOf` cycle g<br>> > ><br>> ><br>> >-- Steffen<br>> ><br>> ><br>> >_______________________________________________<br>> >Haskell-Cafe mailing list<br>> ><a ymailto="mailto:Haskell-Cafe@haskell.org" href="/mc/compose?to=Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>> ><a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>> <br>> _______________________________________________<br>> Haskell-Cafe mailing list<br>> <a ymailto="mailto:Haskell-Cafe@haskell.org" href="/mc/compose?to=Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>> <a
href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br></div><br>-----Inline Attachment Follows-----<br><br><div class="plainMail">_______________________________________________<br>Haskell-Cafe mailing list<br><a ymailto="mailto:Haskell-Cafe@haskell.org" href="/mc/compose?to=Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br><a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br></div></blockquote></div></td></tr></table>