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

1, 2, 6, 8, 30, 12, 126, 128, 342, 260, 2046, 1608, 8190, 4760, 15840, 32768, 131070, 80820, 524286, 493280, 1165542, 1391720, 8388606, 5769552, 26910650, 23153832, 89478486, 131849648, 536870910, 352845960, 2147483646, 2147483648

Offset: 1

Author

Labos Elemer, Aug 02 2000

Keywords

• nonn

Comments

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

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

Examples

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

Links

• Laszlo Toth, Weighted gcd-sum functions, J. Integer Sequences, 14 (2011), Article 11.7.7.

Crossrefs

Cf. A056045, A056189.

Programs

Maple

A056188 := proc(n)
    a := 0 ;
    for k from 1 to n do
        if igcd(k,n) = 1 then
            a := a+binomial(n,k);
        end if ;
    end do:
    a ;
end proc: # R. J. Mathar, Sep 02 2017

Mathematica

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

PARI

a(n) = if (n==1, 1, sum(k=0, n, if (gcd(n,k) == 1, binomial(n,k)))); \\ Michel Marcus, Mar 22 2020

Formula

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

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