For each positive integer larger than with prime factorization , its signature is defined as the sum . Does there exist consecutive positive integers such that among them, there are exactly integers whose signatures are strictly smaller than ?
Solution
Yes. Let be the number of integers among having signatures less than . Since , all of have signatures smaller than . Therefore, we have .
Next, let be distinct primes. By the Chinese remainder theorem,
there exists a positive integer such that
For this , since divides for , each of the integers has signature larger than or equal to . This implies .
Now, when we move from the integers to the integers , the number of integers with signature less than will be increased or decreased by , or remain unchanged. Thus, the difference between and is at most . Therefore, in order to decrease to , we must come across a positive integer such that , and we are done.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.