Hint 1 Project Euler Problem 484 Arithmetic Derivative

By -

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·1015
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 using the methods above.
I am just too lazy to calculate that. :)



Comments

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