OFFSET
1,4
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.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 250 terms from Dmytro Inosov)
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) = 2^(n - 1) - phi(2^n - 1)/2 for n > 1. (End)
EXAMPLE
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.
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}]
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Dmytro Inosov, Nov 29 2024
EXTENSIONS
a(32)-a(38) from Alois P. Heinz, Nov 29 2024
STATUS
approved