cp's OEIS Frontend

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.

%I A378761 #59 Jul 03 2025 09:29:42
%S A378761 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,
%T A378761 0,0,0,1,1135,16734,28063,5922,756,1,130,130,13,0,0,1,1779,43757,
%U A378761 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
%N 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.
%C A378761 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).
%C A378761 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.
%C A378761 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.
%C A378761 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.
%C A378761 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.
%C A378761 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).
%H A378761 Dmytro Inosov, <a href="/A378761/b378761.txt">Table of n, a(n) for n = 2..95</a>
%H A378761 Dmytro Inosov, <a href="/A378761/a378761_5.txt">Table of T(n,k), with missing terms and row sums</a>
%F A378761 T(n,k) = 0 for k > n/2 (such terms are skipped as trivial zeros).
%F A378761 T(n,1) = 1 for n >= 2.
%F A378761 T(n,1) + T(n,2) = A378511(n).
%F A378761 Sum_{k} T(n,k) = A385539(n) (row sums).
%F A378761 T(n,k) = Stirling2(n,k) - A378154(n,k) for 2 <= k <= 9.
%F A378761 T(A004023(n),k) = 0 for k >= 2.
%e A378761 The triangle T(n,k) starts (omitting terms with k > n/2, which are zero):
%e A378761 -----------------------------------------------------------------------------------------
%e A378761 n\k: 1,       2,         3,         4,         5,         6,        7,       8,   9,  ...
%e A378761 -----------------------------------------------------------------------------------------
%e A378761  2 | 1;
%e A378761  3 | 1;
%e A378761  4 | 1,       3;
%e A378761  5 | 1,       0;
%e A378761  6 | 1,      19,         6;
%e A378761  7 | 1,       0,         0;
%e A378761  8 | 1,      47,        98,        29;
%e A378761  9 | 1,      84,       280,         0;
%e A378761 10 | 1,     141,       650,       600,       120;
%e A378761 11 | 1,       0,         0,         0,         0;
%e A378761 12 | 1,    1135,     16734,     28063,      5922,       756;
%e A378761 13 | 1,     130,       130,        13,         0,         0;
%e A378761 14 | 1,    1779,     43757,    161700,    161700,     52920,     5040;
%e A378761 15 | 1,    6183,    263386,   1401900,   1401400,         0,        0;
%e A378761 16 | 1,    9919,    438582,   2634549,   4381246,   2587326,   577612,   40913;
%e A378761 17 | 1,       0,         0,         0,         0,         0,        0,       0;
%e A378761 18 | 1,   75433,  10808037, 140403209, 391178517, 290493433, 39663279, 6540609, 362880;
%e A378761 19 | 1,       0,         0,         0,         0,         0,        0,       0,      0;
%e A378761 20 | 1,  124467,  26825456, 514583021, ...
%e A378761 ... (for more terms, see the A-file).
%e A378761 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:
%e A378761   {100001, 010010, 001100}: GCD(100001, 10010, 1100) = 11;
%e A378761   {100001, 011000, 000110}: GCD(100001, 11000, 110) = 11;
%e A378761   {100100, 010010, 001001}: GCD(100100, 10010, 1001) = 1001;
%e A378761   {100100, 011000, 000011}: GCD(100100, 11000, 11) = 11;
%e A378761   {110000, 001001, 000110}: GCD(110000, 1001, 110) = 11;
%e A378761   {110000, 001100, 000011}: GCD(110000, 1100, 11) = 11.
%e A378761 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).
%e A378761 T(17,k) = 0 for k >= 2 since A378511(17) = 1 (though 17 isn't a term in A004023).
%e A378761 T(317,k) = 0 for k >= 2 since 317 is a term in A004023.
%t A378761 Clear[SubListNonCoprimes];
%t A378761 SubListNonCoprimes[bnum_, m_] := SubListNonCoprimes[bnum, m] =
%t A378761   (If[m == 1, Return[If[bnum == Repunit, Nothing, {Repunit - bnum}]]];
%t A378761   ListOfParts2 = Select[Total[10^(ResourceFunction["KSetPartitions"][(#)[[Range[Length[#]]]], 2] &[Position[IntegerDigits[bnum] // Reverse, 0] // Flatten] - 1), {3}] /. 0 -> {}, GCD @@ Prepend[#, bnum] > 1 &];
%t A378761   If[m == 2, ListOfParts2, Select[Flatten[MapApply[Append]@*Thread@*
%t A378761 Comap[{SubListNonCoprimes[# + bnum, m-1] &, Identity}] @* Max /@ ListOfParts2, 1], GCD @@ Prepend[#, bnum] > 1 &]]);
%t A378761 SubCountNonCoprimes10[n_, m_, k_, totk_] := (Result = 0; Do[If[!CoprimeQ[#, Repunit-#],
%t A378761 Result += Length[SubListNonCoprimes[#, m-1]]] &[FromDigits[IntegerDigits[i, 2]]], {i, #[[k]], #[[k+1]]-1}] &[Round[Subdivide[2^(n-1), 2^n, totk]]];
%t A378761   Result);
%t A378761 CountNonCoprimes10[n_, m_] := (If[m > n/2, Return[0], If[m == 1, Return[1]]];
%t A378761   Repunit = (10^n - 1)/9; ParallelSum[SubCountNonCoprimes10[n, m, k, #], {k, #}, Method -> "FinestGrained", ProgressReporting -> (n >= 15)] &[If[n >= 15, 100, 1] $KernelCount]);
%t A378761 Table[CountNonCoprimes10[n, k], {n, 2, 16}, {k, 1, 8}] // TableForm
%Y A378761 Cf. A002275, A004023, A378154, A378511, A378154, A385539 (row sums).
%K A378761 nonn,base,tabf
%O A378761 2,4
%A A378761 _Dmytro Inosov_, Dec 06 2024