Problem:
A sequence of natural numbers is constructed by listing the first 4, then skipping one, listing the next 5, skipping 2, listing 6, skipping 3, and, on the nth iteration, listing n+3 and skipping n. The sequence begins 1,2,3,4,6,7,8,9,10,13. What is the 500,000th number in the sequence?
Answer Choices:
A. 996,506
B. 996,507
C. 996,508
D. 996,509
E. 996,510
Solution:
After the nth iteration there will be 4+5+6+⋯+(n+3)= 2(n+3)(n+4)​−6=2n(n+7)​ numbers listed, and 1+2+3+⋯+n=2n(n+1)​ numbers skipped. The first number to be listed on the (n+1) st iteration will be one more than the sum of these, or n2+4n+1.
It is necessary to find the greatest integer value of n such that 2n(n+7)​<500,000. This implies that n(n+7)<1,000,000. Note that, for n=993, this product becomes 993⋅1000=993,000. Next observe that, in general, (a+k)(b+k)= ab+(a+b)k+k2 so (993+k)(1000+k)=993,000+1993k+k2. By inspection, the largest integer value of k that will satisfy the above inequality is 3 and the n needed is 996. After the 996th iteration, there will be 2993,000+1993⋅3+9​= 2998,988​=499,494 numbers in the sequence. The 997 th iteration will begin with the number 9962+4⋅996+1=996⋅1000+1=996,001.
The 506th number in the 997th iteration will be the 500,000th number in the sequence. This is 996,001+505=(A)996,506​.
The problems on this page are the property of the MAA's American Mathematics Competitions