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,4

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).

Links

Dmytro Inosov, Table of n, a(n) for n = 2..95

Dmytro Inosov, Table of T(n,k), with missing terms

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).

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

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

Example

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.

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

Crossrefs

Cf. A002275, A004023, A378154, A378511, A378154

Sequence in context: A261318 A103879 A322706 * A051722 A357354 A166408

Adjacent sequences: A378758 A378759 A378760 * A378762 A378763 A378764

Keyword

nonn,base,tabf

Author

Dmytro Inosov, Dec 06 2024

Status

approved