Euler Problem 145
Miano Njoka
mianonjoka at gmail.com
Fri Jul 4 14:39:44 BST 2008
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