We consider the classical cow-path/treasure-hunt problem on a discrete infinite line, being solved by a deterministic finite state agent with s states and k pebbles. We show asymptotically optimal solutions for small values of k, as well as an efficient algorithm for general k. For non-constant number of pebbles we show that \(O(\log \log n)\) pebbles are sufficient to find the treasure located at distance n within \(O(n\log n)\) steps. Having more pebbles does not help, as we show a lower bound \(\varOmega (n\log n)\)  steps even with unlimited number of pebbles. Randomization can break this bound, as we show that a randomized agent can solve the problem with expected \(O(n\log \log n)\) steps using \(O(\log \log n)\) pebbles. Along the way, we introduce two subproblems that might be of independent interest, and use the solutions to those as building blocks for our solutions to the treasure-hunt problem. In fact, the core of the paper is a result on how to efficiently travel with a counter implemented by pebbles, so that the amortized cost of the travel is significantly smaller than the traveled distance times the counter size, despite always having the counter nearby for incrementing in each travel step.