Euler Problem 145
kinuthiA muchanE
muchanek at gmail.com
Fri Jul 4 15:27:41 BST 2008
Miano,
I am very much aware of the one minute rule, but accomplishing it is
easier said than done! Getting to optimize your code is always the
hardest part! But sometime you win some and lose some. For example,
yesterday night, I solved number 40 by just looking at it. And by the
way, number 145 came in correct, a sluggish 32 minutes...
Kinuthia...
On Fri, 2008-07-04 at 16:39 +0300, Miano Njoka wrote:
> In the FAQ
> I've written my program but should it take days to get to the answer?
> Absolutely not! Each problem has been designed according to a "one-
> minute rule", which means that although it may take several hours to
> design a successful algorithm with more difficult problems, an
> efficient implementation will allow a solution to be obtained on a
> modestly powered computer in less than one minute.
>
> On Jul 4, 2008, at 4:18 PM, kinuthiA muchanE wrote:
>
> > Habari,
> >
> > Right know I am trying to solve Problem Number 145, I look for the
> > ones
> > which are not too intimidating at first sight :-) I wrote the code in
> > Java and still waiting for the computer to spew the answer 1 hour
> > later!
> >
> >
> > Some positive integers n have the property that the sum [ n +
> > reverse(n) ] consists entirely of odd (decimal) digits. For
> > instance, 36
> > + 63 = 99 and 409 + 904 = 1313. We will call such numbers
> > reversible; so
> > 36, 63, 409, and 904 are reversible. Leading zeroes are not allowed in
> > either n or reverse(n).
> >
> > There are 120 reversible numbers below one-thousand.
> >
> > How many reversible numbers are there below one-billion (109)?
> >
> >
> >
> > Kinuthia...
> > On Fri, 2008-07-04 at 14:16 +0300, Ronald Odero wrote:
> >>
> >> Hi all,
> >> On a second thought, I remembered about counts in my C++ lessons, and
> >> I can now confirm that you got it right Kinuthia. I am begining to
> >> like project euler and I will recommend it to anyone who is serious
> >> into programming. I had lots of problem obtaining the right result
> >> coz
> >> at first I told it to return decimal places that are 50 and above
> >> (which were still many), but eventually instructed it to list all
> >> their corresponding DPs and bingo!
> >> Ronald.
> >> On 7/3/08, kinuthiA muchanE <muchanek at gmail.com> wrote:
> >> Ronald,
> >>
> >> Bed at 2am, that is the spirit! :-) And yes, that is longest
> >> recurring
> >> sequence for d < 1000. And I am curious, why do you want to
> >> count the
> >> decimals manually?
> >>
> >> Kinuthia...
> >>
> >> On Thu, 2008-07-03 at 09:18 +0300, Ronald Odero wrote:
> >>> Hi all,
> >>> I went to bed at 2am because of this. Even a scientific
> >> calculator
> >>> cannot give the complete permutation and so I programmed in
> >> C++ to get
> >>> it. I can say that I have completed the calculation and now
> >> the
> >>> remaining part is counting the decimal places - manually.
> >>> Kinuthia,are you sure that this is the highest permutation?
> >> If so,
> >>> then you will have saved me.
> >>> Ronald.
> >>>
> >>> On Wed, Jul 2, 2008 at 1:46 PM, kinuthiA muchanE
> >> <muchanek at gmail.com>
> >>> wrote:
> >>> This email is from a ubuntu-ke subscriber to other
> >> subscribers
> >>> inluding you:)
> >>>
> >>> Habari wajamaa,
> >>>
> >>> I got it but I am not enthusiastic about it because
> >> it was
> >>> largely trial
> >>> and error. I have never done so much long division
> >> with a pen
> >>> and paper
> >>> trying to look for a pattern in my life! What I was
> >> sure about
> >>> was that
> >>> it had to be a prime.
> >>>
> >>> Using the python's decimal module I set the decimal
> >> precision
> >>> to 1000
> >>> places! Then using my eyes and maybe a bit of luck,
> >> I started
> >>> with 997,
> >>> 991, and then 983... bingo!
> >>>
> >>>
> >>
> >> 00101729399796541200406917599186164801627670396744659206510681586978636826042726347914547304170905391658189216683621566632756866734486266531027466937945066124109867751780264496439471007121057985757884028484231943031536113936927772126144455747711088504577822990844354018311291963377416073245167853509664292980671414038657171922685656154628687690742624618514750762970498474059003051881993896236012207527975584944048830
> >>>
> >>
> >> 11190233977619532044760935910478128179043743641912512716174974567650050864699898270600203458799593082400813835198372329603255340793489318413021363173957273652085452695829094608341810783316378433367243133265513733468972533062054933875890132248219735503560528992878942014242115971515768056968463886063072227873855544252288911495422177009155645981688708036622583926754832146490335707019328585961342828077314343845371312309257375381485249237029501525940996948118006103763987792472024415055951169888097660223804679552390640895218718209562563580874872838250254323499491353
> >>>
> >>> 982 digits!
> >>>
> >>> Andrew, I do not know if you would like to see the
> >> code, if
> >>> you can call
> >>> it that! How did you guys do it?
> >>>
> >>> Kinuthia...
> >>>
> >>> On Tue, 2008-07-01 at 18:06 +0300, Miano Njoka
> >> wrote:
> >>>> I was wrong the first time, got it after a couple
> >> of tries.
> >>> good
> >>>> luck!!! :)
> >>>>
> >>>> On Jul 1, 2008, at 4:37 PM, kinuthiA muchanE
> >> wrote:
> >>>>
> >>>>> Miano,
> >>>>>
> >>>>> Just got back to the computer, right now I am
> >> struggling
> >>> with "for"
> >>>>> loops :-/
> >>>>> I do not know what the answer is but check here
> >>>>>
> >>
> >>>
> >> http://projecteuler.net/index.php?section=problems&amp;id=26
> >>
> >>>>>
> >>>>> Kinuthia...
> >>>>> On Tue, 2008-07-01 at 14:34 +0300, Miano Njoka
> >> wrote:
> >>>>>> I've written a solution using C, I got d=831,
> >> one cycle
> >>> is 69 digits
> >>>>>> long. What is the answer?
> >>>>>>
> >>>>>>
> >>>>>> On Jul 1, 2008, at 12:02 PM, Andrew Mathenge
> >> wrote:
> >>>>>>
> >>>>>>> This email is from a ubuntu-ke subscriber to
> >> other
> >>> subscribers
> >>>>>>> inluding you:)
> >>>>>>> Only glad I could be of assistance. Let me
> >> know if you
> >>> find a python
> >>>>>>> solution to the problem. I wrote a solution in
> >> perl, but
> >>> I'm
> >>>>>>> interested in learning python.
> >>>>>>>
> >>>>>>> Good luck!
> >>>>>>>
> >>>>>>> Andrew.
> >>>>>>>
> >>>>>>> On Tue, Jul 1, 2008 at 2:50 AM, kinuthiA
> >> muchanE
> >>>>>>> <muchanek at gmail.com> wrote:
> >>>>>>>>
> >>>>>>>> On Mon, 2008-06-30 at 18:33 -0400, Andrew
> >> Mathenge
> >>> wrote:
> >>>>>>>>> Actually, I think that understanding the
> >> question is
> >>> the easiest
> >>>>>>>>> part.
> >>>>>>>> Not for me it seems, I think it is one of
> >> those days
> >>> for me when
> >>>>>>>> even
> >>>>>>>> the obvious escapes you :-)
> >>>>>>>>> Here's the question as copied from the
> >> website:
> >>>>>>>>>
> >>>>>>>>> Find the value of d < 1000 for which 1/d
> >> contains the
> >>> longest
> >>>>>>>>> recurring cycle in its decimal fraction
> >> part.
> >>>>>>>>>
> >>>>>>>>> Let's take the example that's given where d
> >> <= 10.
> >>>>>>>>>
> >>>>>>>>> When d = 7, the value of 1/d (1/7) is:
> >>>>>>>>>
> >>>>>>>>>
> >> 0.142857142857142857142857142857142857142857....
> >>>>>>>>
> >>>>>>>> Ah...okay
> >>>>>>>>>
> >>>>>>>>> As you can see, (142857) repeats
> >> indefinitely. It has
> >>> a sequence
> >>>>>>>>> of 6
> >>>>>>>>> digits that repeat. This is longer than any
> >> of the
> >>> others where
> >>>>>>>>> d <=
> >>>>>>>>> 10.
> >>>>>>>> That was the crux of the matter!
> >>>>>>>>>
> >>>>>>>>> Therefore, the question asks, for d = 1 to
> >> 1000, which
> >>> value of d
> >>>>>>>>> has
> >>>>>>>>> the longest sequence of repeating digits in
> >> the
> >>> fractional part?
> >>>>>>>>>
> >>>>>>>>> Quite rightfully so, you can't limit the
> >> number of
> >>> digits to 9
> >>>>>>>>> as in
> >>>>>>>>> your example since there will be a number
> >> with a
> >>> series of
> >>>>>>>>> repeating
> >>>>>>>>> digits greater than 9.
> >>>>>>>>>
> >>>>>>>>> For example, 1/17 is:
> >>>>>>>>>
> >>>>>>>>>
> >>>
> >>
> >> 0.0588235294117647058823529411764705882352941176470588235294117647
> >>>>>>>>> .....
> >>>>>>>>>
> >>>>>>>>> or
> >>>>>>>>>
> >>>>>>>>> 0.(0588235294117647)
> >>>>>>>>>
> >>>>>>>>> The number of repeating digits in this
> >> sequence is 16.
> >>>>>>>>>
> >>>>>>>>> Hope that helps. I'm not a python programmer
> >> so I
> >>> really can't
> >>>>>>>>> help
> >>>>>>>>> debug your code.
> >>>>>>>> It is now crystal clear, Anrdew, and thank
> >> you very
> >>> much for
> >>>>>>>> bailing me
> >>>>>>>> out, do not worry about the code, I just
> >> wanted a nudge
> >>> in the
> >>>>>>>> right
> >>>>>>>> direction ;-)
> >>>>>>>>>
> >>>>>>>>> Andrew.
> >>>>>>>>>
> >>>>>>>>> On Mon, Jun 30, 2008 at 4:03 PM, kinuthiA
> >> muchanE
> >>> <muchanek at gmail.com
> >>>>>>>>>> wrote:
> >>>>>>>>>> This email is from a ubuntu-ke subscriber
> >> to other
> >>> subscribers
> >>>>>>>>>> inluding you:)
> >>>>>>>>>>
> >>>>>>>>>> On Mon, 2008-06-30 at 22:04 +0300, Tony
> >> White wrote:
> >>>>>>>>>>> Hi
> >>>>>>>>>>>
> >>>>>>>>>>> My guess, your pattern is limiting you to
> >> uniquely
> >>> the digits
> >>>>>>>>>>> 0-9, so
> >>>>>>>>>>
> >>>>>>>>>> ...and that is the whole idea IMHO,
> >> actually
> >>> "input-ting" nothing
> >>>>>>>>>> would
> >>>>>>>>>> match my regular expression. There are only
> >> ten
> >>> non-recurring
> >>>>>>>>>> digits in
> >>>>>>>>>> the world ie zero to nine, :-).
> >>>>>>>>>>> that's where it stops. Consider -
> >>> (1011011101234101111109) could
> >>>>>>>>>>> also
> >>>>>>>>>>> be a valid sequence. ie, digits may be
> >> used more
> >>> than once.
> >>>>>>>>>>
> >>>>>>>>>> My dear Tony, so what is the question? I
> >> thought they
> >>> wanted the
> >>>>>>>>>> reciprocal of a number, that will give you
> >> the digits
> >>> "123456789"
> >>>>>>>>>> in a
> >>>>>>>>>> non-repeating order. And
> >> 1011011101234101111109 would
> >>> not match
> >>>>>>>>>> the
> >>>>>>>>>> regular expression I had! 1's are and 0's
> >> occur more
> >>> than once!
> >>>>>>>>>>
> >>>>>>>>>>
> >>>>>>>>>>
> >>>>>>>>>> Mugumo, I think there is always a
> >> mathematical angle
> >>> to
> >>>>>>>>>> everything! And
> >>>>>>>>>> I am okay...
> >>>>>>>>>>
> >>>>>>>>>> Asante kwa kuweza kupata wasaa wa kunijibu,
> >> natumai
> >>> tutaendelea
> >>>>>>>>>> kuwasiliana.
> >>>>>>>>>>
> >>>>>>>>>> Kinuthia...
> >>>>>>>>>>
> >>>>>>>>>>>
> >>>>>>>>>>> Tony
> >>>>>>>>>>>
> >>>>>>>>>>>
> >>>>>>>>>>> 2008/6/30 kinuthiA muchanE
> >> <muchanek at gmail.com>:
> >>>>>>>>>>>> This email is from a ubuntu-ke subscriber
> >> to other
> >>> subscribers
> >>>>>>>>>>>> inluding you:)
> >>>>>>>>>>>> Habari wote,
> >>>>>>>>>>>>
> >>>>>>>>>>>>
> >>>>>>>>>>>> I am trying to solve Problem Number 26
> >>>>>>>>>>>>
> >>
> >>>
> >> (http://projecteuler.net/index.php?section=problems&amp;id=26
> >> )
> >>
> >>> on
> >>>>>>>>>>>> Project
> >>>>>>>>>>>> Euler but apparently the answer I am
> >> submitting is
> >>> wrong.
> >>>>>>>>>>>>
> >>>>>>>>>>>> Here is the problem:
> >>>>>>>>>>>>
> >>>>>>>>>>>>
> >>>>>>>>>>>> A unit fraction contains 1 in the
> >> numerator. The
> >>> decimal
> >>>>>>>>>>>> representation
> >>>>>>>>>>>> of the unit fractions with denominators 2
> >> to 10 are
> >>> given:
> >>>>>>>>>>>>
> >>>>>>>>>>>> 1/2
> >>>>>>>>>>>> =
> >>>>>>>>>>>> 0.5
> >>>>>>>>>>>> 1/3
> >>>>>>>>>>>> =
> >>>>>>>>>>>> 0.(3)
> >>>>>>>>>>>> 1/4
> >>>>>>>>>>>> =
> >>>>>>>>>>>> 0.25
> >>>>>>>>>>>> 1/5
> >>>>>>>>>>>> =
> >>>>>>>>>>>> 0.2
> >>>>>>>>>>>> 1/6
> >>>>>>>>>>>> =
> >>>>>>>>>>>> 0.1(6)
> >>>>>>>>>>>> 1/7
> >>>>>>>>>>>> =
> >>>>>>>>>>>> 0.(142857)
> >>>>>>>>>>>> 1/8
> >>>>>>>>>>>> =
> >>>>>>>>>>>> 0.125
> >>>>>>>>>>>> 1/9
> >>>>>>>>>>>> =
> >>>>>>>>>>>> 0.(1)
> >>>>>>>>>>>> 1/10
> >>>>>>>>>>>> =
> >>>>>>>>>>>> 0.1
> >>>>>>>>>>>>
> >>>>>>>>>>>> Where 0.1(6) means 0.166666..., and has a
> >> 1-digit
> >>> recurring
> >>>>>>>>>>>> cycle. It
> >>>>>>>>>>>> can be seen that 1/7 has a 6-digit
> >> recurring cycle.
> >>>>>>>>>>>>
> >>>>>>>>>>>> Find the value of d < 1000 for which 1/d
> >> contains
> >>> the longest
> >>>>>>>>>>>> recurring
> >>>>>>>>>>>> cycle in its decimal fraction part.
> >>>>>>>>>>>>
> >>>>>>>>>>>> I am giving the answer 38, because 1/38 =
> >>> 0.0263157894. It
> >>>>>>>>>>>> seems I have
> >>>>>>>>>>>> misunderstood the question or I cant
> >> solve it! Here
> >>> is the
> >>>>>>>>>>>> code(in
> >>>>>>>>>>>> Python) that I
> >>>>>>>>>>>> came up with:
> >>>>>>>>>>>>
> >>>>>>>>>>>> def aux(num):
> >>>>>>>>>>>> import re
> >>>>>>>>>>>> pattern =
> >>> re.compile(r"^0?1?2?3?4?5?6?7?8?9?$")
> >>>>>>>>>>>>
> >>>>>>>>>>>> frac ="%.9f"%(1.0/num)
> >>>>>>>>>>>> fracSlice =
> >> frac[2:] # get
> >>> the decimal
> >>>>>>>>>>>> fractional part, ie remove
> >>>>>>>>>>>> '0.'
> >>>>>>>>>>>>
> >>>>>>>>>>>> fracList = list(fracSlice)
> >>> #convert string
> >>>>>>>>>>>> to a
> >>>>>>>>>>>> list
> >>>>>>>>>>>> fracList.sort()
> >>> # I need
> >>>>>>>>>>>> to
> >>>>>>>>>>>> sort , because I will be searching by
> >>>>>>>>>>>> increasing order
> >>>>>>>>>>>>
> >>>>>>>>>>>> testFrac = "".join(fracList) #
> >> convert list
> >>> back to a
> >>>>>>>>>>>> string,
> >>>>>>>>>>>> phew!
> >>>>>>>>>>>> if re.match(pattern,testFrac): # if
> >> the
> >>> pattern matches,
> >>>>>>>>>>>> the
> >>>>>>>>>>>> number is
> >>>>>>>>>>>> our candidate
> >>>>>>>>>>>> print (num,fracSlice)
> >>>>>>>>>>>>
> >>>>>>>>>>>>
> >>>>>>>>>>>> for b in xrange(1,1000):
> >>>>>>>>>>>> aux(b)
> >>>>>>>>>>>>
> >>>>>>>>>>>> Er... er, that does not exactly work as
> >> expected
> >>> but it narrows
> >>>>>>>>>>>> the
> >>>>>>>>>>>> search to only 3 candidates because of
> >> the
> >>> inclusion of the
> >>>>>>>>>>>> zero:
> >>>>>>>>>>>>
> >>>>>>>>>>>> (28, '035714286')
> >>>>>>>>>>>> (38, '026315789')
> >>>>>>>>>>>> (81, '012345679')
> >>>>>>>>>>>>
> >>>>>>>>>>>> For 28, the digit, in the fractional
> >> part, after 8
> >>> is 5, so 5
> >>>>>>>>>>>> is
> >>>>>>>>>>>> repeated and as for, 81 the next digit
> >> after 7 is
> >>> 0, so again 0
> >>>>>>>>>>>> occurs
> >>>>>>>>>>>> twice. But for 38, the next digit after 9
> >> is 4, and
> >>> because it
> >>>>>>>>>>>> has NOT
> >>>>>>>>>>>> occurred before, I assume 38 is the
> >> correct
> >>> answer... and I am
> >>>>>>>>>>>> wrong!
> >>>>>>>>>>>>
> >>>>>>>>>>>> I suspect I have completely misunderstood
> >> the
> >>> question.
> >>>>>>>>>>>>
> >>>>>>>>>>>> Any ideas?
> >>>>>>>>>>>> Thanks!
> >>>>>>>>>>>>
> >>>>>>>>>>>> Kinuthia...
> >>>>>>>>>>>>
> >>>>>>>>>>>>
> >>>>>>>>>>>> --
> >>>>>>>>>>>> Ubuntu-ke mailing list
> >>>>>>>>>>>> Ubuntu-ke at lists.ubuntu.com
> >>>>>>>>>>>>
> >> https://lists.ubuntu.com/mailman/listinfo/ubuntu-ke
> >>>>>>>>>>>>
> >>>>>>>>>>>
> >>>>>>>>>>>
> >>>>>>>>>>>
> >>>>>>>>>>
> >>>>>>>>>>
> >>>>>>>>>> --
> >>>>>>>>>> Ubuntu-ke mailing list
> >>>>>>>>>> Ubuntu-ke at lists.ubuntu.com
> >>>>>>>>>>
> >> https://lists.ubuntu.com/mailman/listinfo/ubuntu-ke
> >>>>>>>>>>
> >>>>>>>>
> >>>>>>>>
> >>>>>>>
> >>>>>>> --
> >>>>>>> Ubuntu-ke mailing list
> >>>>>>> Ubuntu-ke at lists.ubuntu.com
> >>>>>>>
> >> https://lists.ubuntu.com/mailman/listinfo/ubuntu-ke
> >>>>>>
> >>>>>
> >>>>
> >>>
> >>>
> >>> --
> >>> Ubuntu-ke mailing list
> >>> Ubuntu-ke at lists.ubuntu.com
> >>> https://lists.ubuntu.com/mailman/listinfo/ubuntu-ke
> >>>
> >>>
> >>
> >>
> >
>
More information about the Ubuntu-ke
mailing list