This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A378154 #92 Jan 03 2025 23:28:26
%S A378154 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,
%T A378154 1,0,80,868,1672,1050,266,28,1,0,171,2745,7770,6951,2646,462,36,1,0,
%U A378154 370,8680,33505,42405,22827,5880,750,45,0,0,1023,28501,145750,246730,179487,63987,11880,1155,55
%N 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.
%C A378154 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.
%C A378154 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.
%C A378154 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.
%C A378154 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).
%C A378154 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.
%C A378154 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).
%C A378154 T(n,k) gives an upper bound for the number of contributions to A267013(n) with exactly k distinct digits.
%C A378154 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).
%C A378154 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.
%C A378154 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].
%H A378154 Dmytro Inosov, <a href="/A378154/b378154.txt">Table of n, a(n) for n = 1..149</a>
%H A378154 Dmytro Inosov, <a href="/A378154/a378154_10.txt">Table of T(n,k), with missing terms</a>
%H A378154 Dmytro S. Inosov and Emil Vlasák, <a href="https://arxiv.org/abs/2410.21427">Cryptarithmically unique terms in integer sequences</a>, arXiv:2410.21427 [math.NT], 2024.
%H A378154 Math Stackexchange, <a href="https://math.stackexchange.com/questions/5011458/a-general-formula-for-a-tricky-combinatorics-problem">A general formula for a tricky combinatorics problem</a>
%F A378154 Sum_{k=1..min(n,10)} T(n,k) = A376918(n) (row sums).
%F A378154 T(n+1,n) = A000217(n) for n <= 10.
%F A378154 T(n,2) = 2^(n-1) - A378511(n) for n > 1.
%F A378154 T(n,k) <= S2(n,k) -- k'th column of A008277.
%F A378154 T(n,k) = S2(n,k) - A378761(n,k) for 2 <= k <= 9.
%F A378154 T(n,k) = S2(n,k) for n/2 < k <= 9.
%F A378154 T(n,k) = S2(n,k) for 2 <= k <= 9 if A378511(n) = 1 (see A378761).
%F A378154 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.
%F A378154 T(13,10) = S2(13,10) - binomial(13,4).
%F A378154 T(16,10) = S2(16,10) - binomial(16,7) - binomial(16,4)*binomial(12,4)/2.
%F A378154 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.
%F A378154 T(23,10) = S2(23,10) - binomial(23,5)*Product_{i=1..8}(2n+1) -- since A378761(23,10)=0.
%e A378154 T(n,k) as a table (omitting terms with k > n):
%e A378154 ---------------------------------------------------------------------------------------------
%e A378154 k: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10; | Total,
%e A378154 n | | A376918(n)
%e A378154 ---------------------------------------------------------------------------------------------
%e A378154 1 | 1; | 1
%e A378154 2 | 1, 1; | 2
%e A378154 3 | 0, 3, 1; | 4
%e A378154 4 | 0, 4, 6, 1; | 11
%e A378154 5 | 0, 15, 25, 10, 1; | 51
%e A378154 6 | 0, 12, 84, 65, 15, 1; | 177
%e A378154 7 | 0, 63, 301, 350, 140, 21, 1; | 876
%e A378154 8 | 0, 80, 868, 1672, 1050, 266, 28, 1; | 3965
%e A378154 9 | 0, 171, 2745, 7770, 6951, 2646, 462, 36, 1; | 20782
%e A378154 10 | 0, 370, 8680, 33505, 42405, 22827, 5880, 750, 45, 0; | 114462
%e A378154 11 | 0, 1023, 28501, 145750, 246730, 179487, 63987, 11880, 1155, 55; | 678568
%e A378154 12 | 0, 912, 69792, 583438, 1373478, 1322896, 627396, 159027, 22275, 1705; | 4160919
%e A378154 13 | 0, 3965, 261495, 2532517, 7508501, 9321312, 5715424, 1899612, 359502, 38610; | 27640938
%e A378154 ... (for more terms, see the A-file).
%e A378154 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.
%e A378154 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.
%e A378154 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.
%e A378154 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.
%e A378154 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.
%t A378154 MinLength = 1; MaxLength = 10; (* the range of n to calculate T(n,k) for *)
%t A378154 (* Function that calculates the canonical form A358497(n) *)
%t A378154 A358497[k_] := FromDigits@a358497C[k]
%t A378154 a358497C = Compile[{{k, _Integer}}, Module[{firstpos = ConstantArray[0, 10],
%t A378154 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]}]]];
%t A378154 (* Function that checks if a common prime factor of a different digital type exists *)
%t A378154 DivisibilityRulesQ[pat_] := (
%t A378154 If[Divisible[Length[pat], 10] && Length[Counts[pat]] == 10 &&
%t A378154 AllTrue[Table[Counts[pat][[i]] == Length[pat]/10, {i, 1, 10}], TrueQ], Return[True]];
%t A378154 (# != 1) && AnyTrue[Extract[# // FactorInteger, {All, 1}],
%t A378154 A358497[#] != A358497[pat // FromDigits] &] &[
%t A378154 Apply[GCD, Total[10^(Position[Reverse[pat], #]-1) // Flatten]& /@
%t A378154 Mod[Range[CountDistinct[pat]], 10]]]);
%t A378154 (* Function that generates all patterns that do not satisfy divisibility rules *)
%t A378154 Patterns[len_, k_] := (
%t A378154 Clear[dfs];
%t A378154 ResultingPatterns = {};
%t A378154 dfs[number_List] := If[Length[number] == len,
%t A378154 If[Length[Union[If[# < 10, #, 0] & /@ number]] == k,
%t A378154 AppendTo[ResultingPatterns, If[# < 10, #, 0] & /@ number]],
%t A378154 Do[If[i <= 10, dfs[Append[number, i]]], {i, Range[1, Last[Union[number]] + 1]}]];
%t A378154 dfs[{1}];
%t A378154 FromDigits /@ Select[ResultingPatterns, ! DivisibilityRulesQ[#] &]);
%t A378154 (* Counting the patterns T(n, k) and their sum, A376918(n) *)
%t A378154 Do[Print[{n, #, Sum[#[[m]], {m, 1, Length[#]}]}] &[Table[Length[Patterns[n, j]], {j, 1, Min[10, n]}]], {n, MinLength, MaxLength}];
%Y A378154 Cf. A008277, A164864, A267013, A376918 (row sums), A377727, A378199, A378511, A378761
%K A378154 nonn,base,tabf
%O A378154 1,5
%A A378154 _Dmytro Inosov_, Nov 18 2024