Connect with us

numerical challenge

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

  1. RichD

    RichD Guest

    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. RichD

    RichD Guest

    I think you flunked the interiew.
     
  3. 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. Another way is to calculate
    a^3 mod d, a^9 = (a^3)^3 mod d,
    etc. and use 172 = 2 * 81 + 9 + 1
     
  5. G. Morgan

    G. Morgan Guest

    384?
     
  6. G. Morgan

    G. Morgan Guest

    That's how I interpret it.

    3.2425961901630295961298609791066e+384
     
  7. Tim Williams

    Tim Williams Guest

    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 Else

    Sylvia Else Guest

    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 Else

    Sylvia Else Guest

    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 Bartoli

    Fred Bartoli Guest

    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 Macy

    Robert Macy Guest

    WOW! Those jobs at McDonald's require more and more education!
     
  13. Robert Macy

    Robert Macy Guest

    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 Bartoli

    Fred Bartoli Guest

    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. tm

    tm Guest

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

    John S Guest


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

    Fred Bartoli Guest

    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 :)
     
Ask a Question
Want to reply to this thread or ask your own question?
You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.
Electronics Point Logo
Continue to site
Quote of the day

-