A378514 Number of partitions of 2^n-1 into two summands >= 0 having a common divisor > 1.

0, 1, 1, 4, 1, 14, 1, 64, 40, 212, 56, 1184, 1, 2900, 2884, 16384, 1, 61088, 1, 284288, 159520, 776800, 89264, 5070848, 577216, 11195732, 10375168, 67834880, 1522240, 269570912, 1, 1073741824, 813199072, 2863486292, 917553184, 21299044352, 308159200, 45813683540

Offset: 1

Author

Dmytro Inosov, Nov 29 2024

Keywords

• nonn

Comments

a(n) counts binary numbers (A007088) of length n that are not coprime with their bitwise inverse as integers in base 2.

Equivalently, m from A007088 is counted toward a(A055642(m)) iff GCD(m, A002275(A055642(m)) - m) > 1, assuming base 2 in the calculation of GCD. Therefore a(n) is the base-2 analog of A378511.

For any n > 1, a(n) > 0 because the trivial partition A002275(n) = A002275(n) + 0 always counts toward a(n): GCD(A002275(n), 0) = A002275(n) > 1.

a(n) = 1 iff n is a Mersenne exponent (A000043). Indeed, if a partition 2^n-1 = k + m exists with GCD(k, m) = q > 1, then 2^n-1 itself is divisible by q. Whenever 2^n-1 is a Mersenne prime (A000668), this is only possible for q = 2^n-1, therefore the only such partition is the trivial one, {2^n-1, 0}. The inverse is also true. If n is not a Mersenne exponent, 2^n-1 has a nontrivial divisor q, and the partition 2^n-1 = q + (2^n-1-q) counts toward a(n) because GCD(q, 2^n-1-q) = q > 1. Therefore, a(n) > 1.

Examples

			a(2) = 1 because there are only 2 possible partitions of 2^2-1 = 3 into a sum of two nonnegative integers, namely: 3 = 3 + 0 and 3 = 2 + 1. The partition {3, 0} counts toward a(2) since GCD(3,0) = 3 > 1. The partition {2, 1} does not count since GCD(2,1) = 1.
a(4) = 4 because among the 8 possible partitions of 2^4-1 = 15 into a sum of two nonnegative integers, the summands are non-coprime in exactly 4 cases:
----------------------------------------------
partition   binary vectors       GCD
(base 10)      (base 2)
----------------------------------------------
15 = 8 + 7   {1000, 0111}   GCD(8, 7) = 1;
15 = 9 + 6   {1001, 0110}   GCD(9, 6) = 3;
15 = 10 + 5  {1010, 0110}   GCD(10, 5) = 5;
15 = 11 + 4  {1011, 0100}   GCD(11, 4) = 1;
15 = 12 + 3  {1100, 0011}   GCD(12, 3) = 3;
15 = 13 + 2  {1101, 0010}   GCD(13, 2) = 1;
15 = 14 + 1  {1110, 0001}   GCD(14, 1) = 1;
15 = 15 + 0  {1111, 0000}   GCD(15, 0) = 15.
----------------------------------------------
a(7) = 1 because 7 is a term in A000043.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 250 terms from Dmytro Inosov)

Crossrefs

Cf. A000010, A000043, A000079, A000225, A000668, A056742, A082023, A378511.

Programs

Maple

a:= n-> (m-> ceil((m-numtheory[phi](m))/2))(2^n-1):
seq(a(n), n=1..38);  # Alois P. Heinz, Nov 29 2024

Mathematica

CountNonCoprimes2[i_] := Table[If[!CoprimeQ @@ #, #, ##&[]] &[{n, 2^i-1-n}], {n, 2^(i-1), 2^i-1}] // Length; Table[CountNonCoprimes2[i], {i, 25}]
(* Version that uses the built-in EulerPhi[] function *)
Table[Ceiling[(# - EulerPhi[#])/2] &[2^m-1], {m, 100}]

SageMath

def a(n): return 2^(n-1) - euler_phi(2^n-1) / 2 if n > 1 else 0
print([a(n) for n in range(1, 39)])  # Peter Luschny, Nov 29 2024

Formula

a(n) <= A000325(n-1) = 2^(n-1) - n + 1;

a(A000043(n)) = 1;

From Alois P. Heinz, Nov 29 2024: (Start)

a(n) = A082023(2^n-1) + signum(n-1).

a(n) = ceiling((2^n-1 - phi(2^n-1))/2). (End)

From Peter Luschny, Nov 30 2024: (Start)

a(n) = A000079(n-1) - A056742(n) for n > 1.

a(n) = 2^(n - 1) - phi(2^n - 1)/2 for n > 1. (End)

Extensions

a(32)-a(38) from Alois P. Heinz, Nov 29 2024