Question

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

Answer 1

@amistre64 Phi function?

Answer 2

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

Answer 3

How can I proceed with that information?

Answer 4

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

Answer 5

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?

Answer 6

Yup, know that property. :-)

Answer 7

Idea of mine.

Answer 8

Or would it be recognizing some pattern?

Answer 9

it might be patternable ... if your mod reductions simplify down to a repetition

what are the first 10 terms .. or 5 terms?

Answer 10

1!, 2!, 6!, 24!, 120!, 720!, ....

that can be a nightmare, but might be reduceable by phis

Answer 11

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

Answer 12

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

Answer 13

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

Hmm

Answer 14

Do you see any pattern? o_O

Answer 15

not yet ...

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

Answer 16

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

Answer 17

no, 576.

Answer 18

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

Answer 19

Super-exponential function! :-O

Answer 20

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

Answer 21

Dag nab those fancy names.

Answer 22

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

Answer 23

Yup.

Answer 24

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

Answer 25

Hmm... :-|

Answer 26

Is there anything to do now? :-\

Answer 27

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

Answer 28

thats fermats little thrm i believe

Answer 29

Were you able to solve it then?

Answer 30

Gotta sleep, or rather: gotta sleep on the problem. ;-)

If you have any solution, feel free to post.

Answer 31

Thanks for your time!

Answer 32

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.

Answer 33

Thanks anyway sire!

Answer 34

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

Answer 35

@experimentX Any ideas on this one?

Answer 36

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

Answer 37

What does Mathematica compute?

Answer 38

:-|

Answer 39

overflow :(((

Answer 40

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

Answer 41

Yep ...

Answer 42

Darn. I thought Mathematica was smart.

Answer 43

Let me try finding the sum of mods first

Answer 44

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.

Answer 45

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

Answer 46

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

Answer 47

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

Answer 48

Yup, that.

Answer 49

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

Answer 50

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

Answer 51

Me too :-(

Answer 52

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

Answer 53

@Callisto Hi, any ideas?

Answer 54

Try calculating modulo 1000? Just an idea...

Answer 55

bug on my code .. :(((

Answer 56

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

Answer 57

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

Answer 58

But still lesser than Googol.

Answer 59

Or is it?

Answer 60

Grahams number is bigger than googol

Answer 61

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

Answer 62

Fiasco indeed.

Answer 63

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

Answer 64

Ditto!

Answer 65

freaking group theory is again here.

Answer 66

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

Answer 67

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)\)

Answer 68

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

Answer 69

Is there a CRT here too?!

Answer 70

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

Answer 71

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

Answer 72

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