Quantcast

A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

ParthKohli

  • 2 years ago

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

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

    @amistre64 Phi function?

  2. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  3. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    How can I proceed with that information?

  4. amistre64
    • 2 years ago
    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

  5. amistre64
    • 2 years ago
    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?

  6. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yup, know that property. :-)

  7. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Idea of mine.

  8. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Or would it be recognizing some pattern?

  9. amistre64
    • 2 years ago
    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?

  10. amistre64
    • 2 years ago
    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

  11. ParthKohli
    • 2 years ago
    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)

  12. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  13. ParthKohli
    • 2 years ago
    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

  14. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Do you see any pattern? o_O

  15. amistre64
    • 2 years ago
    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

  16. ParthKohli
    • 2 years ago
    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

  17. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    no, 576.

  18. amistre64
    • 2 years ago
    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

  19. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Super-exponential function! :-O

  20. amistre64
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  21. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Dag nab those fancy names.

  22. amistre64
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  23. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yup.

  24. amistre64
    • 2 years ago
    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

  25. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Hmm... :-|

  26. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Is there anything to do now? :-\

  27. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  28. amistre64
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    thats fermats little thrm i believe

  29. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Were you able to solve it then?

  30. ParthKohli
    • 2 years ago
    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.

  31. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Thanks for your time!

  32. amistre64
    • 2 years ago
    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.

  33. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Thanks anyway sire!

  34. amistre64
    • 2 years ago
    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 :)

  35. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @experimentX Any ideas on this one?

  36. experimentX
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  37. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    What does Mathematica compute?

  38. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    :-|

  39. experimentX
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    overflow :(((

  40. ParthKohli
    • 2 years ago
    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?

  41. experimentX
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Yep ...

  42. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Darn. I thought Mathematica was smart.

  43. experimentX
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Let me try finding the sum of mods first

  44. ParthKohli
    • 2 years ago
    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.

  45. experimentX
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  46. experimentX
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  47. experimentX
    • 2 years ago
    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.

  48. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yup, that.

  49. ParthKohli
    • 2 years ago
    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. :-|

  50. experimentX
    • 2 years ago
    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.

  51. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Me too :-(

  52. experimentX
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  53. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @Callisto Hi, any ideas?

  54. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Try calculating modulo 1000? Just an idea...

  55. experimentX
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    bug on my code .. :(((

  56. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  57. experimentX
    • 2 years ago
    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.

  58. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    But still lesser than Googol.

  59. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Or is it?

  60. experimentX
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Grahams number is bigger than googol

  61. experimentX
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  62. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Fiasco indeed.

  63. experimentX
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  64. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Ditto!

  65. experimentX
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    freaking group theory is again here.

  66. experimentX
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  67. experimentX
    • 2 years ago
    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)\)

  68. experimentX
    • 2 years ago
    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, ...

  69. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Is there a CRT here too?!

  70. experimentX
    • 2 years ago
    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.

  71. ParthKohli
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  72. experimentX
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  73. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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.