cp's OEIS Frontend

We study words made of letters from an alphabet of size b, where b >= 1. We assume the letters are labeled {1,2,3,...,b}. There are b^n possible words of length n.

We say that a word is in "standard order" if it has the property that whenever a letter i appears, the letter i-1 has already appeared in the word. This implies that all words begin with the letter 1.

Let X be the random variable that assigns to each permutation of {1,2,...,b} (with uniform distribution) its number of fixed points (as in A008290). Then T(b,n) is the n-th moment about 0 of X, i.e., the expected value of X^n. - Geoffrey Critzer, Jun 23 2020

Table starts

....1.....1......1......1......1......1......1......1......1......1......1

....2.....2......2......2......2......2......2......2......2......2......2

....4.....5......5......5......5......5......5......5......5......5......5

....8....14.....15.....15.....15.....15.....15.....15.....15.....15.....15

...16....41.....51.....52.....52.....52.....52.....52.....52.....52.....52

...32...122....187....202....203....203....203....203....203....203....203

...64...365....715....855....876....877....877....877....877....877....877

..128..1094...2795...3845...4111...4139...4140...4140...4140...4140...4140

..256..3281..11051..18002..20648..21110..21146..21147..21147..21147..21147

..512..9842..43947..86472.109299.115179.115929.115974.115975.115975.115975

.1024.29525.175275.422005.601492.665479.677359.678514.678569.678570.678570

Lower left triangular part seems to be A102661. - R. J. Mathar, Nov 29 2015

From Danny Rorabaugh, Mar 03 2015: (Start)

a(n) is also the number of ways of placing n labeled balls into 11 indistinguishable boxes.

a(n) is also the number of word structures of length n using an 11-ary alphabet.

(End)

The smallest single-digit positive number is 1. This is the first type.

The smallest of the two-digit positive numbers with distinct digits is 10. This is the second type. The smallest of two-digit positive numbers with equal digits is 11. This is the third type, etc.

A digital type is an equivalence class of integers that share the same pattern of identical digits. a(n) defines a possible canonical form for this equivalence relation. It can be obtained from the distinct terms in A358497 after the following digit replacement: {1->1, 2->0, 3->2, 4->3, 5->4, 6->5, 7->6, 8->7, 9->8, 0->9}. - Dmytro Inosov, Nov 14 2024

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).

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 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).

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].

The sequence is related to A266991.

Sequence {A164864(n) - a(n)}_(n>=1) begins 0,0,1,4,1,26,1,175,365,1516,...

One can explain, why, for example, a(4)=11, instead of A164864(4)=15. There exist exactly 4 types of 4-digit numbers, which cannot be prime. In A266946 these types are: 1001, 1010, 1100, 1111. Indeed, numbers abba,aabb,aaaa are divisible by 11; a number abab is divisible by 101.

In other cases of n-digit types we should verify the divisibility of numbers of types in A266946 at least by primes of the form 11,101,... Besides, a digital type 1...1 exists only for n in A004023, i.e., for only 9 values of n from the first 270343. This simplifies the calculations.

a(n) <= A376918(n) with equality for n <= 9, but thereafter some digital types which pass the divisibility rules of A376918 don't in fact occur among the primes (see A377727). - Dmytro Inosov, Nov 05 2024

Based on the conjectured terms in A377727, the next three terms can be conjectured: a(14)=190402538; a(15)=1378294708; a(16)=10437142874. - Dmytro Inosov, Jan 07 2025

Digit patterns (or digital types) are as per A266946.

The divisibility rules are per A376918 and they act to exclude patterns which always result in composite numbers, just due to the pattern.

There are A376918(n) remaining patterns but not all of them actually contain primes, and a(n) is how many of them do not, so that a(n) = A376918(n) - A267013(n).

We call these digital types primonumerophobic and a(n) is the number of these of length n.

It is conjectured that the next terms are a(14)=362, a(15)=363, a(16)=1448. This is based on the calculated number of primonumerophobic digit patterns with only 2 or 3 distinct digits and the vanishingly small combinatorial probability for the existence of additional primonumerophobic digit patterns of this length with 4 or more distinct digits.

a(n) is the number of palindromic word structures of length n using 10-ary alphabet.

a(n) is the same as taking every element twice from A164864.