cp's OEIS Frontend

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

%I A378514 #52 Nov 30 2024 08:50:40
%S A378514 0,1,1,4,1,14,1,64,40,212,56,1184,1,2900,2884,16384,1,61088,1,284288,
%T A378514 159520,776800,89264,5070848,577216,11195732,10375168,67834880,
%U A378514 1522240,269570912,1,1073741824,813199072,2863486292,917553184,21299044352,308159200,45813683540
%N A378514 Number of partitions of 2^n-1 into two summands >= 0 having a common divisor > 1.
%C A378514 a(n) counts binary numbers (A007088) of length n that are not coprime with their bitwise inverse as integers in base 2.
%C A378514 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.
%C A378514 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.
%C A378514 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.
%H A378514 Alois P. Heinz, <a href="/A378514/b378514.txt">Table of n, a(n) for n = 1..1000</a> (first 250 terms from Dmytro Inosov)
%F A378514 a(n) <= A000325(n-1) = 2^(n-1) - n + 1;
%F A378514 a(A000043(n)) = 1;
%F A378514 From _Alois P. Heinz_, Nov 29 2024: (Start)
%F A378514 a(n) = A082023(2^n-1) + signum(n-1).
%F A378514 a(n) = ceiling((2^n-1 - phi(2^n-1))/2). (End)
%F A378514 From _Peter Luschny_, Nov 30 2024: (Start)
%F A378514 a(n) = A000079(n-1) - A056742(n) for n > 1.
%F A378514 a(n) = 2^(n - 1) - phi(2^n - 1)/2 for n > 1. (End)
%e A378514 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.
%e A378514 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:
%e A378514 ----------------------------------------------
%e A378514 partition   binary vectors       GCD
%e A378514 (base 10)      (base 2)
%e A378514 ----------------------------------------------
%e A378514 15 = 8 + 7   {1000, 0111}   GCD(8, 7) = 1;
%e A378514 15 = 9 + 6   {1001, 0110}   GCD(9, 6) = 3;
%e A378514 15 = 10 + 5  {1010, 0110}   GCD(10, 5) = 5;
%e A378514 15 = 11 + 4  {1011, 0100}   GCD(11, 4) = 1;
%e A378514 15 = 12 + 3  {1100, 0011}   GCD(12, 3) = 3;
%e A378514 15 = 13 + 2  {1101, 0010}   GCD(13, 2) = 1;
%e A378514 15 = 14 + 1  {1110, 0001}   GCD(14, 1) = 1;
%e A378514 15 = 15 + 0  {1111, 0000}   GCD(15, 0) = 15.
%e A378514 ----------------------------------------------
%e A378514 a(7) = 1 because 7 is a term in A000043.
%p A378514 a:= n-> (m-> ceil((m-numtheory[phi](m))/2))(2^n-1):
%p A378514 seq(a(n), n=1..38);  # _Alois P. Heinz_, Nov 29 2024
%t A378514 CountNonCoprimes2[i_] := Table[If[!CoprimeQ @@ #, #, ##&[]] &[{n, 2^i-1-n}], {n, 2^(i-1), 2^i-1}] // Length; Table[CountNonCoprimes2[i], {i, 25}]
%t A378514 (* Version that uses the built-in EulerPhi[] function *)
%t A378514 Table[Ceiling[(# - EulerPhi[#])/2] &[2^m-1], {m, 100}]
%o A378514 (SageMath)
%o A378514 def a(n): return 2^(n-1) - euler_phi(2^n-1) / 2 if n > 1 else 0
%o A378514 print([a(n) for n in range(1, 39)])  # _Peter Luschny_, Nov 29 2024
%Y A378514 Cf. A000010, A000043, A000079, A000225, A000668, A056742, A082023, A378511.
%K A378514 nonn
%O A378514 1,4
%A A378514 _Dmytro Inosov_, Nov 29 2024
%E A378514 a(32)-a(38) from _Alois P. Heinz_, Nov 29 2024