Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

ParthKohli Group Title

\[\sum_{k = 1}^{1000} 2^{(k!)!} \equiv n\pmod{1000}\]\(n\) is a three-digit number.

  • one year ago
  • one year ago

  • This Question is Closed
  1. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    @amistre64 Phi function?

    • one year ago
  2. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Well, \((k!)!\) would be divisible by all positive numbers under \((k!)!\)

    • one year ago
  3. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    How can I proceed with that information?

    • one year ago
  4. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    well, the sum of mods reduces each term .. might be useful. 23 = k (mod 3) k = 2; since 3(7) + 2 = 23 23 = 3+3+3+3+3+3+3+2 3+3+3+3+3+3+3+2 = k (mod 3) 0+0+0+0+0+0+0+2 = k (mod 3) k = 2

    • one year ago
  5. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    im not sure how applicable the phi function might be, is it stated in the question by chance? or was that just an idea of yours?

    • one year ago
  6. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Yup, know that property. :-)

    • one year ago
  7. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Idea of mine.

    • one year ago
  8. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Or would it be recognizing some pattern?

    • one year ago
  9. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    it might be patternable ... if your mod reductions simplify down to a repetition what are the first 10 terms .. or 5 terms?

    • one year ago
  10. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    1!, 2!, 6!, 24!, 120!, 720!, .... that can be a nightmare, but might be reduceable by phis

    • one year ago
  11. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    a1 = 2 = 0 (mod 1000) a2 = 4 = 4 (mod 1000) a3 = 2^(720!) = O_O (mod 2)

    • one year ago
  12. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    a3 = 2^(6!) = 2^(720) sorry

    • one year ago
  13. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    2^(1!) = 2 = 2 (mod 1000) 2^(2!) = 4 = 4 (mod 1000) 2^(3!) = 64 = 64 (mod 1000) 2^(4!) = 216 (mod 1000) Hmm

    • one year ago
  14. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Do you see any pattern? o_O

    • one year ago
  15. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    not yet ... when does 2^n equal a multiple of 1000? i know 2^10 = 1024, which is 24 mod 1000

    • one year ago
  16. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    2^2 = 4 4^3 = 64 64^4 has the last three digits 216 216^5 has last three digits equal to 216

    • one year ago
  17. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    no, 576.

    • one year ago
  18. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    lol, dont look at this: http://www.wolframalpha.com/input/?i=2%5E%28n%21%29%21%2C+n%3D1..3

    • one year ago
  19. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Super-exponential function! :-O

    • one year ago
  20. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    i see a pollard factorization method that might be useful ... but might not

    • one year ago
  21. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Dag nab those fancy names.

    • one year ago
  22. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    2^(p-1)=1 (mod p) per fermat little thrm.

    • one year ago
  23. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Yup.

    • one year ago
  24. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    if k! = (p-1)q for some interger q, then that reduces to 1 mod p

    • one year ago
  25. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Hmm... :-|

    • one year ago
  26. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Is there anything to do now? :-\

    • one year ago
  27. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Oh.\[k! \equiv 2^{(p - 1)} \pmod{p}\]Is it so?

    • one year ago
  28. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    thats fermats little thrm i believe

    • one year ago
  29. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Were you able to solve it then?

    • one year ago
  30. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Gotta sleep, or rather: gotta sleep on the problem. ;-) If you have any solution, feel free to post.

    • one year ago
  31. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Thanks for your time!

    • one year ago
  32. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    me? no, i got no idea what the solution would be for this. number theory is too far behind and too little used for me to think clearly about it.

    • one year ago
  33. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Thanks anyway sire!

    • one year ago
  34. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    ive got my elementary number theory textbook that im looking thru, and might be able to determine something in about a day :)

    • one year ago
  35. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    @experimentX Any ideas on this one?

    • one year ago
  36. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    I don't know ... but let me see.

    • one year ago
  37. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    What does Mathematica compute?

    • one year ago
  38. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    :-|

    • one year ago
  39. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    overflow :(((

    • one year ago
  40. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Oh . . . what do you mean by overflow? It isn't able to compute it due to the hugeness?

    • one year ago
  41. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    Yep ...

    • one year ago
  42. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Darn. I thought Mathematica was smart.

    • one year ago
  43. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    Let me try finding the sum of mods first

    • one year ago
  44. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Yeah, try it one-by-one, maybe we can find some pattern. Actually we did above, but let's see what we get for the further values.

    • one year ago
  45. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    Sum[Mod[2^((i!)!), 1000], {i, 1, 1000}]

    • one year ago
  46. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    returns overflow in computation ... let me try on matlab.

    • one year ago
  47. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    looks like application of Euler totient function. but let me compute it numerically first.

    • one year ago
  48. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Yup, that.

    • one year ago
  49. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    But it would get harder and harder to compute \(\phi((n!)!)\) as \(n\) increases. :-|

    • one year ago
  50. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    trust me .. I don't know that ... I am least experience with number theory.

    • one year ago
  51. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Me too :-(

    • one year ago
  52. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    damn!! even sum of these numbers is huge digit ... returns NaN

    • one year ago
  53. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    @Callisto Hi, any ideas?

    • one year ago
  54. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Try calculating modulo 1000? Just an idea...

    • one year ago
  55. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    bug on my code .. :(((

    • one year ago
  56. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Well, it's more like pattern recognition, I guarantee you that.

    • one year ago
  57. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    yeah i know ... my code was correct ,,, just 2^(,,(..)) is such a huge number. i guess Bigger than grahms number.

    • one year ago
  58. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    But still lesser than Googol.

    • one year ago
  59. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Or is it?

    • one year ago
  60. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    Grahams number is bigger than googol

    • one year ago
  61. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    numerically it's a fiasco ... let me look for totient function.

    • one year ago
  62. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Fiasco indeed.

    • one year ago
  63. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    I never used Totient function on my entire life. ... looks like worth it.

    • one year ago
  64. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Ditto!

    • one year ago
  65. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    freaking group theory is again here.

    • one year ago
  66. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    up until now I managed to calculate 2^1000! mod 1000 numerically.

    • one year ago
  67. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    A very interesting property \[ a^{\phi (n)} = a^{mn} = k \mod n \] So the problem is asking, for what value of \( k \ge n \), \((k!)! = 0 \mod \phi(1000)\)

    • one year ago
  68. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    The answer is 454 ... Amazing, Apart for Euler theorem I managed to learn Euclid algorithm, System of linear congruence, Chinese Remainder theorem, ...

    • one year ago
  69. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Is there a CRT here too?!

    • one year ago
  70. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    oh ... just step for understanding Euler's theorem. I have never done number theory in my entire life.

    • one year ago
  71. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I see, number theory and contest mathematics combined is pretty hard!

    • one year ago
  72. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    quite hard ... i often have difficulty doing problems on most of them.

    • one year ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.