An arithmetic sequence of length n is a sequence of n numbers in which the difference between each pair of adjacent numbers is some constant delta. For example, the sequence 1,6,11,16 is an arithmetic sequence of length 4 with delta=5. Now, consider the infinite set
{ 1, 3, 4, 7, 8, 9, ... }
This set is of particular interest to mathematicians because it contains arbitrarily long arithmetic sequences for any delta, yet it contains no infinitely long arithmetic sequences. The set is contructed by keeping or dropping successive groups of positive integers according to the following pattern: keep one (1), drop one (2), keep two (3,4), drop two (5,6), keep three (7,8,9), drop three (10,11,12), and so on.
Given n and delta, your task is to find the earliest arithmetic sequence contained in the set that has the given length and delta. In other words, you should find the smallest number A such that all integers of the form A+i*delta are in the set, for all i between 0 and n-1, inclusive. You should return A.
|