36. [20] Isabella writes the expression d for each positive integer d not exceeding 8! on the board. Seeing that these expressions might not be worth points on HMMT, Vidur simplifies each expression to the √ form a b , where a and b are integers such that b is not divisible by the square of a prime number. √ √ √ √ √ √ (For example, 20, 16, and 6 simplify to 2 5, 4 1, and 1 6, respectively.) Compute the sum of a + b across all expressions that Vidur writes. Submit a positive real number A . If the correct answer is C and your answer is A , you get 1 / 5 max 0 , 20 1 − | log( A/C ) | points. Proposed by: Isabella Quan, Pitchayut Saengrungkongka, Rishabh Das, Vidur Jasuja Answer: 534810086 √ P √ Solution: Let n simplifies to a b , and replace 8! by x . First, notice that a is small n n n n ≤ x √ P 3 / 2 ( O ( x ) in particular) because each term cannot exceed x . On the other hand, b will be n n ≤ x 6 large; we have b = n when n is squarefree, and squarefree numbers occurs over the time. Thus, it n 2 π P suffices to consider b . n n ≤ x We first explain how to derive the formula heuristically. Then, we will provide a rigorous proof that 2 X π 2 3 / 2 B ( x ) := b = x + O ( x ) . n 30 n ≤ x For heuristic explanation, we first rewrite the sum as X X X B ( x ) = b = b. 2 2 a ≤ x a b ≤ x b ≤ x/a b squarefree b squarefree 6 We estimate the inner sum as follows: first, recall that the density of squarefree numbers is . The 2 π 2 sum of first k positive integers is approximately k / 2, so the sum of squarefree numbers from 1 , 2 , . . . , k 2 6 k 3 2 should roughly be about · = k . Knowing this, we estimate 2 2 π 2 π X 2 3 x B ( x ) ≈ 2 2 π a a ≤ x X 3 1 2 = x 2 4 π a a ≤ x ∞ X 3 1 2 ≈ x 2 4 π a a =1 4 2 3 π π 2 2 = x · = x . 2 π 90 30 2 π 2 The estimate · (8!) = 534 834 652 is good enough for 18 points. 30 We now give a rigorous proof, which is essentially the above proof, but the errors are properly treated. To do that, we need several lemmas and some standard techniques in analytic number theory. √ 6 Lemma 1. The number of squarefree integers not exceeding x is x + O ( x ). 2 π Proof. This is a standard result in analytic number theory, but we give the full proof for completeness. ( r ( − 1) n is the product of r ≥ 0 distinct primes μ ( n ) = 0 otherwise. Then, by Inclusion-Exclusion, we have j k X x

{ squarefree ≤ x } = μ ( k )

2 k √ k ≤ x X √ x = μ ( k ) + O ( x ) 2 k √ k ≤ x   X √ μ ( k )   = x + O ( x ) . 2 k √ k ≤ x The inner summation is   ∞ X X Y μ ( k ) 1 1 1   √

• O = 1 − + O 2 2 2 k k p x √ k =1 p prime k ≥ x 1 1 = + O √ 1 1 x 1 + + + . . . 2 2 2 3 6 1 √ = + O , 2 π x so putting it together, we get that √ √ 6 1 6 √

{ squarefree ≤ x } = x + O + O ( x ) = x + O ( x ) .

2 2 π x π Lemma 2. We have X 3 2 3 / 2 n = x + O ( x ) . 2 π n squarefree n ≤ x Proof. We apply Abel’s summation formula on the sequence a = 1 ( n ) and weight ϕ ( n ) = n . n squarefree P Define the partial summation A ( x ) = a . Applying Abel’s summation, we get that n n ≤ x X X n = a ϕ ( n ) n n squarefree n ≤ x n ≤ x Z x ′ = A ( x ) ϕ ( x ) − A ( t ) ϕ ( t ) dt 1 Z x √ √ 6 6 = x + O ( x ) x − t + O ( t ) dt 2 2 π π 1 2 6 6 x 3 / 2 3 / 2 = + O ( x ) − · + O ( x ) 2 2 π x π 2 3 2 3 / 2 = x + O ( x ) . 2 π Main Proof. Once we have Lemma 2., it is easy to get the desired estimate. We have X B ( x ) = b 2 a b ≤ x b squarefree X X = b 2 a ≤ x b ≤ x/a b squarefree 2 3 / 2 X 3 x x = + O 2 4 3 π a a a ≤ x     X X 3 1 1 2 3 / 2     = x + O x . 2 4 3 π a a a ≤ x a ≤ x P ∞ 1 3 / 2 Since converges, we get that the big- O term is indeed O ( x ). Now, we only need to deal 3 a =1 a with the main term. Note the estimate ∞ 4 X X X 1 1 1 π 1 = − = + O . 4 4 4 3 a a a 90 x a =1 a ≤ x a ≥ x Hence, we have 4 2 3 π π 2 3 / 2 2 3 / 2 B ( x ) = x · + O ( x ) = x + O ( x ) , 2 π 90 30 as desired. Here is the code that gives the exact answer: import math n = 40320 a = [ 1 f o r i i n range ( n +1)] f o r d i n range ( 1 , math . c e i l ( math . s q r t ( n ) ) ) : f o r x i n range ( d ∗ ∗ 2 , n+1, d ∗ ∗ 2 ) : a [ x ] = d b = [ i // a [ i ] ∗ ∗ 2 f o r i i n range ( 1 , n +1)] p r i n t ( sum ( a)+sum ( b ) )