|
|
A056188
|
|
a(1) = 1; for n>1, sum of binomial(n,k) as k runs over RRS(n), the reduced residue system of n.
|
|
8
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
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 ;
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|