A056188 - OEIS

%I #28 Sep 06 2023 21:10:04

%S 1,2,6,8,30,12,126,128,342,260,2046,1608,8190,4760,15840,32768,131070,

%T 80820,524286,493280,1165542,1391720,8388606,5769552,26910650,

%U 23153832,89478486,131849648,536870910,352845960,2147483646,2147483648

%N a(1) = 1; for n>1, sum of binomial(n,k) as k runs over RRS(n), the reduced residue system of n.

%C a(n) is a multiple of n for all n.

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

%H Laszlo Toth, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL14/Toth/toth9.html">Weighted gcd-sum functions</a>, J. Integer Sequences, 14 (2011), Article 11.7.7.

%F a(n) = Sum{binomial[n, k]; GCD[n, k]=1, 0<=k<=n}.

%F For n=prime, a(n)=2^n-2 because all k<=n except 0 and n are used.

%e For n=10, RRS[10]={1,3,7,9}, the corresponding coefficients are {10,120,120,10}, so the sum a(10)=260.

%p A056188 := proc(n)

%p     a := 0 ;

%p     for k from 1 to n do

%p         if igcd(k,n) = 1 then

%p             a := a+binomial(n,k);

%p         end if ;

%p     end do:

%p     a ;

%p end proc: # _R. J. Mathar_, Sep 02 2017

%t f[n_] := Plus @@ Binomial[n, Select[ Range[n], GCD[n, # ] == 1 &]]; Table[ f[n], {n, 33}] (* _Robert G. Wilson v_, Nov 04 2004 *)

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

%Y Cf. A056045, A056189.

%K nonn

%O 1,2

%A _Labos Elemer_, Aug 02 2000