cp's OEIS Frontend

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

%I A376918 #119 Feb 09 2025 14:15:30
%S A376918 1,2,4,11,51,177,876,3965,20782,114462,678568,4160919,27640938,
%T A376918 190402900,1378295071,10437144322,82285618466,671415306221,
%U A376918 5676395537455
%N A376918 Number of digit patterns of length n without common prime factors of a different digital type.
%C A376918 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.
%C A376918 The number of remaining digit patterns not counted toward a(n) is given by A378199(n).
%C A376918 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.
%C A376918 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.
%C A376918 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.
%C A376918 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 A376918 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).
%C A376918 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.
%C A376918 a(n) coincides with A267013(n) for n<10 because the shortest primonumerophobic digit patterns "AAABBBAAAB", "AABABBBBBA", and "ABAAAAABBB" have length 10.
%C A376918 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.
%C A376918 A164864(n) gives the total number of possible digit patterns of length n and is therefore an upper bound for a(n).
%H A376918 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.
%F A376918 a(n) = Sum_{k=1..min(n,10)} T(n,k) -- row sums of A378154.
%F A376918 A267013(n) <= a(n) <= A164864(n).
%F A376918 a(n) = A164864(n) - A378199(n).
%F A376918 a(n) = A267013(n) + A377727(n).
%e A376918 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.
%e A376918 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.
%e A376918 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.
%e A376918 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.
%e A376918 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
%t A376918 MinLength = 1; MaxLength = 12; (* the range of n to calculate a(n) for *)
%t A376918 (* Function that calculates the canonical form A358497(n) *)
%t A376918 A358497[k_] := FromDigits@a358497C[k]
%t A376918 a358497C = Compile[{{k, _Integer}}, Module[{firstpos = ConstantArray[0, 10],
%t A376918   digits = IntegerDigits[k], indx = 0}, Table[If[firstpos[[digits[[j]] + 1]] == 0, firstpos[[digits[[j]] + 1]] = Mod[++indx,10]];
%t A376918   firstpos[[digits[[j]] + 1]], {j, Length[digits]}]]];
%t A376918 (* Function that checks if a common prime factor of a different digital type exists *)
%t A376918 DivisibilityRulesQ[pat_] := (
%t A376918   If[Divisible[Length[pat], 10] && Length[Counts[pat]] == 10 &&
%t A376918      AllTrue[Table[Counts[pat][[i]] == Length[pat]/10, {i, 1, 10}], TrueQ], Return[True]];
%t A376918   (# != 1) && AnyTrue[Extract[# // FactorInteger, {All, 1}],
%t A376918      A358497[#] != A358497[pat // FromDigits] &] &[
%t A376918      Apply[GCD, Total[10^(Position[Reverse[pat], #]-1) // Flatten]& /@
%t A376918      Mod[Range[CountDistinct[pat]], 10]]]
%t A376918 );
%t A376918 (* Function that generates all patterns that do not satisfy divisibility rules *)
%t A376918 Patterns[len_, k_] := (
%t A376918   Clear[dfs];
%t A376918   ResultingPatterns = {};
%t A376918   dfs[number_List] := If[Length[number] == len,
%t A376918     If[Length[Union[If[# < 10, #, 0] & /@ number]] == k,
%t A376918       AppendTo[ResultingPatterns, If[# < 10, #, 0] & /@ number]],
%t A376918     Do[If[i <= 10, dfs[Append[number, i]]], {i, Range[1, Last[Union[number]] + 1]}]];
%t A376918   dfs[{1}];
%t A376918   FromDigits /@ Select[ResultingPatterns, ! DivisibilityRulesQ[#] &]
%t A376918 );
%t A376918 (* Counting the patterns T(n,k) as per A378154 and their row sums a(n) *)
%t A376918 Do[Print[{n, #, Sum[#[[m]], {m, 1, Length[#]}]}] &[Table[Length[Patterns[n, j]], {j, 1, Min[10, n]}]], {n, MinLength, MaxLength}];
%Y A376918 Cf. A164864, A267013, A377727, A378154, A378199, A378761
%K A376918 nonn,base,more
%O A376918 1,2
%A A376918 _Dmytro Inosov_, Oct 10 2024
%E A376918 a(13)-a(19) from _Dmytro Inosov_, Dec 23 2024