Project Euler Hint

Smallest prime factor Problem 521 Let smpf( n ) be the smallest prime factor of  n . smpf(91)=7 because 91=7×13 and smpf(45)=3 because 45=3×3×5. Let S( n ) be the sum of smpf( i ) for 2 ≤  i  ≤  n . E.g. S(100)=1257. Find S(10 12 ) mod 10 9 . Last time I mentioned "Sieve of Eratosthenes". However, the memory of a personal laptop I can afford only goes around 10^9 considering the sieve takes at least 1 bit for each number for labeling purpose. And 10^9 = 1/8 Gigabyte of memory at least. Since it won't go up to 10^12 anyway, I can play it safe and stick with 10^6 instead of trying to push it for the moment. First, it is obvious that min prime < 10^6 unless the number itself is a prime. Second, assume we set a flag for IsPrime[1] ~ IsPrime[10^6] which takes around 1M of memory. flag = 1 indicate that it is a prime, flag = 0 indicate it is not a prime. Below is just an illustration. //Init IsPrime{}=1; IsPrime[1]=0; //Everytime we encounter a prime(the next n...

Smallest prime factor Problem 521 Let smpf( n ) be the smallest prime factor of  n . smpf(91)=7 because 91=7×13 and smpf(45)=3 because 45=3×3×5. Let S( n ) be the sum of smpf( i ) for 2 ≤  i  ≤  n . E.g. S(100)=1257. Find S(10 12 ) mod 10 9 . First thing comes into mind is Sieve of Eratosthenes.  However, 10^12 equals to 1000G which would cost too much time/space in a average laptop.  1, One thing comes into my mind is that obviously, Prime > 10^6 is only going to be count once. Therefore, take the S(100) as an example; S(100)= 2*50 + 3*17 + 5*7 + 7*4 + sum(prime < 100) - sum(prime < 10) (Note: sum(prime < N) is calculable in wolfram alpha, we don't have to worry about that part at least.) 2, Now let us take a look at the smallest primes. //Define sum_p(P) = count_p(P)*P; //Define count_p(P) = count of smpf(i)=P; We don't need to worry about prime(1) = 2. Because there will always be sum_p(...

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...

Problem 500!!! Problem 500 The number of divisors of 120 is 16. In fact 120 is the smallest number having 16 divisors. Find the smallest number with 2 500500  divisors. Give your answer modulo 500500507. 120 = 2^3 * 5^1 *7^1 Number of Divisors =  4 * 2 * 2 While trying to obtain the smallest number with 2^4 divisors, here are the steps: 1, Understand that what we're really doing is picking 4 smallest numbers from the below table, which is 2,3,4,5; P P^2 P^4 2  4   16 3  9   81 5  25 ... 7  49 ... 11 ... 13 ... 2, Generalize that; We will pick 500500 smallest numbers from the exact same table. Thanks to Wolfram Alpha, we can get the whole table in no time. prime(500500) = 7376507 prime(500500)^(1/2) ~= 2713 = prime(396) prime(500500)^(1/4) ~= 47 = prime(15) prime(500500)^(1/8) ~= 7 = prime(3) prime(500500)^(1/16) ~= 2 = prime(1) That is approximately 396+15+3+1=415 less primes needed. Since, we also ha...

Lousy English, hard to read….Warning…. A=[10^18!/(10^18-10^9+1)!], B=[10^9!]; PRIME=P; A has a prime factor “P”s, B has b prime factor “P”s; since A/B is Combination(10^18,10^9), A/B is integer; Therefore, a>=b; 1, a>b A/B = 0 mod P 2, a=b A’=A/P^a;B’=B/P^b=B/p^a; A1=A’%P; B1=B’%P; Exists B2, B1*B2=1 mod P,since (B1,P)=1; =>(B2,P)=1; We can draw the conclusion below: A/B = A1*B2 (MOD P) Here’s the proof: INT R = A/B = A’/B'; R = r (mod P) (1<r<P-1); (R,P)=1; (r,P)=1; (A’,P)=1; (B’,P)=1; MOD P RB’ = rB’ => A’ = rB’ => A’ = rB1 => A’B2=r(B1*B2)=r => A1*B2=r=A/B with another hint (P-1)!=1 mod P, everything is good to go.

Last night, I took a while on Problem 358. Here’s the approach without the help of matlab or mathmatica or VS. The main idea of this solution is summed up as below: 1, Cyclic number generated by 1/p, p is a prime number. 2, Prove that SUM(all digits of cyclic number)=(p-1)*9/2 3, the last 5 digits of p can be calculated by hand Conclusion: All help from outside we need is a list of all prime numbers within 724’000’000 to 729’999’999 Brief Proof: 1, Since what makes cyclic number cyclic is: [MOD p]: exist a=10 10/p, 100/p, 1000/p, … , 10^(p-2) in {2, 3, … ,p-1} && 10^(p-1) =1 therefore p is prime (Lehmer’s theorem) 2, This part is simple, if Sn=a1+a2+…+an a1a2a3a4…an is cyclic, then a1a2a3a4…an *1 a1a2a3a4…an *2 … a1a2a3a4…an *(n-1) +) ______________ Sn*111111…1(n-1 digit)=a1a2a3a4…an*(1+2+…+(n-1)) Therefore, Sn*1111..1(n-1 digit)=999..9(n-1 digit) * (1/n) * (n-1)n/2 => Sn=9*(n-1)/2 3, The last 5 digit can be calculated as below: exists N<p, N/p = 0.5678900000000137...