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.
-- Rich
If you interpret it in C, 171 XOR 172, it's not that hard:
171 = 160+11 = 0xAB 172 = 160+12 = 0xAC0xB = 0b1011
0xA = 0b1010so 171 ^ 172 = 1.
If you interpret it as taking the 172nd power of 171, you could be there awhile.
Cheers
Phil Hobbs
-- Dr Philip C D Hobbs Principal Consultant ElectroOptical Innovations LLC Optics, Electro-optics, Photonics, Analog Electronics 160 North State Road #203 Briarcliff Manor NY 10510 USA +1 845 480 2058 hobbs at electrooptical dot net http://electrooptical.net
huh?
I think you flunked the interiew.
-- Rich
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.
That's a really stupid interview question for an electronic design position.
-- John Larkin Highland Technology Inc www.highlandtechnology.com jlarkin at highlandtechnology dot com Precision electronic instrumentation Picosecond-resolution Digital Delay and Pulse generators Custom timing and laser controllers Photonics and fiberoptic TTL data links VME analog, thermocouple, LVDT, synchro, tachometer Multichannel arbitrary waveform generators
Another way is to calculate a^3 mod d, a^9 = (a^3)^3 mod d, etc. and use 172 = 2 * 81 + 9 + 1
I'm glad about that. I prefer working on fun stuff, of which I have lots at the moment.
Cheers
Phil Hobbs
-- Dr Philip C D Hobbs Principal Consultant ElectroOptical Innovations LLC Optics, Electro-optics, Photonics, Analog Electronics 160 North State Road #203 Briarcliff Manor NY 10510 USA +1 845 480 2058 hobbs at electrooptical dot net http://electrooptical.net
384?
That's how I interpret it.
3.2425961901630295961298609791066e+384Presumably, 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
-- Deep Friar: a very philosophical monk. Website:
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.
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 10000then 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 100000hmmm...does anyone else see a pattern to these numbers?
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.
1000
Another way is:
171^172 = (170+1)^172Using 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 240Now 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
-- Thanks, Fred.
Perhaps they want to make sure that you are both able and willing to do some actual work.
Here's a hand analysis ...
Let x = 171^172.
First, evaluate x (mod 8) ...
Since x is an odd square,
x = 1 (mod 8)
Next, evaluate x (mod 125) ...
x = 171^172 = 46^172 (mod 125) = (45+1)^172 (mod 125) = C(172,2)*(45^2) + C(172,1)*45 + 1 (mod 125) = (81*25) + (47*45) + 1 (mod 125) = ((80 + 1)*25) + ((50-3)*(50-5)) + 1 (mod 125) = (25) + (-150 + 15) + 1 (mod 125) = 16 (mod 125)
The simultaneous congruences
x = 1 (mod 8) x = 16 (mod 125)
imply
x = 641 (mod 1000)
so the last 3 digits of x are 641.
quasi
That's 172**172.
[pcdh@orthodox ~]$ mc2 'exp(ln(10)*(172*log(172)-384))' 3.242596190163031885571244The answer to the question posed is that the last 3 digits are '641'. (REXX to the rescue.)
[pcdh@orthodox ~]$ rexx rexxtry "numeric digits 500; result=1; do 172; result = result*171; end; say result;" 1189408362050899232331742548544079352843642973887737980381143384247782716222833932275790528049591602801982365577332286115374553061109422815431261462944420553436302158846639937649074486702295858231061014815003701856067898072301499489535982821308553995236716650994484275639670292828652624433814244134653337397556701859802285204337784880847597171549786961194804353449316566215601255402641 ................................ /home/pcdh/apps/rexxtry.rex on UNIXCheers
Phil Hobbs
-- Dr Philip C D Hobbs Principal Consultant ElectroOptical Innovations LLC Optics, Electro-optics, Photonics, Analog Electronics 160 North State Road #203 Briarcliff Manor NY 10510 hobbs at electrooptical dot net http://electrooptical.net
WOW! Those jobs at McDonald's require more and more education!
222833932275790528049591602801982365577332286115374553061109422815431261 462944420553436302158846639937649074486702295858231061014815003701856067 898072301499489535982821308553995236716650994484275639670292828652624433 814244134653337397556701859802285204337784880847597171549786961194804353 449316566215601255402641
IX
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.
On Oct 23, 5:58 am, John Larkin wrote: > On Mon, 22 Oct 2012 18:31:00 -0700 (PDT), RichD > > wrote: > >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. > > That's a really stupid interview question for an electronic design > position. > > --
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.
-- Thanks, Fred.
True, but it only gets worse. Job interview questions are drifting from the irrelevant to the ridiculous. For example:
3,715 questions, none of which have anything to do with engineering.In order to insure my place in infamy, I created my own irrelevant questions. Well, not exactly a question, more of a process. I would show the applicant a PCB from the company product, and ask them to identify components that they've worked with in the past, and give a short description on what they do. Ostensively, this was to gauge experience. Most would recognize about 25% of the major RF components, which was about what I would expect. I then explained what the board did, what products it was used in, some of the parts they missed, and generally filled in the blanks.
I would then give the applicant a tour of the factory, production line, grab a cup of coffee, and return to my messy office where I would hand the applicant the exact same PCB, and ask the exact same question. The real test was whether they were paying attention and how much of my explanation they were able to recall. 50% recognition was typical. Exceptional engineers and techs, which unfortunately we couldn't afford to hire, would come very close to 100% recognition and recall.
Other companies use the interview for testing problem solving skills. Now, that's what I call relevant questions. However, it's occasionally abused by asking the applicant to solve a real problem with a current product. I once interviewed at a company that did that to me. I was presented with a large schematic of the product, and asked to critique the design. After a few minutes of hasty back of the envelope calculations, I declared the product to be over-designed, a tolerance accumulation nightmare, and that there were several active stages that were superfluous. I offered specific recommendations on what should be changed. I then expect to be thanked for my brilliant insights. Instead, I was diplomatically thrown out the door. It seems that the manager that was conducting the interview had designed the product, and did not take kindly to criticism. So much for a relevant problem solving interview.
-- Jeff Liebermann jeffl@cruzio.com 150 Felker St #D http://www.LearnByDestroying.com Santa Cruz CA 95060 http://802.11junk.com Skype: JeffLiebermann AE6KS 831-336-2558
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.