## ParthKohli 2 years ago $\sum_{k = 1}^{1000} 2^{(k!)!} \equiv n\pmod{1000}$$$n$$ is a three-digit number.

1. ParthKohli

@amistre64 Phi function?

2. ParthKohli

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

3. ParthKohli

How can I proceed with that information?

4. amistre64

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

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

Yup, know that property. :-)

7. ParthKohli

Idea of mine.

8. ParthKohli

Or would it be recognizing some pattern?

9. amistre64

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

10. amistre64

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

11. ParthKohli

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

12. ParthKohli

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

13. ParthKohli

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

Do you see any pattern? o_O

15. amistre64

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

16. ParthKohli

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

no, 576.

18. amistre64

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

19. ParthKohli

Super-exponential function! :-O

20. amistre64

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

21. ParthKohli

Dag nab those fancy names.

22. amistre64

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

23. ParthKohli

Yup.

24. amistre64

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

25. ParthKohli

Hmm... :-|

26. ParthKohli

Is there anything to do now? :-\

27. ParthKohli

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

28. amistre64

thats fermats little thrm i believe

29. ParthKohli

Were you able to solve it then?

30. ParthKohli

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

31. ParthKohli

32. amistre64

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

Thanks anyway sire!

34. amistre64

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

35. ParthKohli

@experimentX Any ideas on this one?

36. experimentX

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

37. ParthKohli

What does Mathematica compute?

38. ParthKohli

:-|

39. experimentX

overflow :(((

40. ParthKohli

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

41. experimentX

Yep ...

42. ParthKohli

Darn. I thought Mathematica was smart.

43. experimentX

Let me try finding the sum of mods first

44. ParthKohli

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

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

46. experimentX

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

47. experimentX

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

48. ParthKohli

Yup, that.

49. ParthKohli

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

50. experimentX

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

51. ParthKohli

Me too :-(

52. experimentX

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

53. ParthKohli

@Callisto Hi, any ideas?

54. ParthKohli

Try calculating modulo 1000? Just an idea...

55. experimentX

bug on my code .. :(((

56. ParthKohli

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

57. experimentX

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

58. ParthKohli

But still lesser than Googol.

59. ParthKohli

Or is it?

60. experimentX

Grahams number is bigger than googol

61. experimentX

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

62. ParthKohli

Fiasco indeed.

63. experimentX

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

64. ParthKohli

Ditto!

65. experimentX

freaking group theory is again here.

66. experimentX

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

67. experimentX

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

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

69. ParthKohli

Is there a CRT here too?!

70. experimentX

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

71. ParthKohli

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

72. experimentX

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