# numerical challenge

Discussion in 'Electronic Design' started by RichD, Oct 23, 2012.

1. ### RichDGuest

I saw this posed as an interview question:

(usual exponent notation)
What are the last 3 digits of 171 ^ 172?

Presumably, one is given pen and paper.

Is there a trick here? The second digit isn't too tough,
but the third is a lot of work.

2. ### RichDGuest

I think you flunked the interiew.

3. ### William ElliotGuest

a = 171; d = 1000
b = 172 = 128 + 32 + 8 + 4

Calculate:
a^2 mod d = 241
a^4 = (a^2)^2 mod d = 241^2 mod d = 81

a^8 = (a^4)^2 mod d
a^32 = (a^8)^4 = [(a^8)^2]^2 mod d
a^128 = (a^32)^4 = [(a^32)^2]^2 mod d

and use those results to calculate

a^172 = a^128 a^32 a^8 a^4 mod d.

4. ### William ElliotGuest

Another way is to calculate
a^3 mod d, a^9 = (a^3)^3 mod d,
etc. and use 172 = 2 * 81 + 9 + 1

384?

6. ### G. MorganGuest

That's how I interpret it.

3.2425961901630295961298609791066e+384

7. ### Tim WilliamsGuest

Presumably, one is given a script interpreter? d3_N = ((171^N) mod 1000) / 100
gets the repeating string:
22085059234420727145664294936788641615890086383701
The 172 mod 50 = 22nd digit (in from the left of this string) is a 6.

Tim

8. ### Sylvia ElseGuest

Don't know about a trick. After noting the (*) result below using a
caculator, I managed to get the right answer from scratch on a
whiteboard, but I doubt I'd have managed to do it in an interview
environment.

Anyway, since we're only looking at the last three digits, we can do
calculations mod 1000.

Also, note that 172 is 4 * 43.

Doing 171^2 by long multiplication, keeping only the last three digits
gives 241.

241^2 by long multiplication, keeping only the last three digits is 81.

So 171^4 = 81 mod 1000 (this is the * result) and 171^172 = 81^43 mod
1000 = 9^86 mod 1000.

Now 9 is 10 - 1, so we have 171^172 = (10 - 1)^86 mod 1000.

If we were to expand that using the binomial theorem, all the terms
would by multiples of 1000, and therefore unimportant, except the last
three.

The last three are

a)(86 * 85) / 2 * 10^2 * (-1)^84,
b) 86 * 10^1 * (-1)^85, and
c)(-1)^86.

a) can also be written 43 * 85 * 100, and since we're taking it modulo
1000, we need only multiply the 3 by the 5, giving 15, and keep only the
5, so a) is 500 mod 1000.

b) is -860

c) is 1

So the result is 500 - 860 + 1 = -359 mod 1000.

But that's negative, so add 1000 to make it positive, and the answer is 641.

Sylvia.

9. ### Guest

This can be done any number of ways using a^(n1 + n2 + n3 + ...+ nk)=
(a^n1) x (a^n2) x ...(a^nk) and the identity (a^n)^m = a^(n x m)
so since 172=128 + 32 + 8 + 4, 171^172= 171^128 x 171^32 x 171^8 x 171^4

in modulo 1000 arithmetic
(171)^1 = 171
(171)^2 = 241
(171)^4=(171^2)^2= 241 x 241=81 etc
(171)^8= 81^2=561
(171)^16=561^2=721
(171)^32=721^2=841
(171)^64=841^2=281
(171)^128=281^2=961

so 171^172= 171^128 x 171^32 x 171^8 x 171^4= 961 x 841 x 561 x 81 =641 mod 1000
using mod 1000 at intermediate multiplications...
i.e. 641 are least three digits

If you want last four digits then use modulo 10000:

(171)^1 = 171
(171)^2 = 9241
(171)^4=(171^2)^2= 6081
(171)^8= 81^2=8561
(171)^16=561^2=0721
(171)^32=721^2=9841
(171)^64=841^2=5281
(171)^128=281^2=8961

171^172=8961 x 9841 x 8561 x 6081= 2641 mod 10000

then mod 100,000 for last five digits:
(171)^1 = 171
(171)^2 = 29241
(171)^4=(171^2)^2= 36081
(171)^8= 81^2=38561
(171)^16=561^2=50721
(171)^32=721^2=19841
(171)^64=841^2=65281
(171)^128=281^2=8961

171^172=8961 x 19841 x 38561 x 36081= 02641 mod 100000

hmmm...does anyone else see a pattern to these numbers?

10. ### Sylvia ElseGuest

Indeed thinking along similar lines, one can write 171 as (170 + 1).

So we need (170 + 1)^172 mod 1000.

Again, only the last three terms can be non-zero mod 1000.

a) (172 * 171) / 2 * 170^2
b) 172 * 170
c) 1

a) is 56 * 171 * 170^2.

170^2 is 900 mod (square the 7, and drop the leading 4).
Now mutiply by the 6 and 1, and drop the leading 5, gives 400.

b) is 2 * 170 + 70 * 70 mod 1000 = 340 + 900 mod 1000.

So the sum is 400 + 340 + 900 + 1 mod 1000, or, unsurprisingly 641.

Sylvia.

11. ### Fred BartoliGuest

a écrit :
Another way is:

171^172 = (170+1)^172

Using binomial expansion you have the first terms being

1 + 172 * 170 + 172!/(2! 170!) * 170^2 + ...

The modulo 1000 '...' terms are obviously null.

and all that simplifies to 1 + 170*172 + 172*171/2*170^2

170*172 = 29240 of which we keep 240

Now for the last term, thinking being fast and computing being slow (no
GHz pencil) :

170^2 will write as xy900,

172*171/2 = 86*171 will end with a 6

and the modulo 1000 172*171/2*170^2 term will then be 400.

The last three digits of 171^172 are thus 400+240+1 = 641

12. ### Robert MacyGuest

WOW! Those jobs at McDonald's require more and more education!

13. ### Robert MacyGuest

decimal 171 * 172 = 29412
octal 171 * 172 = 34652
hex 171 * 172 = 21552

not sure the point of that question, except to see if the applicant
starts shaking.

I much prefer more 'imaginative' questions, like, "How many uses for a
standard cinder block, except its intended construction purpose, can
you think of?"

Supposed to be over 26, I could only think of around 6 and that
included using a a leather thong and tying it around your neck as a
super macho tiki god.

14. ### Fred BartoliGuest

Can't disagree more.
Such a question will expose the way of thinking on a seemingly difficult pb.
There's a huge tendency to jump on the most obvious answer, that is
brute force computing, where with a bit of thinking you can find elegant
and easy solutions.

I'd sure like to have a guy able to, under pressure, think one minute or
two, see the easy way, ... in addition to have the design skills.

15. ### Guest

Ugh- and you think that is better than modular arithmetic? The method I demonstrated actually has a name, the right-to-left binary method.
http://en.wikipedia.org/wiki/Modular_exponentiation
I thought there might be some esoteric theorem leading to a short cut basedon factorization of something or another, but there isn't that I can find.

16. ### Guest

Consider yourself lucky. Who would want to work for a worthless trouble-making asshole with an ego to boot? People like that make me applaud when engineering jobs are shipped to China, actually I don't care if they're shippedto Mars- whatever it takes to kick trash like that to the curb works.

17. ### Guest

!WRONG! Base voltage is 5V .
Okay, now that is 5V-0.6V .

Ummm, gimme a minute, that's a tough one.

18. ### tmGuest

Sorry, you stay in the 47%. Go get your food stamps.

19. ### John SGuest

Damn! I sure hope somebody read Sylvia's post. Very nice!

20. ### Fred BartoliGuest

a écrit :
I never made such a claim.
Rather it being another way, which is perfectly valid.

Given the constrains of only pencil, paper and limited time, it
immediately came to mind and I had the answer with very low efforts in
less than 5 minutes, which is a good answer for an interview. And a bit
of astuteness to save some operations don't hurt.

Guess I'd hire me   