For a positive integer , we define For how many integers is
Details and assumptions
You may use the fact that there are 25 primes less than 100.
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.
G ( n + 1 ) = lcm ( n + 1 , G ( n ) ) = ( g cd ( n + 1 , G ( n ) ) ( n + 1 ) ( G ( n ) ) ) . Suppose the integer m can be written as the product of two relatively prime factors p , q . Then p < m , q < m so p ∣ G ( m − 1 ) , q ∣ G ( m − 1 ) and so m ∣ G ( m − 1 ) . If m cannot be written as a product of two relatively prime factors, then m must be a power of a prime. Thus, G ( k ) = G ( k + 1 ) if and only if k + 1 is not a power of a prime. There are 26 primes from 2 to 1 0 1 , including 2 , 3 , 5 , 7 , which are less than 10. Powers of 2 less than 101 are 4 , 8 , 1 6 , 3 2 , 6 4 , powers of 3 less than 101 are 9 , 2 7 , 8 1 , powers of 5 less than 101 are 2 5 and powers of 7 less than 101 are 4 9 . This is an additional 5 + 3 + 1 + 1 = 1 0 numbers. Thus, there are 2 6 + 1 0 = 3 6 powers of primes from 2 to 101, so 1 0 0 − 3 6 = 6 4 of the numbers from 1 to 100 have the property that G ( k ) = G ( k + 1 ) .