The same multiple as before

For a positive integer n n , we define G ( n ) = lcm ( 1 , 2 , , n ) . G(n) = \mbox{lcm}(1,2,\ldots,n). For how many integers 1 k 100 1 \leq k \leq 100 is G ( k ) = G ( k + 1 ) ? G(k) = G(k+1)?

Details and assumptions

You may use the fact that there are 25 primes less than 100.


The answer is 64.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Calvin Lin Staff
May 13, 2014

G ( n + 1 ) = lcm ( n + 1 , G ( n ) ) = ( ( n + 1 ) ( G ( n ) ) gcd ( n + 1 , G ( n ) ) ) . G(n+1) = \mbox{lcm}(n+1,G(n)) = \left( \frac{(n+1) \left(G(n)\right)}{\gcd\left(n+1,G(n)\right)}\right). Suppose the integer m m can be written as the product of two relatively prime factors p , q . p,q. Then p < m , q < m p < m, q < m so p G ( m 1 ) , q G ( m 1 ) p\ \vert\ G(m-1), q\ \vert \ G(m-1) and so m G ( m 1 ) . m\ \vert \ G(m-1). If m m cannot be written as a product of two relatively prime factors, then m m must be a power of a prime. Thus, G ( k ) = G ( k + 1 ) G(k) = G(k+1) if and only if k + 1 k+1 is not a power of a prime. There are 26 primes from 2 2 to 101 , 101, including 2 , 3 , 5 , 7 , 2,3,5,7, which are less than 10. Powers of 2 less than 101 are 4 , 8 , 16 , 32 , 64 4,8,16,32,64 , powers of 3 less than 101 are 9 , 27 , 81 9,27,81 , powers of 5 less than 101 are 25 25 and powers of 7 less than 101 are 49. 49. This is an additional 5 + 3 + 1 + 1 = 10 5 + 3 + 1 + 1 = 10 numbers. Thus, there are 26 + 10 = 36 26 + 10 = 36 powers of primes from 2 to 101, so 100 36 = 64 100 - 36 = 64 of the numbers from 1 to 100 have the property that G ( k ) = G ( k + 1 ) . G(k) = G(k+1).

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...