SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
User avatar
sevvost
Topic Author
Posts: 361
Joined: February 17th, 2006, 7:47 pm

Alternating harmonic sum

April 23rd, 2006, 4:52 am

Let integers m, n satisfy . Prove that m is a multiple of 2003.(This problem of course should have been posted 3 years ago...)
 
User avatar
alexandreC
Posts: 678
Joined: June 9th, 2004, 11:35 pm

Alternating harmonic sum

April 23rd, 2006, 9:17 am

m = 187280139691754991954689696064673719711956788730199355005674805517848644623283\575956589582972941220749058108870240015721647317682809494503732310130055648879\961606413551481551869453347108706902962755469906099131479501769095352735649581\434239212808088032702745003389952703510255438779039702464445167161742840942360\397072142186643221015050354899119482884234567477313020919158418766023013624153\052523781373052284463525342140321762861105335532913216523556739076565249604889\383299681215658737890725382784817644276785987211068931426756143567708362506258\690797803421251146398466511266510214481m / 2003 = 934998201157039400672439820592479878741671436496252396433723442425604815892579\011266048841602302649770634592462506319129542275001545154786481827908415620968\355498819528115585968314264147313544497031801827754026357971887645295734645938\263800363495197367462531220119584141339268291458011495079606426169460014689767\334359172174953674563406664498849140710107675872755970639832345312146847848991\774956472157025883492388128508845545986546857378498335115111028839566897677930\021466206768141477237770258536283795690394344538536851855996722754410197235440\29354869406515799499983280712186827, integer, QED.
Last edited by alexandreC on April 22nd, 2006, 10:00 pm, edited 1 time in total.
 
User avatar
sevvost
Topic Author
Posts: 361
Joined: February 17th, 2006, 7:47 pm

Alternating harmonic sum

April 23rd, 2006, 9:25 am

Great proof! Now I believe it myself
 
User avatar
sevvost
Topic Author
Posts: 361
Joined: February 17th, 2006, 7:47 pm

Alternating harmonic sum

April 23rd, 2006, 6:17 pm

Anyone interested in getting a real proof?
 
User avatar
Chukchi
Posts: 915
Joined: December 15th, 2001, 3:43 am

Alternating harmonic sum

April 23rd, 2006, 6:18 pm

There is a nice theorem about divisibility of numerator of alternating harmonic sum.2003 is a prime p=6k-1 (k=334), then p divides a(4k-1)=a(1335).Ref: http://www.research.att.com/~njas/sequences/A097279
Last edited by Chukchi on April 23rd, 2006, 10:00 pm, edited 1 time in total.
 
User avatar
sevvost
Topic Author
Posts: 361
Joined: February 17th, 2006, 7:47 pm

Alternating harmonic sum

April 23rd, 2006, 6:28 pm

Yes, it is the same statement. Still no proof though...
 
User avatar
zarnywhoop
Posts: 337
Joined: December 2nd, 2004, 5:39 pm

Alternating harmonic sum

April 24th, 2006, 6:13 pm

What's wrong with the given proof? I guess one should show that the suggested numerator and denominator are coprime, but there's not much else to do.
 
User avatar
sevvost
Topic Author
Posts: 361
Joined: February 17th, 2006, 7:47 pm

Alternating harmonic sum

April 24th, 2006, 6:31 pm

QuoteOriginally posted by: zarnywhoopWhat's wrong with the given proof? I guess one should show that the suggested numerator and denominator are coprime, but there's not much else to do.Could there possibly be a bug in the given "proof"?In any case, the real problem is of course to find a proof that would also stand for any prime p = 6k-1, as Chukchi pointed out below.
 
User avatar
mattcushman
Posts: 100
Joined: July 14th, 2002, 3:00 am

Alternating harmonic sum

April 24th, 2006, 7:55 pm

2003 is prime. Multiply numerator and denominator by 2003!, you get that the denominator is not divisible by 2003, and the numerator is a sum of terms of the form (-1)^k 2003!/k, where k<=1335. All of these terms are divisible by 2003, hence the numerator is divisible by 2003. QED.
 
User avatar
mattcushman
Posts: 100
Joined: July 14th, 2002, 3:00 am

Alternating harmonic sum

April 24th, 2006, 8:13 pm

Sorry, meant 1335!
 
User avatar
sevvost
Topic Author
Posts: 361
Joined: February 17th, 2006, 7:47 pm

Alternating harmonic sum

April 24th, 2006, 8:15 pm

QuoteOriginally posted by: mattcushman2003 is prime. Multiply numerator and denominator by 2003!, you get that the denominator is not divisible by 2003, and the numerator is a sum of terms of the form (-1)^k 2003!/k, where k<=1335. All of these terms are divisible by 2003, hence the numerator is divisible by 2003. QED.Why the denominator is not divisible by 2003?Wouldn't this argument hold for any other prime imaginable? Or any other bound (besides 1335), for that matter? P.S. Sorry, crossed with your later post...
Last edited by sevvost on April 23rd, 2006, 10:00 pm, edited 1 time in total.
 
User avatar
mattcushman
Posts: 100
Joined: July 14th, 2002, 3:00 am

Alternating harmonic sum

April 24th, 2006, 8:17 pm

Nevermind.. just realized my "proof" is erroneous. Needs more work on the numerator...
 
User avatar
wannabequantie
Posts: 70
Joined: October 30th, 2004, 12:13 pm

Alternating harmonic sum

April 26th, 2006, 12:39 pm

Hi,Heres a solution to the problem. In what follows i'm going to be working in the field , so when i write a = b i mean of course a=b modulo(2003) and when i write 1/a I mean the inverse of a in this field F. Now note that 1 + 1/2 + 1/3 + ... 1/2002 = 0 since this is the same as the set of numbers 1, 2, 3 ... 2002 under some permutation. Also 1/(2003-a) = -1/a. Now let A = 1 - 1/2 + 1/3 ... 1/1335 = (1-1/2+1/3...1/1335) + (1+1/2+1/3+...1/2002)= 2(1 + 1/3 + 1/5 +... 1/1335) + (1/1336 + ... 1/2002)= 2(1 + 1/3 + 1/5 +... 1/1335) - (1/667 + ... 1)= 2(1 + 1/3 + 1/5 + ...1/1335) - 2(1/2 + 1/4 + ...1/1334)= 2(1 - 1/2 + 1/3 - 1/4 ... 1/1335) = 2A.So now since we have A = 2A therefore A has to be equal to zero! QED.I have left some details to be filled but i assume anyone reading this should be able to fill that in.Ofcourse note that this method is quite general and you can use the same proof for any prime of the form 3n - 1 instead of 2003.
 
User avatar
pk14
Posts: 85
Joined: February 15th, 2006, 12:43 am

Alternating harmonic sum

April 26th, 2006, 5:04 pm

Dear wannabequantie,very nice proof!!! Awesome!!!BTW, are you one of those who came to quant with a Math Ph.D.?
 
User avatar
sevvost
Topic Author
Posts: 361
Joined: February 17th, 2006, 7:47 pm

Alternating harmonic sum

April 26th, 2006, 7:53 pm

Yes, this is correct. Here is a "naive" version of the same solution.m/n = 1 -1/2 + 1/3 - ...- 1/1334 + 1/1335 = (1 + 1/2 + 1/3 +...+ 1/1334 + 1/1335) - 2(1/2 + 1/4 + ... + 1/1334) = 1/668 + 1/669 + ... + 1/1335.Now, grouping terms in pairs in a school kid Gauss manner (conveniently, we have an even number of terms), we have:m/n = (1/668 + 1/1335) + (1/669 + 1/1334) + ... + (1/1001 + 1/1002) and the result follows from each term being equal 2003/q where q = k(2003-k) is relatively prime to 2003.
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On