به ازای هر عدد طبیعی $n$، تعداد بیت‌های ۰ سمت راست نمایش دودویی $n$ را $f(n)$ می‌نامیم. برای مثال $f(12)=2$ است.

محور اعداد طبیعی را در نظر بگیرید. قورباغه‌ای داریم که هرگاه روی عدد $n$ قرار بگیرد، می‌تواند به‌یکی از ۲ عدد $n+f(n)$ و $n-f(n)$ برود. قورباغه تنها حق دارد روی اعداد طبیعی قرار بگیرد.

فرض کنید قورباغه روی عدد $n$ باشد. تعداد اعدادی به جز خود $n$، که قورباغه می‌تواند با تعدادی گام به آن‌ها برسد را $g(n)$ می‌نامیم. برای مثال، $g(4)=6$ و $g(3)=0$ است. مقدار $g(1)+g(2)+\ldots+g(10^6)$ را محاسبه کنید.