OFFSET
1,5
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 n = 0 (mod 10) and k = 10, check in addition whether all 10 distinct digits occur an equal number of times in the pattern. In this case, the sum of digits is a multiple of 45, hence any number with that pattern is divisible by 9 and the pattern is excluded.
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].
LINKS
Dmytro Inosov, Table of n, a(n) for n = 1..99
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.
FORMULA
EXAMPLE
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, 39325; | 27641653
... (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.
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}],
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}];
CROSSREFS
KEYWORD
nonn,base,tabf,new
AUTHOR
Dmytro Inosov, Nov 18 2024
STATUS
approved