numerical challenge

whatsoever, GG completely ignores its 'Quote Original' button, and it puts all this double space junk in here just by hitting 'Post Reply'. And if I don't watch it, it will send replies to the author too.

Google is killing iGoogle, too.

What happened to "do no evil"?

whatsoever, GG completely ignores its 'Quote Original' button, and it puts all this double space junk in here just by hitting 'Post Reply'. And if I don't watch it, it will send replies to the author too.

Irritating. I use that daily.

I guess evil has a higher ROI.

whatsoever, GG completely ignores its 'Quote Original' button, and it puts all this double space junk in here just by hitting 'Post Reply'. And if I don't watch it, it will send replies to the author too.

Yup. It's my home page. The sticky note manages my life.

Last time I checked, they were killing it *and* still pushing people to develop new apps for it.

I think the problem with iGoogle is that it doesn't include ads.

Evil.

Hint: iGoogle doesn't sell or display any advertising.

Sold out, cashed in, paid off, etc? The current version is: "You can make money without doing evil".

Incidentally, it was originally "Don't be evil".

I presume it's possible to do evil, and not actually "be" evil.

Generally, other than to prove how smart the interviewer is, these sorts of questions are asked to find out how a candidate goes about solving a problem. The right answer isn't very important (it suggests he's seen it before ;-).

Yes, that's probably what they expect, and would get you the job. It's not too much work.

I did it by looking at periodicities in the second digit, as one does the multiplications. But that became excessive, in the third digit.

But I wonder if there are some obscure number theory short cuts. Which might give you a leg up on other candidates, though it's doubtful the interviewers expect that.

In modulo arithmetic, I thought the modulo had to be a prime number.

2. Is there anything special about 171 and 172?

whatsoever, GG completely ignores its 'Quote Original' button, and it puts all this double space junk in here just by hitting 'Post Reply'. And if I don't watch it, it will send replies to the author too.

That is scary. There are a handful of apps that I rely on, such as Eudora for email. I had to use Microsoft Outlook at a job once and hated it. More than hated it, I found it very disorganized and disfunctional. I would be severely impacted if I could no longer use Eudora for my email. Using anything web based from an outfit like Google is uncertain at best. I think it is not so much *if* they change it, but *when*. If you rely on this, you might want to switch preemptively.

Yeah, well, that's Google!

But then you have eyes wide open, no?

Rick

It depends upon what you mean by "modulo arithmetic". If the modulus is a prime number, then you have a field, i.e. division is defined.

For all x and y (with y non-zero), there exists z such that x = y * z, i.e. z = x / y is always defined. If the modulus isn't a prime number, then this isn't the case; e.g. 1/2 modulo 2 isn't defined: there is no z such that 2*z = 1 modulo 2.

But if you just want the result of additions "modulo N" (multiplication being repeated addition and exponentiation being repeated multiplication), then all intermediate calculations can be performed modulo N regardless of whether or not N is prime.

If you calculate in base N (or a base R such that N=R^K for some integer K), then remember that the carry always propagates from right to left. Any given digit in the operands can affect that digit in the result, and the digits to the left of it, but will never affect the digits to the right of it. So the last K digits of the result will only be affected by the last K digits of the operands. This holds for addition, multiplication, and for the base operand of exponentiation, but not for division or the exponent.

This is why, when generating pseudo-random numbers using a linear congruential generator, you keep the most significant bits and not the least significant bits (the low bits have short periods as the last N bits of the output are only affected by the last N bits of the input).

There's nothing particularly special about 172, but Sylvia noted that the fact 171=900-9^3 can be used to simplify the calculation.

That's a bunch of rigamarole with little to do with a working solution. The crux of the calculation using modular arithmetic is:

((a mod c) x (b mod c)) mod c = (ab) mod c , which is little more than a mental calcilation.

They really put people through the wringer for front desk clerk jobs these days...

crux of the calculation using modular arithmetic is:

mental calcilation.

days...

Nobody's response seemed reasonable to me in the context of RichD's question about modulo arithmetic.

Sylvia.

crux of the calculation using modular arithmetic is:

mental calcilation.

days...

Well then you have something over the people who have made a career in cryptography, since the method of choice IS repeated squaring in modular arithmetic- at least according to a CRC handbook that claims to survey all the background algebra used therein.

crux of the calculation using modular arithmetic is:

mental calcilation.

days...

cryptography, since the method of choice IS repeated squaring in modular arithmetic- at least according to a CRC handbook that claims to survey all the background algebra used therein.

Such people probably spend little of their time performing the calculations manually, but are rather more concerned with finding the most efficient algorithm that can be applied to the general case by a computer.

Such people are also rarely interested in performing calculations modulo 10.

Just because an algorithm is the best solution for the general case on a computer does make it the best solution for a particular case when being calculated by a human modulo 10.

Sylvia.

n. The crux of the calculation using modular arithmetic is:

han a mental calcilation.

these days...

cryptography, since the method of choice IS repeated squaring in modular ar ithmetic- at least according to a CRC handbook that claims to survey all th e background algebra used therein.

2. >

As yet you have not found an efficiency improvement hinging of the numbers

The crux of the calculation using modular arithmetic is:

mental calcilation.

days...

cryptography, since the method of choice IS repeated squaring in modular arithmetic- at least according to a CRC handbook that claims to survey all the background algebra used therein.

and 172, probably because they were just random selections of the Taiwanese puzzle nut who posted the problem. He has a stake in refusing to believe the solution is other than straightforward calculation because he's addicted to the "aha" moment, well he's just not going to get that this time.

The squaring approach appears to require 8 modulo 1000 multiplications.

Using the (170 + 1)^172 approach requires 4 modulo 1000 multiplications, a modulo 1000 addition, a simple division by 2 and a simple addition. Further, some of the factors in the modulo 1000 multipications are multiples of 10 or 100, making them easier to handle.

How was the nationality of the person setting the puzzle a consideration?

Sylvia.

That is after some observations on the operand and other short cuts you too k with the binomial coefficients. And it's supposed to be supperior to bang ing out 5x squares? Maybe you just have lots of time to kill.

It's as much a consideration as the blogger thought it was to include the i nformation in his bio. If he said he was crossdresser living in Toledo , Oh io then fill in the blanks:"...because they were just random selections of the crossdressing Toledo puzzle nut..." Get it?

with the binomial coefficients. And it's supposed to be supperior to banging out

I think that if someone reads that, and then reads your earlier comment about people with careers in cryptography, they'd feel that you are desperately trying to salvage an untenable position.

information in his bio. If he said he was crossdresser living in Toledo , Ohio then fill in the blanks:"...because they were just random selections of the crossdressing Toledo puzzle nut..." Get it?

So, not actually specified in the puzzle. Again, I ask, why was it a consideration?

Sylvia.

with the binomial coefficients. And it's supposed to be supperior to banging out

It happens to be a fact, the method of repeated squares is the most straight forward methodology for computing large powers.

Taiwan has never won. The blogger specializes in IMO preparation, that is his slant, and the puzzles in his blog reflect that.