Euler Problem 26
Andrew Mathenge
mathenge at gmail.com
Wed Jul 2 15:56:23 BST 2008
Congratulations.
I'd definitely like to see python code. I'm a beginner but I'm sure
I'll understand it.
Thanks!
Andrew.
On Wed, Jul 2, 2008 at 6:46 AM, kinuthiA muchanE <muchanek at gmail.com> wrote:
> 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
>> >>
>> >
>>
>
>
More information about the Ubuntu-ke
mailing list