Project Euler Hint

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

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