ParthKohli
  • ParthKohli
\[\sum_{k = 1}^{1000} 2^{(k!)!} \equiv n\pmod{1000}\]\(n\) is a three-digit number.
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
chestercat
  • chestercat
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
ParthKohli
  • ParthKohli
@amistre64 Phi function?
ParthKohli
  • ParthKohli
Well, \((k!)!\) would be divisible by all positive numbers under \((k!)!\)
ParthKohli
  • ParthKohli
How can I proceed with that information?

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

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

Looking for something else?

Not the answer you are looking for? Search for more explanations.