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 . If you didn't already, read Hint 1 and Hint 2 first.  Below is an implementation based on ideas from Hint 1 and Hint 2, with some performance tuning in place. Below c++ code reaches correct answer in ~1 hour. #include <iostream> #include <vector> using namespace std; int main () { const long long maxp = 1000000 ; const long long maxbillion = 100 ; const long long maxp2 = 10000000000 ; const long long maxarrsize = maxp2 + 1 ; const long long mod = 1000000000 ; std :: vector < bool > primemap( maxp + 1 , true ); std :: vector < long long > arrp = {}; long long sum1 = 0 ; for ( long ...

Integer sided equiangular hexagons     Problem 600 Let  H ( n ) be the number of distinct integer sided  equiangular  convex hexagons with perimeter not exceeding  n . Hexagons are distinct if and only if they are not  congruent . You are given  H (6) = 1,  H (12) = 10,  H (100) = 31248. Find  H (55106). Equiangular hexagons with perimeter not exceeding 12 First convert this problem into below equivalent problem: Find integers: a,b,c (1) a<=b<=c (2) 3x-(a+b+c)<=n (3) x>=(a+b+c) The 2 problems are equivalent, how? a) Add 3 small triangles (a,a,a), (b,b,b), (c,c,c) at each corner of the hexagons, to form a large triangle (x,x,x), due to summitry, simple define (1) a<=b<=c b) As each hexagon has 2 possible x- triangles, in order not to count the same solution twice, always use the one with a smaller x.  Thus, we have 3x <= c+2(x-b-c)+b+2(x-a-b...

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

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