We will now derive an upper and a lower estimate for , the number of elements in . For large , these bounds will turn out to be contradictory. Upper estimate Every in can be written as with positive integers and , where is square-free. Since only the primes can show up (with exponent 1) in the prime factorization of , there are at most different possibilities for . Furthermore, there are at most possible values for . This gives us the upper estimate Lower estimate The remaining numbers in the set difference are all divisible by a prime greater than . Let denote the set of those in which are divisible by the th prime . Then Since the number of integers in is at most (actually zero for ), we get Using (1), this implies This produces a contradiction: when , the estimates (2) and (3) cannot both hold, because . Proof that the series exhibits log-log growth Here is another proof that actually gives a lower estimate for the partial sums; in particular, it shows that these sums grow at least as fast as . The proof is due to Ivan Niven, adapted from the product expansion idea of Euler. In the following, a sum or product taken over always represents a sum or product taken over a specified set of primes. The proof rests upon the following four inequalities: Every positive integer can be uniquely expressed as the product of a square-free integer and a square as a consequence of the fundamental theorem of arithmetic. Start with where the βs are 0 (the corresponding power of prime is even) or 1 (the corresponding power of prime is odd). Factor out one copy of all the primes whose β is 1, leaving a product of primes to even powers, itself a square. Relabeling: where the first factor, a product of primes to the first power, is square free. Inverting all the s gives the inequality To see this, note that and That is, is one of the summands in the expanded product . And since is one of the summands of , every summand is represented in one of the terms of when multiplied out. The inequality follows. The upper estimate for the natural logarithm The lower estimate for the exponential function, which holds for all . Let . The upper bound (using a telescoping sum) for