## 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

1. ParthKohli Group Title

@amistre64 Phi function?

2. ParthKohli Group Title

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

3. ParthKohli Group Title

How can I proceed with that information?

4. amistre64 Group Title

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 Group Title

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 Group Title

Yup, know that property. :-)

7. ParthKohli Group Title

Idea of mine.

8. ParthKohli Group Title

Or would it be recognizing some pattern?

9. amistre64 Group Title

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

10. amistre64 Group Title

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

11. ParthKohli Group Title

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

12. ParthKohli Group Title

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

13. ParthKohli Group Title

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 Group Title

Do you see any pattern? o_O

15. amistre64 Group Title

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

16. ParthKohli Group Title

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 Group Title

no, 576.

18. amistre64 Group Title

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

19. ParthKohli Group Title

Super-exponential function! :-O

20. amistre64 Group Title

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

21. ParthKohli Group Title

Dag nab those fancy names.

22. amistre64 Group Title

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

23. ParthKohli Group Title

Yup.

24. amistre64 Group Title

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

25. ParthKohli Group Title

Hmm... :-|

26. ParthKohli Group Title

Is there anything to do now? :-\

27. ParthKohli Group Title

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

28. amistre64 Group Title

thats fermats little thrm i believe

29. ParthKohli Group Title

Were you able to solve it then?

30. ParthKohli Group Title

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

31. ParthKohli Group Title

32. amistre64 Group Title

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 Group Title

Thanks anyway sire!

34. amistre64 Group Title

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

35. ParthKohli Group Title

@experimentX Any ideas on this one?

36. experimentX Group Title

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

37. ParthKohli Group Title

What does Mathematica compute?

38. ParthKohli Group Title

:-|

39. experimentX Group Title

overflow :(((

40. ParthKohli Group Title

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

41. experimentX Group Title

Yep ...

42. ParthKohli Group Title

Darn. I thought Mathematica was smart.

43. experimentX Group Title

Let me try finding the sum of mods first

44. ParthKohli Group Title

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 Group Title

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

46. experimentX Group Title

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

47. experimentX Group Title

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

48. ParthKohli Group Title

Yup, that.

49. ParthKohli Group Title

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

50. experimentX Group Title

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

51. ParthKohli Group Title

Me too :-(

52. experimentX Group Title

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

53. ParthKohli Group Title

@Callisto Hi, any ideas?

54. ParthKohli Group Title

Try calculating modulo 1000? Just an idea...

55. experimentX Group Title

bug on my code .. :(((

56. ParthKohli Group Title

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

57. experimentX Group Title

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

58. ParthKohli Group Title

But still lesser than Googol.

59. ParthKohli Group Title

Or is it?

60. experimentX Group Title

Grahams number is bigger than googol

61. experimentX Group Title

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

62. ParthKohli Group Title

Fiasco indeed.

63. experimentX Group Title

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

64. ParthKohli Group Title

Ditto!

65. experimentX Group Title

freaking group theory is again here.

66. experimentX Group Title

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

67. experimentX Group Title

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 Group Title

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

69. ParthKohli Group Title

Is there a CRT here too?!

70. experimentX Group Title

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

71. ParthKohli Group Title

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

72. experimentX Group Title

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