Project Euler Hint

Before throwing all these sites to you, the first question I am gonna answer is "Why do I get taking those challenges at all?".  Motivations: 1, Preparation for future interviews Some folks blame that the current interview scenario put "slow but thorough thinker” in disadvantage. But this can be mitigated by practice. 2, A sense of accomplishment We do a lot of stuff for the sole purpose of earning some sort of achievement ,(e.g. video games). I did this for the same thrill, plus, taking these challenges is beneficial. ------------------------------------------ Here're some hand picked coder challenges for you. 1, ACM Online Judge Site Link:   http://acm.timus.ru/ It is a ACM problem list with online judge. They even hold contests every now and then. Wiki Quote: An online judge is an online system to test programs in  programming  contests. They are also used to practice for such contests. Many of these systems organize ...

Tags: #Project Euler without coding series #wolfram alpha rocks Pandigital prime Problem 41 We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime. What is the largest n-digit pandigital prime that exists? https://projecteuler.net/problem=41 It is easy to prove that if n-digit number N can be divided by 3, the sum of all its digits can be divided by 3. Therefore, the pandigital number forms by 123456789 can be divided by 3 (sum of its 9 digits is 45), thus it cannot be a prime number. Similarly, the pandigital number forms by 12345678 can be divided by 3 (sum of its 9 digits is 45-9 = 36), thus it cannot be a prime number. The best we can do on this is a 7 digit number forms by 7654321. Test the number from largest to smallest on www.wolframalpha.com . 7654321 7654213 7654123 7653421 7653241 7652431 7652413 -> bingo! We got our answer without coding and within only 7 tri...

Tags: #Project Euler without coding series #junior high maths Counting Sundays Problem 19 You are given the following information, but you may prefer to do some research for yourself. 1 Jan 1900 was a Monday. Thirty days has September, April, June and November. All the rest have thirty-one, Saving February alone, Which has twenty-eight, rain or shine. And on leap years, twenty-nine. A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400. How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)? Let's take a break from the latest brain-drilling problems and take a look at some rather simple issues. As you can see from the tags, we will do this without coding. ------------------------------------------------------ Method 1 Tool: Paper, pen 31 days mod 7 = 3 days 30 days mod 7 = 2 days 29 days mod 7 = 1 days 28 days mod 7 = 0 days If assign Mon = 1, Tue = 2, ... , Sat = 6, Sun = 0; we ...

Arithmetic Derivative Problem 484 The  arithmetic derivative  is defined by p'  = 1 for any prime  p ( ab ) '  =  a'b  +  ab'  for all integers  a ,  b  (Leibniz rule) For example, 20 '  = 24 Find ∑  gcd ( k , k' ) for 1 <  k  ≤ 5·10 15 Note:  gcd ( x , y ) denotes the greatest common divisor of  x  and  y . If k=p1^a1 * p2^a2 * ... * pn^an Then k' = a1*p1^(a1-1)*(k/(p1^a1)) + ... + an*pn^(an-1)*(k/(pn^an)) k' = k*(a1/p1 + a2/p2 + ... + an/pn) It is easy to conduct that, unless exists pi|ai,  gcd(k,k') = k/(p1*p2*...*pn) If exists pi|ai, then we have a bonus pi in gcd, gcd(k,k') =  k/(p1*p2*...*pn) * pi The next step is how do we sum it up within reasonable complexity. --------------------- 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 u...

Problem 498 For positive integers  n  and  m , we define two polynomials F n ( x ) =  x n  and G m ( x ) = ( x -1) m . We also define a polynomial R n , m ( x ) as the remainder of the division of F n ( x ) by G m ( x ). For example, R 6,3 ( x ) = 15 x 2  - 24 x  + 10. Let C( n ,  m ,  d ) be the absolute value of the coefficient of the  d -th degree term of R n , m ( x ). We can verify that C(6, 3, 1) = 24 and C(100, 10, 4) = 227197811615775. Find C(10 13 , 10 12 , 10 4 ) 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 fac...

Problem 498 For positive integers  n  and  m , we define two polynomials F n ( x ) =  x n  and G m ( x ) = ( x -1) m . We also define a polynomial R n , m ( x ) as the remainder of the division of F n ( x ) by G m ( x ). For example, R 6,3 ( x ) = 15 x 2  - 24 x  + 10. Let C( n ,  m ,  d ) be the absolute value of the coefficient of the  d -th degree term of R n , m ( x ). We can verify that C(6, 3, 1) = 24 and C(100, 10, 4) = 227197811615775. Find C(10 13 , 10 12 , 10 4 ) mod 999999937. https://projecteuler.net/problem=498 Pick up where we left off earlier. C(n,m,d) =  C(n,d)*  sum(  C(n-d,k)* (-1)^k )    0=<k<=m-d-1 Anyone recall that C(N,K) = C(N-1,K)+C(N-1,K-1); The equation above just makes our life a lot easier. sum(C(N,k) * (-1)^k)   0=<k<=K =C( N-1,K)*(-1)^K + C(N-1,K-1) *(-1)^K + C( N-1,K-1)*(-1)^(K-1) + C(N-1,K-2) *(-1)^(K-1) +... +C(N-1,1)*(-1) + C(N-1,0)*(-1...

Remainder of polynomial division Problem 498 For positive integers  n  and  m , we define two polynomials F n ( x ) =  x n  and G m ( x ) = ( x -1) m . We also define a polynomial R n , m ( x ) as the remainder of the division of F n ( x ) by G m ( x ). For example, R 6,3 ( x ) = 15 x 2  - 24 x  + 10. Let C( n ,  m ,  d ) be the absolute value of the coefficient of the  d -th degree term of R n , m ( x ). We can verify that C(6, 3, 1) = 24 and C(100, 10, 4) = 227197811615775. Find C(10 13 , 10 12 , 10 4 ) mod 999999937. https://projecteuler.net/problem=498 Firstful, let's have t=x-1, therefore, x=t+1; F n ( x ) =   x n   and G m ( x ) = ( x -1) m  F n ( x ) =   (t+1) n  and   G m ( x ) = t m Therefore,  R n , m ( x ) = sum( C(n,i)*t^i )    0=<i<=m-1 Change t back to x,  R = sum( C(n,i) * (x-1)^i) Pick only d-th degree term, C(n,m,d) = sum( C(n,i)*C(i,d...