cp's OEIS Frontend

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

%I A056188 #28 Sep 06 2023 21:10:04
%S A056188 1,2,6,8,30,12,126,128,342,260,2046,1608,8190,4760,15840,32768,131070,
%T A056188 80820,524286,493280,1165542,1391720,8388606,5769552,26910650,
%U A056188 23153832,89478486,131849648,536870910,352845960,2147483646,2147483648
%N A056188 a(1) = 1; for n>1, sum of binomial(n,k) as k runs over RRS(n), the reduced residue system of n.
%C A056188 a(n) is a multiple of n for all n.
%C A056188 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 A056188 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 A056188 a(n) = Sum{binomial[n, k]; GCD[n, k]=1, 0<=k<=n}.
%F A056188 For n=prime, a(n)=2^n-2 because all k<=n except 0 and n are used.
%e A056188 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 A056188 := proc(n)
%p A056188     a := 0 ;
%p A056188     for k from 1 to n do
%p A056188         if igcd(k,n) = 1 then
%p A056188             a := a+binomial(n,k);
%p A056188         end if ;
%p A056188     end do:
%p A056188     a ;
%p A056188 end proc: # _R. J. Mathar_, Sep 02 2017
%t A056188 f[n_] := Plus @@ Binomial[n, Select[ Range[n], GCD[n, # ] == 1 &]]; Table[ f[n], {n, 33}] (* _Robert G. Wilson v_, Nov 04 2004 *)
%o A056188 (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 A056188 Cf. A056045, A056189.
%K A056188 nonn
%O A056188 1,2
%A A056188 _Labos Elemer_, Aug 02 2000