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,2

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

Links

Table of n, a(n) for n=1..32.

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

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.

Example

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

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 *)

Prog

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

Crossrefs

Cf. A056045, A056189.

Sequence in context: A272614 A210737 A140539 * A020696 A328769 A290249

Adjacent sequences: A056185 A056186 A056187 * A056189 A056190 A056191

Keyword

nonn

Author

Labos Elemer, Aug 02 2000

Status

approved