A378154 Array read by rows: T(n,k) for k <= min(n,10) is the number of digital types of length n with exactly k distinct decimal digits without common prime factors of a different digital type.

1, 1, 1, 0, 3, 1, 0, 4, 6, 1, 0, 15, 25, 10, 1, 0, 12, 84, 65, 15, 1, 0, 63, 301, 350, 140, 21, 1, 0, 80, 868, 1672, 1050, 266, 28, 1, 0, 171, 2745, 7770, 6951, 2646, 462, 36, 1, 0, 370, 8680, 33505, 42405, 22827, 5880, 750, 45, 0, 0, 1023, 28501, 145750, 246730, 179487, 63987, 11880, 1155, 55

Offset: 1

Author

Dmytro Inosov, Nov 18 2024

Keywords

• nonn
• base
• tabf

Comments

T(n,k) is defined as the number of distinct digit patterns (or digital types, as per A266946) of length n with k distinct digits such that all integers of that digital type share no common prime factor of a different digital type (as per A376918). Terms with k > n are omitted as trivial zeros.

To check whether a digit pattern of length n with k distinct digits A,B,... should be counted toward T(n,k), write that pattern as a linear combination of the form X1*A + X2*B + ..., where the pattern coefficients X1,X2,... consist of 0's and 1's (A007088), with 1's on positions of the corresponding digit in the pattern.

If GCD(X1,X2,...) has no prime divisors with a different digit pattern from the one we started from, the pattern is counted toward T(n,k). Otherwise, it is excluded.

For k = 10, the sum of all distinct digits A + B + ... + J = 45, which is divisible by 9. Hence, patterns in which all 10 distinct digits from A to J have the same number of occurrences in the pattern modulo 3 are identically divisible by 3 and should be excluded. This has an effect on T(n,10) whenever n takes the form 10m + 3q (with m >= 1 and q >= 0).

The digital types excluded in this way result in composites for any values of the distinct digits in the pattern, without the need to run primality tests on all numbers of that digital type individually.

The requirement for a divisor of a different digital type only affects terms with k=1, i.e. repdigits AA..AA, and acts to include that pattern iff the n-repunit is prime (n in A004023).

T(n,k) gives an upper bound for the number of contributions to A267013(n) with exactly k distinct digits.

Stirling numbers of the second kind S2(n,k) (A008277) give the total number of possible digital types of length n with k distinct digits and are therefore an upper bound for T(n,k).

T(n,1)=1 either when n=1 or when n is a term in A004023 (indices of prime repunits); otherwise T(n,1)=0 because all the repdigits A*(10^n-1)/9 are simultaneously divisibly by any proper divisor of the repunit (10^n-1)/9.

T(n,2) is nonmonotonic because a larger number of digit patterns is excluded whenever n has a large number of nontrivial divisors (A070824), resulting in anomalously low values, for example, for n=12 or n=18. This is a consequence of divisibility rules that are formulated for prime divisors of 10^r-1 or 10^r+1 (where r divides n) in terms of the sum or alternating sum of r-digit blocks, respectively [see S. Shirali, First Steps in Number Theory: A Primer on Divisibility, Universities Press, 2019, pp. 42-49].

Examples

			T(n,k) as a table (omitting terms with k > n):
---------------------------------------------------------------------------------------------
 k:  1,    2,      3,       4,       5,       6,       7,       8,      9,    10; | Total,
 n |                                                                              | A376918(n)
---------------------------------------------------------------------------------------------
 1 | 1;                                                                           |        1
 2 | 1,    1;                                                                     |        2
 3 | 0,    3,      1;                                                             |        4
 4 | 0,    4,      6,       1;                                                    |       11
 5 | 0,   15,     25,      10,       1;                                           |       51
 6 | 0,   12,     84,      65,      15,       1;                                  |      177
 7 | 0,   63,    301,     350,     140,      21,       1;                         |      876
 8 | 0,   80,    868,    1672,    1050,     266,      28,       1;                |     3965
 9 | 0,  171,   2745,    7770,    6951,    2646,     462,      36,      1;        |    20782
10 | 0,  370,   8680,   33505,   42405,   22827,    5880,     750,     45,     0; |   114462
11 | 0, 1023,  28501,  145750,  246730,  179487,   63987,   11880,   1155,    55; |   678568
12 | 0,  912,  69792,  583438, 1373478, 1322896,  627396,  159027,  22275,  1705; |  4160919
13 | 0, 3965, 261495, 2532517, 7508501, 9321312, 5715424, 1899612, 359502, 38610; | 27640938
... (for more terms, see the A-file).
The pattern "ABCA" is counted toward T(4,3) because ABCA = A*1001 + B*100 + C*10. Since GCD(1001,100,10) = 1, integers of the digital type "ABCA" (1021 in A266946) share no common prime factors.
The pattern "AA" is counted toward T(2,1) because AA = A*11, and 11 is a prime repunit. The only common prime factor shared by the repdigits "AA" is 11, which is of the same digital type as the original pattern. Since no other patterns with n=2 and k=1 exist, T(2,1)=1.
The pattern "ABAB" is not counted toward T(4,2) because it is divisible by 101 for any A > 0 and B >= 0, and 101 has a different digital type from ABAB. Indeed, ABAB = A*1010+B*101, which is identically divisible by 101. Since there are two more patterns "ABBA" and "AABB" that are excluded due to divisibility by 11, T(4,1) = S2(4,2) - 3 = 4.
The pattern "ABCDEFGHIJ" that contains all possible digits exactly once does not contribute to T(10,10) because its sum of digits is 1+2+...+9 = 45, which is divisible by 9. Therefore, all integers with the digital type "ABCDEFGHIJ" share the common prime factor 3. Since no other patterns with n=k=10 exist, T(10,10)=0.
The pattern "ABCBDEFBGHIBJ" is not counted toward T(13,10) because its sum of digits is 3*B+45, which is divisible by 3. In total there are binomial(13,4) = 715 patterns of length 13 with all 10 distinct digits in which any 4 digits are equal, and since A378761(13,10) = 0, we obtain T(13,10) = S2(13,10) - 715.
		

Links

• Dmytro Inosov, Table of n, a(n) for n = 1..149
• Dmytro Inosov, Table of T(n,k), with missing terms
• Dmytro S. Inosov and Emil Vlasák, Cryptarithmically unique terms in integer sequences, arXiv:2410.21427 [math.NT], 2024.
• Math Stackexchange, A general formula for a tricky combinatorics problem

Crossrefs

Cf. A008277, A164864, A267013, A376918 (row sums), A377727, A378199, A378511, A378761

Programs

Mathematica

MinLength = 1; MaxLength = 10; (* the range of n to calculate T(n,k) for *)
(* Function that calculates the canonical form A358497(n) *)
A358497[k_] := FromDigits@a358497C[k]
a358497C = Compile[{{k, _Integer}}, Module[{firstpos = ConstantArray[0, 10],
  digits = IntegerDigits[k], indx = 0}, Table[If[firstpos[[digits[[j]] + 1]] == 0, firstpos[[digits[[j]] + 1]] = Mod[++indx, 10]]; firstpos[[digits[[j]] + 1]], {j, Length[digits]}]]];
(* Function that checks if a common prime factor of a different digital type exists *)
DivisibilityRulesQ[pat_] := (
  If[Divisible[Length[pat], 10] && Length[Counts[pat]] == 10 &&
     AllTrue[Table[Counts[pat][[i]] == Length[pat]/10, {i, 1, 10}], TrueQ], Return[True]];
  (# != 1) && AnyTrue[Extract[# // FactorInteger, {All, 1}],
     A358497[#] != A358497[pat // FromDigits] &] &[
     Apply[GCD, Total[10^(Position[Reverse[pat], #]-1) // Flatten]& /@
     Mod[Range[CountDistinct[pat]], 10]]]);
(* Function that generates all patterns that do not satisfy divisibility rules *)
Patterns[len_, k_] := (
  Clear[dfs];
  ResultingPatterns = {};
  dfs[number_List] := If[Length[number] == len,
    If[Length[Union[If[# < 10, #, 0] & /@ number]] == k,
      AppendTo[ResultingPatterns, If[# < 10, #, 0] & /@ number]],
    Do[If[i <= 10, dfs[Append[number, i]]], {i, Range[1, Last[Union[number]] + 1]}]];
  dfs[{1}];
  FromDigits /@ Select[ResultingPatterns, ! DivisibilityRulesQ[#] &]);
(* Counting the patterns T(n, k) and their sum, A376918(n) *)
Do[Print[{n, #, Sum[#[[m]], {m, 1, Length[#]}]}] &[Table[Length[Patterns[n, j]], {j, 1, Min[10, n]}]], {n, MinLength, MaxLength}];

Formula

Sum_{k=1..min(n,10)} T(n,k) = A376918(n) (row sums).

T(n+1,n) = A000217(n) for n <= 10.

T(n,2) = 2^(n-1) - A378511(n) for n > 1.

T(n,k) <= S2(n,k) -- k'th column of A008277.

T(n,k) = S2(n,k) - A378761(n,k) for 2 <= k <= 9.

T(n,k) = S2(n,k) for n/2 < k <= 9.

T(n,k) = S2(n,k) for 2 <= k <= 9 if A378511(n) = 1 (see A378761).

T(n,10) = S2(n,10) for n = 11, 12, 14, 15, 17, 18 -- the only integers >= 10 for which no representation n = 10m + 3q with m >= 1 and q >= 0 exists and A378761(n,10)=0.

T(13,10) = S2(13,10) - binomial(13,4).

T(16,10) = S2(16,10) - binomial(16,7) - binomial(16,4)*binomial(12,4)/2.

T(19,10) = S2(19,10) - binomial(19,10) - binomial(19,7)*binomial(12,4) - binomial(19,4)*binomial(15,4)*binomial(11,4)/6.

T(23,10) = S2(23,10) - binomial(23,5)*Product_{i=1..8}(2n+1) -- since A378761(23,10)=0.