Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

ParthKohli

  • 3 years ago

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

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

    @amistre64 Phi function?

  2. ParthKohli
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    How can I proceed with that information?

  4. amistre64
    • 3 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
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yup, know that property. :-)

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

    Idea of mine.

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

    Or would it be recognizing some pattern?

  9. amistre64
    • 3 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
    • 3 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
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  13. ParthKohli
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Do you see any pattern? o_O

  15. amistre64
    • 3 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
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    no, 576.

  18. amistre64
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Super-exponential function! :-O

  20. amistre64
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Dag nab those fancy names.

  22. amistre64
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yup.

  24. amistre64
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Hmm... :-|

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

    Is there anything to do now? :-\

  27. ParthKohli
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    thats fermats little thrm i believe

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

    Were you able to solve it then?

  30. ParthKohli
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Thanks for your time!

  32. amistre64
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Thanks anyway sire!

  34. amistre64
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @experimentX Any ideas on this one?

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

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

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

    What does Mathematica compute?

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

    :-|

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

    overflow :(((

  40. ParthKohli
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Yep ...

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

    Darn. I thought Mathematica was smart.

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

    Let me try finding the sum of mods first

  44. ParthKohli
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

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

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

  47. experimentX
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yup, that.

  49. ParthKohli
    • 3 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
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Me too :-(

  52. experimentX
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @Callisto Hi, any ideas?

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

    Try calculating modulo 1000? Just an idea...

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

    bug on my code .. :(((

  56. ParthKohli
    • 3 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
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    But still lesser than Googol.

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

    Or is it?

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

    Grahams number is bigger than googol

  61. experimentX
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Fiasco indeed.

  63. experimentX
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Ditto!

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

    freaking group theory is again here.

  66. experimentX
    • 3 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
    • 3 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
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Is there a CRT here too?!

  70. experimentX
    • 3 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
    • 3 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
    • 3 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