A077585 - OEIS

%I #64 Feb 16 2025 08:32:48

%S 0,1,7,127,32767,2147483647,9223372036854775807,

%T 170141183460469231731687303715884105727,

%U 57896044618658097711785492504343953926634992332820282019728792003956564819967

%N a(n) = 2^(2^n - 1) - 1.

%C a(2), a(3), a(5) and a(7) are prime; a(11) is not.

%C Let S be a set of n elements. First we perform a set partition on S. Let SU be the set of all nonempty subsets of S. As is well known, 2^n - 1 is the number of nonempty subsets of a set with n elements (see A000225). That is, 2^n - 1 is the number of elements |SU| of SU. In the second step, we select k elements from SU. We want to know how many different selections are possible. Let W be the resulting set of selections formed from SU. Then the number of elements |W| of W is |W| = Sum_{k=1..2^n-1} binomial(2^n-1,k) = 2^(2^n-1) - 1 = A077585. Example: |W(n)| = a(n=2) = 7, because W = {[[1, 2]], [[1]], [[1, 2], [1]], [[1, 2], [2], [1]], [[1, 2], [2]], [[2], [1]], [[2]]}. - _Thomas Wieder_, Nov 08 2007

%C These are so-called double Mersenne numbers, sometimes denoted MM(n) where M = A000225. MM(n) is prime iff M(n) = 2^n-1 is a Mersenne prime exponent (A000043), which isn't possible unless n itself is also in A000043. Primes of this form are called double Mersenne primes MM(p). For all Mersenne exponents between 7 and 61, factors of MM(p) are known. MM(61) is far too large for any currently known primality test, but a distributed search for factors of this and other MM(p) is ongoing, see the doublemersenne.org web site. - _M. F. Hasler_, Mar 05 2020

%C This is a strong divisibility sequence, that is, gcd(a(n),a(m)) = a(gcd(n,m)) for n, m >= 1. - _Peter Bala_, Dec 05 2022

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DoubleMersenneNumber.html">Double Mersenne Number</a>

%F a(n) = A000225(A000225(n)).

%F a(n) = A058891(n+1) - 1. - corrected by _Maurizio De Leo_, Feb 25 2015

%F a(n) = (A001146(n) - 2)/2.

%F a(n) = A056220(1+a(n-1)).

%F a(n) = Sum_{k=1..2^n-1} binomial(2^n-1,k). - _Thomas Wieder_, Nov 08 2007

%F a(n) = 2*a(n-1)^2 + 4*a(n-1) + 1. - _Roderick MacPhee_, Oct 05 2012

%e a(5) = 2^(2^5 - 1) - 1 = 2^31 - 1 = 2147483647.

%p a:= n-> 2^(2^n-1)-1:

%p seq(a(n), n=0..8); # _Thomas Wieder_, Nov 08 2007

%t 2^(2^Range[0, 9] - 1) - 1 (* _Vladimir Joseph Stephan Orlovsky_, Jun 22 2011 *)

%o (PARI) a(n)=if(n<1,0,-1+2*(1+a(n-1))^2)

%o (PARI) apply( {A077585(n)=1<<(1<<n-1)-1}, [0..9]) \\ _M. F. Hasler_, Mar 05 2020

%o (Python)

%o def A077585(n): return (1<<(1<<n)-1)-1 # _Chai Wah Wu_, Mar 14 2023

%Y Cf. A077586.

%Y Cf. A000225, A000043.

%K nonn,easy

%O 0,3

%A _Henry Bottomley_, Nov 07 2002

%E Corrected by _Lekraj Beedassy_, Jan 02 2007