Lowest Arduino Power consumption

[Wrend]

For low self discharge NiMHs, check out Eneloops. They're the only AA and AAA cells I use anymore.

For a cell that you want to last at least several years, the lithium primary ones are probably the way to go.