Ritka szám

Ritka számoknak nevezzük azokat a természetes számokat, amelyek kettes számrendszerbeli alakjában sehol sincs egymás mellett két szomszédos 1-es számjegy. Az első tíz ritka szám a következő:

1, aminek a bináris alakja 1, amelyben nincs is más számjegy önmagán kívül;
2, aminek a bináris alakja 10, amelyben mindössze egyetlen 1-es számjegy található;
4, aminek a bináris alakja 100;
5, aminek a bináris alakja 101, itt a két 1-es számjegyet egy 0-s számjegy választja el egymástól;
8, aminek a bináris alakja 1000;
9, aminek a bináris alakja 1001;
10, aminek a bináris alakja 1010;
16, aminek a bináris alakja 10000;
17, aminek a bináris alakja 10001;
18, aminek a bináris alakja 10010.

Figyelje meg, hogy ha ismeri bármelyik ritka számot (beleértve akár az elsőt is), abból további ritka számokat pofonegyszerűen tud generálni. Ha páratlan számról van szó, akkor egyszerűen csak meg kell szoroznia 2-vel, és máris megkapott egy újabbat, ha pedig párosról, akkor rögtön két újabbat is elő tud állítani: a kisebbet egy 2-vel való szorzással, a nagyobbat úgy, hogy megnöveli az előbb kiszámított szám értékét 1-gyel.

Írjon programot, amely a standard bemenet soraiból állományvégjelig (EOF-ig) egy-egy pozitív egész számot (n-et, n ≤ 20 000) olvas be! A programja minden beolvasott szám esetén írja a standard kimenetre az n-edik ritka számot!

Példa bemenet

1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 1
2. 2
3. 4
4. 5
5. 8
6. 9
7. 10
8. 16
9. 17
10. 18

letöltés szöveges állományként

Forrás: az ELTE Mester feladatgyűjteménye, ott az NT, OKTV, IOI válogató szint Nemes Tihamér 2. 2016/17 2. forduló témájában lehet megtalálni.