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

%I #33 Feb 05 2022 16:43:50

%S 1,1,3,5,15,17,63,85,219,325,1023,1105,4095,5397,13515,21845,65535,

%T 70737,262143,333125,890523,1397077,4194303,4527185,16236015,22365525,

%U 57521883,88429845,268435455,272962625,1073741823,1431655765,3679302363,5726557525

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

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

%H Robert Israel, <a href="/A054432/b054432.txt">Table of n, a(n) for n = 1..2658</a>

%F 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

%F 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].

%F 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).

%F a(n-1) = Sum_{k=1..n, gcd(n, k) = 1} 2^(k-1). - _Vladeta Jovovic_, Aug 15 2002

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

%p 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;

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

%o (PARI) a(n) = sum(k=1, n, if (gcd(k,n)==1, 2^(k-1), 0)); \\ _Michel Marcus_, Jul 20 2014

%o (PARI) a(n) = subst(Polrev(vector(n, i, gcd(n, i)==1)), x, 2); \\ _Michel Marcus_, Jul 21 2014

%Y Cf. A054431, A054433, A001317, A054521.

%K nonn

%O 1,3

%A _Antti Karttunen_

%E Edited by _N. J. A. Sloane_, Jul 03 2008 at the suggestion of _R. J. Mathar_

%E More terms from _Michel Marcus_, Jul 20 2014