ParthKohli
\[\sum_{k = 1}^{1000} 2^{(k!)!} \equiv n\pmod{1000}\]\(n\) is a three-digit number.
Delete
Share
This Question is Closed
ParthKohli
Best Response
You've already chosen the best response.
0
@amistre64 Phi function?
ParthKohli
Best Response
You've already chosen the best response.
0
Well, \((k!)!\) would be divisible by all positive numbers under \((k!)!\)
ParthKohli
Best Response
You've already chosen the best response.
0
How can I proceed with that information?
amistre64
Best Response
You've already chosen the best response.
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
amistre64
Best Response
You've already chosen the best response.
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?
ParthKohli
Best Response
You've already chosen the best response.
0
Yup, know that property. :-)
ParthKohli
Best Response
You've already chosen the best response.
0
Idea of mine.
ParthKohli
Best Response
You've already chosen the best response.
0
Or would it be recognizing some pattern?
amistre64
Best Response
You've already chosen the best response.
0
it might be patternable ... if your mod reductions simplify down to a repetition
what are the first 10 terms .. or 5 terms?
amistre64
Best Response
You've already chosen the best response.
0
1!, 2!, 6!, 24!, 120!, 720!, ....
that can be a nightmare, but might be reduceable by phis
ParthKohli
Best Response
You've already chosen the best response.
0
a1 = 2 = 0 (mod 1000)
a2 = 4 = 4 (mod 1000)
a3 = 2^(720!) = O_O (mod 2)
ParthKohli
Best Response
You've already chosen the best response.
0
a3 = 2^(6!) = 2^(720) sorry
ParthKohli
Best Response
You've already chosen the best response.
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
ParthKohli
Best Response
You've already chosen the best response.
0
Do you see any pattern? o_O
amistre64
Best Response
You've already chosen the best response.
0
not yet ...
when does 2^n equal a multiple of 1000? i know 2^10 = 1024, which is 24 mod 1000
ParthKohli
Best Response
You've already chosen the best response.
0
2^2 = 4
4^3 = 64
64^4 has the last three digits 216
216^5 has last three digits equal to 216
ParthKohli
Best Response
You've already chosen the best response.
0
no, 576.
ParthKohli
Best Response
You've already chosen the best response.
0
Super-exponential function! :-O
amistre64
Best Response
You've already chosen the best response.
0
i see a pollard factorization method that might be useful ... but might not
ParthKohli
Best Response
You've already chosen the best response.
0
Dag nab those fancy names.
amistre64
Best Response
You've already chosen the best response.
0
2^(p-1)=1 (mod p) per fermat little thrm.
ParthKohli
Best Response
You've already chosen the best response.
0
Yup.
amistre64
Best Response
You've already chosen the best response.
0
if k! = (p-1)q for some interger q, then that reduces to 1 mod p
ParthKohli
Best Response
You've already chosen the best response.
0
Hmm... :-|
ParthKohli
Best Response
You've already chosen the best response.
0
Is there anything to do now? :-\
ParthKohli
Best Response
You've already chosen the best response.
0
Oh.\[k! \equiv 2^{(p - 1)} \pmod{p}\]Is it so?
amistre64
Best Response
You've already chosen the best response.
0
thats fermats little thrm i believe
ParthKohli
Best Response
You've already chosen the best response.
0
Were you able to solve it then?
ParthKohli
Best Response
You've already chosen the best response.
0
Gotta sleep, or rather: gotta sleep on the problem. ;-)
If you have any solution, feel free to post.
ParthKohli
Best Response
You've already chosen the best response.
0
Thanks for your time!
amistre64
Best Response
You've already chosen the best response.
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.
ParthKohli
Best Response
You've already chosen the best response.
0
Thanks anyway sire!
amistre64
Best Response
You've already chosen the best response.
0
ive got my elementary number theory textbook that im looking thru, and might be able to determine something in about a day :)
ParthKohli
Best Response
You've already chosen the best response.
0
@experimentX Any ideas on this one?
experimentX
Best Response
You've already chosen the best response.
2
I don't know ... but let me see.
ParthKohli
Best Response
You've already chosen the best response.
0
What does Mathematica compute?
ParthKohli
Best Response
You've already chosen the best response.
0
:-|
experimentX
Best Response
You've already chosen the best response.
2
overflow :(((
ParthKohli
Best Response
You've already chosen the best response.
0
Oh . . . what do you mean by overflow? It isn't able to compute it due to the hugeness?
experimentX
Best Response
You've already chosen the best response.
2
Yep ...
ParthKohli
Best Response
You've already chosen the best response.
0
Darn. I thought Mathematica was smart.
experimentX
Best Response
You've already chosen the best response.
2
Let me try finding the sum of mods first
ParthKohli
Best Response
You've already chosen the best response.
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.
experimentX
Best Response
You've already chosen the best response.
2
Sum[Mod[2^((i!)!), 1000], {i, 1, 1000}]
experimentX
Best Response
You've already chosen the best response.
2
returns overflow in computation ... let me try on matlab.
experimentX
Best Response
You've already chosen the best response.
2
looks like application of Euler totient function. but let me compute it numerically first.
ParthKohli
Best Response
You've already chosen the best response.
0
Yup, that.
ParthKohli
Best Response
You've already chosen the best response.
0
But it would get harder and harder to compute \(\phi((n!)!)\) as \(n\) increases. :-|
experimentX
Best Response
You've already chosen the best response.
2
trust me .. I don't know that ... I am least experience with number theory.
ParthKohli
Best Response
You've already chosen the best response.
0
Me too :-(
experimentX
Best Response
You've already chosen the best response.
2
damn!! even sum of these numbers is huge digit ... returns NaN
ParthKohli
Best Response
You've already chosen the best response.
0
@Callisto Hi, any ideas?
ParthKohli
Best Response
You've already chosen the best response.
0
Try calculating modulo 1000? Just an idea...
experimentX
Best Response
You've already chosen the best response.
2
bug on my code .. :(((
ParthKohli
Best Response
You've already chosen the best response.
0
Well, it's more like pattern recognition, I guarantee you that.
experimentX
Best Response
You've already chosen the best response.
2
yeah i know ... my code was correct ,,, just 2^(,,(..)) is such a huge number. i guess Bigger than grahms number.
ParthKohli
Best Response
You've already chosen the best response.
0
But still lesser than Googol.
ParthKohli
Best Response
You've already chosen the best response.
0
Or is it?
experimentX
Best Response
You've already chosen the best response.
2
Grahams number is bigger than googol
experimentX
Best Response
You've already chosen the best response.
2
numerically it's a fiasco ... let me look for totient function.
ParthKohli
Best Response
You've already chosen the best response.
0
Fiasco indeed.
experimentX
Best Response
You've already chosen the best response.
2
I never used Totient function on my entire life. ... looks like worth it.
ParthKohli
Best Response
You've already chosen the best response.
0
Ditto!
experimentX
Best Response
You've already chosen the best response.
2
freaking group theory is again here.
experimentX
Best Response
You've already chosen the best response.
2
up until now I managed to calculate 2^1000! mod 1000 numerically.
experimentX
Best Response
You've already chosen the best response.
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)\)
experimentX
Best Response
You've already chosen the best response.
2
The answer is 454 ... Amazing, Apart for Euler theorem I managed to learn Euclid algorithm, System of linear congruence, Chinese Remainder theorem, ...
ParthKohli
Best Response
You've already chosen the best response.
0
Is there a CRT here too?!
experimentX
Best Response
You've already chosen the best response.
2
oh ... just step for understanding Euler's theorem. I have never done number theory in my entire life.
ParthKohli
Best Response
You've already chosen the best response.
0
I see, number theory and contest mathematics combined is pretty hard!
experimentX
Best Response
You've already chosen the best response.
2
quite hard ... i often have difficulty doing problems on most of them.