login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A376918
Number of digit patterns of length n without common prime factors of a different digital type.
5
1, 2, 4, 11, 51, 177, 876, 3965, 20782, 114462, 678568, 4160919
OFFSET
1,2
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 = 0 (mod 10), check in addition whether the pattern has exactly 10 distinct digits that all 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 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).
LINKS
Dmytro S. Inosov and Emil Vlasák, Cryptarithmically unique terms in integer sequences, arXiv:2410.21427 [math.NT], 2024.
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).
EXAMPLE
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.
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}];
CROSSREFS
KEYWORD
nonn,base,more,changed
AUTHOR
Dmytro Inosov, Oct 10 2024
STATUS
approved