# 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;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;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