#include <stdio.h>
#include <math.h>

int baza_2(int n){
	int j, numarul_in_baza_2, power;
	power=1;
	numarul_in_baza_2=0;
	for (j=n;j;j/=2){
		numarul_in_baza_2=numarul_in_baza_2+(j%2)*power;
		power=power*10;
	}
		return numarul_in_baza_2;
}

int numarul_de_cifre_1_din_reprezentarea_binara(int numarul_1){
	int x, nr1, m;
		nr1=0;
		for(m=numarul_1;m;m/=10){
			x=m%10;
			if (x==1)
				nr1++;
		}
			return nr1;
}

int numarul_de_cifre_0_din_reprezentarea_binara(int numarul_0){
	int y, nr0, l;
		nr0=0;
		for(l=numarul_0;l;l/=10){
			y=l%10;
			if (y==0)
				nr0++;
		}
			return nr0;
}

	int main() {
		int n, a0, a1, c, i, k, numarul;
		int nr2, nr_1, nr_0;
			scanf("%d", &n);
			nr2=0;
			//Subpunctul 1: verifica daca numarul "n" citit de la tastatura face parte din seria Lucas.
			a0=2;
			a1=1;
			for(i=2;i<=n;i++){
				c=a0+a1;
				a0=a1;
				a1=c;
				if(n==c)
 				break;
			}
			if(n==c)
			printf("Numarul n face parte din seria Lucas.\n");
			else
			printf("Numarul n nu face parte din seria Lucas.\n");


			//Subpunctul 3: afiseaza si numara numarul de numere mai mici sau egale cu n-ul citit de la tastura care, in binar, au acelasi numar de cifre 0 si 1.

				for(k=1;k<=n;k++){
					numarul=baza_2(k);
					nr_1=numarul_de_cifre_1_din_reprezentarea_binara(numarul);
					nr_0=numarul_de_cifre_0_din_reprezentarea_binara(numarul);
						if(nr_0==nr_1){
						printf("numar gasit=%d\n", k);
						nr2++;
						}
				}
						printf("numarul de numere gasite care veriifica conditiile=%d\n", nr2);
			return 0;
	}