login
a(n) = 2^n - A056188(n).
1

%I #16 Sep 06 2023 21:10:51

%S 1,2,2,8,2,52,2,128,170,764,2,2488,2,11624,16928,32768,2,181324,2,

%T 555296,931610,2802584,2,11007664,6643782,43955032,44739242,136585808,

%U 2,720895864,2,2147483648,3250384970,10923540812,11517062218

%N a(n) = 2^n - A056188(n).

%C For n > 1, a(n) is the number of binary words of length n such that the numbers of 0's and 1's are not coprime. - _Bartlomiej Pawlik_, Sep 03 2023

%F a(n) = 2^n-Sum{binomial[n, k]; k>0, GCD[n, k]=1}, for n>1.

%F a(n) = 2 for primes.

%e For n=6, a(6)=52 because the sum of coefficients is restricted only to k=1,5 so a(6)=64-6-6.

%o (PARI) a(n) = if (n==1, 1, 2^n - sum(k=0, n, if (gcd(n,k) == 1, binomial(n,k)))); \\ _Michel Marcus_, Mar 22 2020

%Y Cf. A056045, A056188.

%K nonn

%O 1,2

%A _Labos Elemer_, Aug 02 2000