Euler Problem 145
kinuthiA muchanE
muchanek at gmail.com
Fri Jul 4 14:18:27 BST 2008
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