A376918 Number of digit patterns of length n without common prime factors of a different digital type.

1, 2, 4, 11, 51, 177, 876, 3965, 20782, 114462, 678568, 4160919, 27640938, 190402900, 1378295071, 10437144322, 82285618466, 671415306221, 5676395537455

Offset: 1

Author

Dmytro Inosov, Oct 10 2024

Keywords

• nonn
• base
• more

Comments

a(n) gives the number of distinct digit patterns (or digital types, as per A266946) such that all integers of that digital type share no common prime factor of a different digital type.

The number of remaining digit patterns not counted toward a(n) is given by A378199(n).

To check whether a digit pattern of length n with distinct digits A,B,... should be counted toward a(n), 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 a(n). Otherwise, it is excluded.

For n of the form 10m + 3q (with m >= 1 and q >= 0), check in addition if the pattern contains all 10 distinct digits whose number of occurrences taken modulo 3 is the same for all digits from A to J. Since A + B + ... + J = 45, which is divisible by 9, such patterns are not counted toward a(n) and should be 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 reprigits of the form AA..AA and acts to include that pattern iff the n-repunit is prime (n in A004023).

a(n) gives the upper bound for the number of distinct digital types of n-digit primes A267013(n). The two sequences are distinct, since some digit patterns such as "AAABBCABCCCAACCB" happen to contain no primes accidentally, without having a common divisor. We call such patterns primonumerophobic. Sequence A377727 = {a(n)-A267013(n)}_(n>=1) gives the number of primonumerophobic digit patterns of length n.

a(n) coincides with A267013(n) for n<10 because the shortest primonumerophobic digit patterns "AAABBBAAAB", "AABABBBBBA", and "ABAAAAABBB" have length 10.

a(n) represents row sums of T(n,k) in A378154 -- an array of contributions to a(n) with exactly k<=10 distinct decimal digits.

A164864(n) gives the total number of possible digit patterns of length n and is therefore an upper bound for a(n).

Examples

			The pattern "ABCA" is counted toward a(4) 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 a(2) 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.
The pattern "ABAB" is not counted toward a(4) 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. In total there are four 4-digit patterns that are excluded: ABBA, AABB, AAAA (all of them divisible by 11) and ABAB (divisible by 101). Therefore, a(4) = A164864(4)-4 = 11.
The pattern "ABCDEFGHIJ" that contains all possible digits exactly once does not contribute to a(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.
a(23) = 37135226382208300 -- the fact that n = 23 is a term in A004023 (indices of prime repunits) simplifies the calculation of A378154(n,k) since A378761(23,k) = 0 for all k > 1. - _Dmytro Inosov_, Dec 21 2024
		

Links

• Dmytro S. Inosov and Emil Vlasák, Cryptarithmically unique terms in integer sequences, arXiv:2410.21427 [math.NT], 2024.

Crossrefs

Cf. A164864, A267013, A377727, A378154, A378199, A378761

Programs

Mathematica

MinLength = 1; MaxLength = 12; (* the range of n to calculate a(n) 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) as per A378154 and their row sums a(n) *)
Do[Print[{n, #, Sum[#[[m]], {m, 1, Length[#]}]}] &[Table[Length[Patterns[n, j]], {j, 1, Min[10, n]}]], {n, MinLength, MaxLength}];

Formula

a(n) = Sum_{k=1..min(n,10)} T(n,k) -- row sums of A378154.

A267013(n) <= a(n) <= A164864(n).

a(n) = A164864(n) - A378199(n).

a(n) = A267013(n) + A377727(n).

Extensions

a(13)-a(19) from Dmytro Inosov, Dec 23 2024