Hint 3 of Problem 498 Remainder of polynomial division

By -


Problem 498

For positive integers n and m, we define two polynomials Fn(x) = xn and Gm(x) = (x-1)m.
We also define a polynomial Rn,m(x) as the remainder of the division of Fn(x) by Gm(x).
For example, R6,3(x) = 15x2 - 24x + 10.
Let C(n, m, d) be the absolute value of the coefficient of the d-th degree term of Rn,m(x).
We can verify that C(6, 3, 1) = 24 and C(100, 10, 4) = 227197811615775.
Find C(1013, 1012, 104) mod 999999937.

https://projecteuler.net/problem=498

 Finally, we're arriving at our final hint for problem 498.
Note that 999999937 = 10^9-63, plus 999999937 is a prime number.

 p = 999999937 and 10^9 = p+63;
Since we already have the conclusion that, 
C(10^13,10^12,10^4) = C(10^13 , 10^4) * C(10^13-10^4-1 , 10^12-10^4-1)
In fact, we can prove that none of C(10^13 , 10^4) and C(10^13-10^4-1 , 10^12-10^4-1) have p as a factor.
Also, we can prove that, 
C(10^13, 10^4) % p = C(63*10^4, 10^4) % p
C(10^13-10^4-1 , 10^12-10^4-1) % p = C(619999 , 52999) % p

 And there goes our answer.

 ---------------------

The opinion above is original and unproven work. Please correct me if I made a mistake.
Please tell me if you have reached the correct answer using the methods above.
I am just too lazy to calculate that. :)

Comments

  1. UnknownNovember 9, 2017 at 8:46 AM

    The last line must be C(10^13-10^4-1 , 10^12-10^4-1) % p = C(10000,100*C(619999 , 52999) % p

    ReplyDelete

Post a Comment

Popular posts from this blog

Project Euler Problem 684 Inverse Digit Sum - Solution

By Brownie -
Image
This one is relatively straight forward. Below is a solution in python and will give us correct answer within reasonable amount of time. (Generally, if python can calculate this fast enough, I am happy with the solution, nothing against python...) modulo = 1000000007 #speed up hint: (10e9) % modulo = -7 #init speedup array shortcut = 18 arr_lookup = [ 1 ] * (shortcut + 1 ) for i in range ( 1 ,(shortcut + 1 )): arr_lookup[i] = ( 10 ** i) % modulo def S (i): A = i % 9 B = i // 9 #sum = (1+..+A)*(10^B) + A*(10^B-1) + 45*(10^(B-1)) + 9*(10^(B-1)-1) + 45*(10^(B-2)) + 9*(10^(B-2)-1) + ... + 45*10 + 9*9 +45 #sum = (A(A+1)/2)*(10^B) + A*(10^B) - A +(9+45)*(10^(B-1) + .. + 1) - 9*B #sum = (10^B) * (A(A+1)/2 + A) - A - 9*B + 6*(10-1)*(10^(B-1) + .. + 1) = (10^B) * (A(A+1)/2 + A) - A - 9*B + 6*(10^B -1) #sum = (10^B) * (A(A+1)/2 + A + 6) - (A + 9*B + 6) #since (7,10e9+7)=1; 7^(10e9+7 - 1)%(10^9+7)=1 #B = 18C+R C = B ...
Read more

Project Euler Problem 686 Powers of Two - Solution

By Brownie -
Image
Powers of Two     Problem 686 2 7 = 128 2 7 = 128  is the first power of two whose leading digits are "12". The next power of two whose leading digits are "12" is  2 80 2 80 . Define  p ( L , n ) p ( L , n )  to be the  n n th-smallest value of  j j  such that the base 10 representation of  2 j 2 j  begins with the digits of  L L . So  p ( 12 , 1 ) = 7 p ( 12 , 1 ) = 7  and  p ( 12 , 2 ) = 80 p ( 12 , 2 ) = 80 . You are also given that  p ( 123 , 45 ) = 12710 p ( 123 , 45 ) = 12710 . Find  p ( 123 , 678910 ) p ( 123 , 678910 ) . Test the first 3 digits of a large number is quite costly.  So first thing first, think log(). --------------------- import math lowerbound = math.log(1.23,10) upperbound = math.log(1.24,10) def testlog(i): logi = math.log(2,10)*i diff = (logi - int(logi)) return diff We only care about the part after decimal point, thus  dif...
Read more

Project Euler Problem 717 Summation of a Modular Formula - Solution

By Brownie -
Image
Summation of a Modular Formula          Problem 717 For an odd prime  p p , define  f ( p ) = ⌊ 2 ( 2 p ) p ⌋ mod 2 p f ( p ) = ⌊ 2 ( 2 p ) p ⌋ mod 2 p For example, when  p = 3 p = 3 ,  ⌊ 2 8 / 3 ⌋ = 85 ≡ 5 ( mod 8 ) ⌊ 2 8 / 3 ⌋ = 85 ≡ 5 ( mod 8 )  and so  f ( 3 ) = 5 f ( 3 ) = 5 . Further define  g ( p ) = f ( p ) mod p g ( p ) = f ( p ) mod p . You are given  g ( 31 ) = 17 g ( 31 ) = 17 . Now define  G ( N ) G ( N )  to be the summation of  g ( p ) g ( p )  for all odd primes less than  N N . You are given  G ( 100 ) = 474 G ( 100 ) = 474  and  G ( 10 4 ) = 2819236 G ( 10 4 ) = 2819236 . Find  G ( 10 7 ) This problem is not really that complicated to reduce to acceptable execution time. (Python, ~8hrs in 1 thread on a typical laptop.) Please leave a comment if you have better solution or suggestion. See note below. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17...
Read more