Hint 1 Project Euler Problem 521 Smallest prime factor

By -

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(1012) mod 109.

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(2) = (10^12 / 2) * 2 = 10^12;
It turns out to be 0 when mod 10^9. 
sum_p(2) mod 10^9 = 0;

As for prime(2) = 3, sum_p(3) = upper{(10^12-1)/3/2} * 3 = 5*10^11+1;
sum_p(3) mod 10^9 = 1;

3, Now we will have to deal with 3<prime<10^6 which is 78496 primes.
Let me think about this tonight and write more if I think of something.


---------------------
The opinion above is original and unproven work. Please correct me if I made a mistake.

Comments

  1. UnknownAugust 13, 2016 at 4:07 AM

    I don´t think there is any easy way to calculate the sum of the primes up to 10^12, but we know that the sum of the all numbers from 2 to 10^12 is 10^24-4. So we can take that number and for each non-prime x we subtract x and add smpf(x). We cannot do this separately for each non-prime (it would take too long), we need to calculate the sum of a series and use that. e.g multiples of 2, then multiples of 3 (excluding multiples of 2) etc.

    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