For me a quality mechanical pencil. Either full-metal or some softish finger-friendly material. And, important, a good eraser on the back. Preferably one that can be replaced. I've replaced many with cut-out pieces of bigger erasers.

These pencils are good for cross-words, difficult logical puzzles, but also for prototyping your thoughts on paper.

What I missed was a wooden stick, which I use when I walk with my kids though the woods or on the beach to draw various things in the sand.