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
Keywords
Examples
For n=6 we have k = 1 and 5 and then 2^0 + 2^4 = 17 = a(6).
Links
- Robert Israel, Table of n, a(n) for n = 1..2658
Programs
-
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 *) -
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
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
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
Comments