Modular Product-Sum Ratio

By -

Modular Product-Sum Ratio

Let \( f(n) \) be the number of pairs of integers \( (x, y) \) such that \( 1 \le x \le y \le n \) and the product \( xy \) is a multiple of the sum \( x+y \).

For example, when \( n = 5 \), there are exactly \( 2 \) valid pairs:

  • \( (2, 2) \), since \( 2 \times 2 = 4 \) is a multiple of \( 2 + 2 = 4 \).
  • \( (4, 4) \), since \( 4 \times 4 = 16 \) is a multiple of \( 4 + 4 = 8 \).

Note that \( (3, 6) \) is not valid since \( y \le 5 \) is required.

You are also given that:

  • \( f(10) = 6 \)
  • \( f(100) = 110 \)
  • \( f(1000) = 1569 \)

Find \( f(10^8) \).

Comments

Post a Comment

Popular posts from this blog

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

Hint for Project Euler Problem 500

By -
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...
Read more