This site is supported by donations to The OEIS Foundation.

User:M. F. Hasler/A218556 and related sequences

From OeisWiki
Jump to: navigation, search

I was about to validate https://oeis.org/history/view?seq=A182092&v=8, a contribution (b-file) to A182092 = primes in A182040 = numbers with exactly three distinct decimal digits, one of which occurs once, one twice, and the third one three times, i.e.,

A182040 = 100012, 100021, ..., 999887.

I did not see at once why "3" was chosen, which seemed a bit arbitrary. I wrote my little PARI code to reproduce the sequence extended "to the left" (and to the right). Part of the investigations are summarized in my

COMMENT: This is the subsequence of A218556 consisting of terms with indices n = 254, ..., 39133. The number of terms is 38880 = A218566(10,3), the starting index is 254 = 1 + A218566(10,1) + A218566(10,2) + 1. — M. F. Hasler, Nov 02 2012

That is, the (good) reason why A182040 starts with 6 digit terms instead of 1 digit terms lies in the fact that 100012 would be preceded in the "complete" sequence (now A218556) by more than 250 terms with 1 or 3 digits, and therefore never appear.

OTOH, the (1+2 =) 3-digit terms 100, 101, 110, 112, ... are the first 243 terms of A210666 = near-repdigit numbers = numbers having all digits equal but one. (There, too, one could argue that 10,12,13,...,98 and maybe even 0,...,9 could be members.)

The new sequence

A218556 = numbers with d distinct decimal digits (d=1,...,10) such that for each k=1,...,d, some digit occurs exactly k times
= 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 100, 101, 110, 112, 113, 114, 115, 116, 117, 118, 119, 121, 122, 131,...

is obviously also finite and ends with 9999999999888888888777777776666666555555444443333222110 (ten "9"s, nine "8"s, ..., one "0").

I added this comment and proposed the sequence for publication, but then Charles R Greathouse IV suggested that the index of this last term should also be given.

(Un)fortunately I was too distracted to find the analytical formula at once, and it was not possible to guess the general pattern from the three initial terms 10 (or 9), 243, 38880, ...(?)....

I also had to realize that neither this sequence, neither padded to 9, _, 243, _, _, 38880, ..., neither the partial sums of these where in OEIS. I tried superseeker (for the first time in 10 years), which had as side effect some minor fixes to the OEIS servers done by David Applegate, but did not produce any exploitable (not even understandable) result.

To get some more hints on the formula, and for obvious other reasons of "systematic" approach, I decided to investigate the same problem for smaller bases. My hacked code gave the bref sequence

0, 1, 4, 5, 6    (= 0, 1, 100[2], 101[2], 110[2])    for base 2,

and the somewhat more exploitable (starting like A167819, apart from 3 initial terms)

0,1,2,9,10,12,14,16,17,18,20,22,23,24,25,248,...,714  =  0,1,2,100[3],101[3],110[3],112[3],...,222110[3] for base 3.

Neither the sequence of the largest terms: 0, 6, 714, ... (which is now A218559 -- to do: "written in base n"?), nor the sequence of "number of terms", 1, 5, 255, ..., (now 1 + row sums of A218566) were in OEIS.

Unfortunately, counting the d=4 term becomes impractical for n>5, and it is zero for n<4. So I had access only to the first three columns of A218566, with the initially mentioned 38880 = A218566(10,3) in the "lower right" corner. Up to n=7, this third column seemed to be of the form (n-1)^3*5*c(n) (with c=6,8,9,?,10), which looked as a generalization of the second column (n-1)^2*3 (viz (n-1)^col*(2*col-1)*something). However, this pattern breaks down at n=6 (a missing factor 5), and even the relaxed pattern (n-1)^3*d(n), d=30,40,45,48,50,? breaks down at n=8 (missing factor 7). Putting one factor of (n-1) into the "remaining factor", however, revealed a general factor 60(n-2).

The (n-1)(n-2) ~ C(n-1,k) was expected, given the way of constructing these numbers. Fortunately, the 2 smallest nonzero terms of column 4, A218566(4,4) = 226800 and A218566(5,4) = 1'209'600 were still "experimentally" available, and comfirmed the general pattern

A218566(n,k) = (n-1) C(n-1,k-1) (k-1)! v(k),
with v(k) = 1, 3, 60, 12600,... = A093883 = A203468 = Vandermonde permanent of the first n positive integers.

From there on, it was not hard to establish this firmly, via some basic combinatorial considerations.

Finally, this also gave the answer to the initial question of knowing N = #A218556, namely

N = #A218556 = 1 + sum_{i=1..10} A218566(10,i) = 9083370609101493843078695864582213215764827510991133.

As a sanity check, we notice that this is about 1/1000 of A218556(10) = 9999999999....222110, and also that the partial sums (+ 1 accounting for the initial 0) yield well the earlier noticed sequence 10, 253, 39133,... (number of terms with number of distinct digits d <= n).

The base 3 analog has been submitted as

A218560 = 0, 1, 2, 9, 10, 12, 14, 16, 17, 18, 20, 22, 23, 24, 25, 248, 250, 251, 254, 257, 258, 259, 262,...
= Numbers with d distinct ternary digits (d=1,2,3) such that for each k=1,...,d, some digit occurs exactly k times.

and the very bref base 2 version does not merit a separate sequence, but IMO the base 4 - base 9 analogs should be added, too; maybe for all of these also the version "written in base b".