A378761 Irregular triangle read by rows: T(n,k) for k <= n/2 is the number of partitions of the repunit A002275(n) into k nonzero complementary binary vectors having a common divisor > 1 in base 10.

1, 1, 1, 3, 1, 0, 1, 19, 6, 1, 0, 0, 1, 47, 98, 29, 1, 84, 280, 0, 1, 141, 650, 600, 120, 1, 0, 0, 0, 0, 1, 1135, 16734, 28063, 5922, 756, 1, 130, 130, 13, 0, 0, 1, 1779, 43757, 161700, 161700, 52920, 5040, 1, 6183, 263386, 1401900, 1401400, 0, 0, 1, 9919, 438582, 2634549, 4381246, 2587326, 577612, 40913, 1, 0, 0, 0, 0, 0, 0, 0, 1, 75433

Offset: 2

Author

Dmytro Inosov, Dec 06 2024

Keywords

• nonn
• base
• tabf

Comments

We call a k-tuple of binary vectors of length n complementary if for every position m (1 <= m <= n) the digit "1" occurs on that position in exactly one of the vectors. For example, {1010, 0100, 0001} is a triple (k=3) of complementary binary vectors of length n=4. The sum of complementary binary vectors of length n is always a repunit of the same length, A002275(n).

T(n,k) gives the number of distinct unordered k-tuples of complementary binary vectors of length n that have a common divisor > 1 as integers in base 10.

For k > n/2, at least one of the binary vectors must contain just a single "1" (with all other digits zero) and is, therefore, a power of 10 (A011557). Hence it cannot have nontrivial common divisors with the repunit A002275(n), which implies T(n,k) = 0. The requirement k <= n/2 acts to skip the corresponding trivial zero terms.

The partitions for k = 1 are trivial and consist of one element -- the repunit itself, which is its own greatest common divisor. Therefore, T(n,1) = 1 for n >= 2.

If T(n,k)=0 for some n and k, then T(n,m)=0 also for any m >= k. Indeed, if some m-tuple of binary vectors existed that is counted toward T(n,m), then an (m-1)-tuple obtained by summing any two of its vectors while leaving others unchanged would be counted toward T(n,m-1). By induction, this leads to T(n,k)>0, which is a contradiction.

Consequently, T(n,k) = 0 for all k > 1 whenever A378511(n) = 1. This holds, in particular, for all n in A004023 (indices of prime repunits).

Examples

			The triangle T(n,k) starts (omitting terms with k > n/2, which are zero):
-----------------------------------------------------------------------------------------
n\k: 1,       2,         3,         4,         5,         6,        7,       8,   9,  ...
-----------------------------------------------------------------------------------------
 2 | 1;
 3 | 1;
 4 | 1,       3;
 5 | 1,       0;
 6 | 1,      19,         6;
 7 | 1,       0,         0;
 8 | 1,      47,        98,        29;
 9 | 1,      84,       280,         0;
10 | 1,     141,       650,       600,       120;
11 | 1,       0,         0,         0,         0;
12 | 1,    1135,     16734,     28063,      5922,       756;
13 | 1,     130,       130,        13,         0,         0;
14 | 1,    1779,     43757,    161700,    161700,     52920,     5040;
15 | 1,    6183,    263386,   1401900,   1401400,         0,        0;
16 | 1,    9919,    438582,   2634549,   4381246,   2587326,   577612,   40913;
17 | 1,       0,         0,         0,         0,         0,        0,       0;
18 | 1,   75433,  10808037, 140403209, 391178517, 290493433, 39663279, 6540609, 362880;
19 | 1,       0,         0,         0,         0,         0,        0,       0,      0;
20 | 1,  124467,  26825456, 514583021, ...
... (for more terms, see the A-file).
T(6,3) = 6 because among the {n,k} = 90 possible triples of nonzero binary vectors of length 6 there are exactly 6 with a common divisor > 1:
  {100001, 010010, 001100}: GCD(100001, 10010, 1100) = 11;
  {100001, 011000, 000110}: GCD(100001, 11000, 110) = 11;
  {100100, 010010, 001001}: GCD(100100, 10010, 1001) = 1001;
  {100100, 011000, 000011}: GCD(100100, 11000, 11) = 11;
  {110000, 001001, 000110}: GCD(110000, 1001, 110) = 11;
  {110000, 001100, 000011}: GCD(110000, 1100, 11) = 11.
The quadruple of binary vectors {1100000001000, 0010001100000, 0001100000001, 0000010010110} counts toward T(13,4) because in base 10, GCD(1100000001000, 10001100000, 1100000001, 10010110) = 53. In total, there are 13 such quadruples of length 13. This exemplifies the smallest prime n with nontrivial T(n,k).
T(17,k) = 0 for k >= 2 since A378511(17) = 1 (though 17 isn't a term in A004023).
T(317,k) = 0 for k >= 2 since 317 is a term in A004023.
		

Links

• Dmytro Inosov, Table of n, a(n) for n = 2..95
• Dmytro Inosov, Table of T(n,k), with missing terms and row sums

Crossrefs

Cf. A002275, A004023, A378154, A378511, A378154, A385539 (row sums).

Programs

Mathematica

Clear[SubListNonCoprimes];
SubListNonCoprimes[bnum_, m_] := SubListNonCoprimes[bnum, m] =
  (If[m == 1, Return[If[bnum == Repunit, Nothing, {Repunit - bnum}]]];
  ListOfParts2 = Select[Total[10^(ResourceFunction["KSetPartitions"][(#)[[Range[Length[#]]]], 2] &[Position[IntegerDigits[bnum] // Reverse, 0] // Flatten] - 1), {3}] /. 0 -> {}, GCD @@ Prepend[#, bnum] > 1 &];
  If[m == 2, ListOfParts2, Select[Flatten[MapApply[Append]@*Thread@*
Comap[{SubListNonCoprimes[# + bnum, m-1] &, Identity}] @* Max /@ ListOfParts2, 1], GCD @@ Prepend[#, bnum] > 1 &]]);
SubCountNonCoprimes10[n_, m_, k_, totk_] := (Result = 0; Do[If[!CoprimeQ[#, Repunit-#],
Result += Length[SubListNonCoprimes[#, m-1]]] &[FromDigits[IntegerDigits[i, 2]]], {i, #[[k]], #[[k+1]]-1}] &[Round[Subdivide[2^(n-1), 2^n, totk]]];
  Result);
CountNonCoprimes10[n_, m_] := (If[m > n/2, Return[0], If[m == 1, Return[1]]];
  Repunit = (10^n - 1)/9; ParallelSum[SubCountNonCoprimes10[n, m, k, #], {k, #}, Method -> "FinestGrained", ProgressReporting -> (n >= 15)] &[If[n >= 15, 100, 1] $KernelCount]);
Table[CountNonCoprimes10[n, k], {n, 2, 16}, {k, 1, 8}] // TableForm

Formula

T(n,k) = 0 for k > n/2 (such terms are skipped as trivial zeros).

T(n,1) = 1 for n >= 2.

T(n,1) + T(n,2) = A378511(n).

Sum_{k} T(n,k) = A385539(n) (row sums).

T(n,k) = Stirling2(n,k) - A378154(n,k) for 2 <= k <= 9.

T(A004023(n),k) = 0 for k >= 2.