Делал подобный проект.
1. Сначала нужно определить границы начального значения. В вашем случае это 1...1500
2. Далее - определяем разрядность максимального значения. В вашем случае это тысяча: 1000
3. Шагаем в цикле с шагом +1000 Это значения 1, 1000, 2000 (последнее на самом деле 1500). Вычисляем CalcValue. Допустим определили, что нужное значение находится во второй тысяче.
4. Шагаем в цикле во второй тысяче с шагом +100 это значения 1000, 1100, 1200, 1300 ... 2000 Вычисляем CalcValue. Допустим определили, что нужное значение находится в третьей сотне.
5. Шагаем в цикле в третьей сотне с шагом +10 это значения 1300, 1310, 1320, .... 1400 Вычисляем CalcValue.
И так далее, идём до единиц.
В этом алгоритме вычисление CalcValue будет производиться минимальное количество раз.