Euler Problem 26
Andrew Mathenge
mathenge at gmail.com
Thu Jul 3 15:09:18 BST 2008
Well done Ronald! If your C++ code is able to spit out the recurring
sequences then perhaps you don't need to count manually ama?
Andrew Mathenge.
On Thu, Jul 3, 2008 at 3:53 AM, kinuthiA muchanE <muchanek at gmail.com> wrote:
> This email is from a ubuntu-ke subscriber to other subscribers inluding you:)
> 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&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&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
>>
>>
>
>
> --
> 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