A054432 a(n) = Sum_{1<=k<=n, gcd(k,n)=1} 2^(k-1).

1, 1, 3, 5, 15, 17, 63, 85, 219, 325, 1023, 1105, 4095, 5397, 13515, 21845, 65535, 70737, 262143, 333125, 890523, 1397077, 4194303, 4527185, 16236015, 22365525, 57521883, 88429845, 268435455, 272962625, 1073741823, 1431655765, 3679302363, 5726557525

Offset

1,3

Comments

For n>0, numbers formed by interpreting the reduced residue set of n (the rows of triangle A054431) as binary numbers.

Links

Robert Israel, Table of n, a(n) for n = 1..2658

Formula

M * V, where M = A054521 is an infinite lower triangular matrix and V = [1, 2, 4, 8, ...] is a vector. - Gary W. Adamson, Jan 13 2007

a(4*n) = (2^(2*n) + 1)*a(2*n) [think how the reduced residue set of the numbers of the form 4n are formed].

For all primes p and integers e > 1, A054432(p^e) = A019320(p^e)*(((2^(p^(e-1)))-1)* ((2^(p-1))-1))/((2^p)-1).

a(n-1) = Sum_{k=1..n, gcd(n, k) = 1} 2^(k-1). - Vladeta Jovovic, Aug 15 2002

Example

For n=6 we have k = 1 and 5 and then 2^0 + 2^4 = 17 = a(6).

Maple

rrs2bincode := proc(n) local i, z; z := 0; for i from 1 to n-1 do z := z*2; if (1 = igcd(n, i)) then z := z + 1; fi; od; RETURN(z); end;

Mathematica

f[n_] := Sum[2^k, {k, Select[ Range@ n, GCD[#, n] == 1 &] - 1}]; Array[f, 35] (* Robert G. Wilson v, Jul 21 2014 *)

Prog

(PARI) a(n) = sum(k=1, n, if (gcd(k, n)==1, 2^(k-1), 0)); \\ Michel Marcus, Jul 20 2014
(PARI) a(n) = subst(Polrev(vector(n, i, gcd(n, i)==1)), x, 2); \\ Michel Marcus, Jul 21 2014

Crossrefs

Cf. A054431, A054433, A001317, A054521.

Sequence in context: A053576 A197818 A077406 * A016043 A077403 A002962

Adjacent sequences: A054429 A054430 A054431 * A054433 A054434 A054435

Keyword

nonn

Author

Antti Karttunen

Extensions

Edited by N. J. A. Sloane, Jul 03 2008 at the suggestion of R. J. Mathar

More terms from Michel Marcus, Jul 20 2014

Status

approved