Computational Complexity

Monday, October 20, 2008

 
An interesting Summation

Posted by GASARCH

(Guest post by Richard Matthew McCutchen.)

The formula below appears in The TeXbook as a typesetting exercise (I have slightly modified it): The expression has a clever mathematical meaning that is not discussed in the book. Try to find it and prove it!

Let p(n) be the limit as m &rarr &infin, m &isin Z, of

&sum_k=0...&infin (1- cos^{2m}(k!ⁿπ/n))

(Comment from Bill: &pi is supposed to be pi, the ratio of circumference to diameter of a circle. html doesn't really do a good pi- if someone knows how to, in html, do a better one- let me know.)

10:45 AM # 7 comments

1.  Anonymous says:  
   
   Use LaTeX to make a GIF image. For example, from here:
   
   http://thornahawk.unitedti.org/equationeditor/equationeditor.php
   

   3:27 PM, October 20, 2008

2.  Ambarish says:  
   
   Why don't you simply type it in, like so: π?
   

   3:50 PM, October 20, 2008

3.  KKMD says:  
   
   It seems to me p(n) is the largest prime factor of n.
   
   The sum is counting how many k's there are such that k!^n/n is not an integer, which happens iff some prime factor of n is larger than k.
   

   7:35 AM, October 21, 2008

4.  Anonymous says:  
   
   kkmd: not quite. Suppose n is a large power of 2.
   

   1:00 PM, October 21, 2008

5.  Anonymous says:  
   
   ignore the previous comment. I was forgetting the "^n"
   
   Anyone know the value with the "^n" deleted?
   

   1:11 PM, October 21, 2008

6.  kml says:  
   
   For any fixed m, the infinite sum is actually finite since n divides k! for all k>=n. I have not looked at this carefully, but I think that p(n) is n minus the number of non-negative integers k less than n for which k!^n is a multiple of n.
   

   3:58 PM, October 21, 2008

7.  KKMD says:  
   
   By the same token, if you delet the ^n, you get the Kempner numbers :
   http://www.research.att.com/~njas/sequences/A002034
   

   4:50 AM, October 22, 2008

Comment Feeds: This Post All