Project Euler Forum

Problem 145 (View Problem)
"There are 120 reversible numbers below one-thousand."
Is this _really_ true? I've tried different solutions, but everytime I end up with 125
I even printed them all to a file, and sure, there are 125 numbers n in which all digits of n+reverse(n) is odd. Starting at 10+1=11 and ending with 948+849=1797.

The reverse of '10' is '01' which a leading zero, and leading zeroes are not allowed. I would imagine the other 'extra' reverisble numbers you found also fall into that category, so check and see.

genious999 wrote:The reverse of '10' is '01' which a leading zero, and leading zeroes are not allowed. I would imagine the other 'extra' reverisble numbers you found also fall into that category, so check and see.

So, if reverse(n) has a leading zero, n can't be a reversible number?

No. It explicitly states in the text for the problem "Leading zeroes are not allowed in either n or reverse(n)."

Hm, I thought something weird about "don't count the leading zeros", which I thought was weird since you usually don't add them...

Surely that could be misunderstood.

Thank you.

must the sums be distincts...?? becouse I saw 9999999 mabe 100 times....DD

Nothing in the problem description specifies that sums must be distinct.

Oukej thats very good .-)

that problem made my lifespan sink by factor 2 x_x
unbelievable...

The problem description is indeed confusing. I assumed that 'leading zeros are not allowed' meant 'remove leading zeros before performing the addition'

For the sake of others who come after us, please fix this!

RichardBuckalew wrote:'remove leading zeros before performing the addition'

Could you explain what difference this could possibly make? Last time I checked, I could calculate 120+21=141=120+021.

While taking the quote: "Leading zeroes are not allowed in either n or reverse(n)." to mean that you should strip of leading zeroes does result in tautology in the original problem, there is nothing to say the writer of the problem didn't include one. At first reading I also assumed that is what the line meant, rather than "Any n, or reverse(n) containing leading zeroes should be excluded from the answer." Which I think much more clearly expresses the intent of the line.

Tony

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.

I got an algorithm to correctly solve the example and possibly the actual problem itself, but is there a clever method to solve this one in about a minute? Project Euler's about clearly says that all answers can be approached within one minute.

I already wrote the functions in a header file(I use C) that deal with storing and reversing numbers, rotating numbers, and checking whether the digits is odd and even, so that I don't have to rewrite the functions required to solve the problems over again.

JMW1994 wrote:I got an algorithm to correctly solve the example and possibly the actual problem itself, but is there a clever method to solve this one in about a minute?

My program takes less than a millisecond.

LOL, I'm stuck in the same place as JMW.

I have an algorithm that gives the correct answer for the example in 24ms (using a very sow language).

However, if I have calculated the O of the algorithm correctly it will take about an hour and a half to solve for upto 999999999.

Oh well...

Hi everybody,

Can someone confirm me that below 100 there is 36 reversible numbers and under 300 there is 99 numbers

Thank you

No, Jamel, those counts are too high. You must be counting some that don't meet the problem's requirements.

The problem says that leading zeros are not allowed but I don't think that it's clear how to treat numbers ending in zeros. Should they be completely discarded since reverse(n) would contain leading zeros? Or should the leading zeros in reverse(n) be trimmed? And if so then which digits would correspond to eachother in n and reverse(n)?

Shroots wrote:The problem says that leading zeros are not allowed but I don't think that it's clear how to treat numbers ending in zeros. Should they be completely discarded since reverse(n) would contain leading zeros? Or should the leading zeros in reverse(n) be trimmed? And if so then which digits would correspond to eachother in n and reverse(n)?

From the description of the problem: "Leading zeroes are not allowed in either n or reverse(n).". So neither n nor reverse(n) can end with zero.