Puzzle 324. Self-descriptive numbers

Problems & Puzzles: Puzzles

Puzzle 324. Self-descriptive numbers

To G. L. Honaker, Jr. & Michelle, for their recent marriage.
I know at least three kind of numbers that can be named as 'self-descriptive'.
On of these numbers (the self-inventoried numbers) were already studied in the puzzle 207 of my pages.
One more is defined in this article from the Eric Weisstein's Mathworld Encyclopedia.
In this puzzle we will deal with a definition that - according to G. L. Honaker, Jr., goes back to 'Numbers Count' by Mudge, Personal Computer World, June 1996
Let's introduce these numbers through an example:

The number 15333110 is said to be self-descriptive because it can be 'read' as follows: "one 5, three 3, three 1, one 0", which correspond exactly to the quantification of the digits in 15333110.

In order to avoid some dispersion in the idea behind this kind of numbers, we will state that every self-descriptive must have an even quantity of digits because the first digit act as a quantifier of his right-neighbor, the third one act as as a quantifier of his right-neighbor, and so on. We will also suppose that all numbers considered in this puzzle are base 10.
Questions:
1. Calculate the total quantity of self-descriptive numbers.
2. Compute the largest self-descriptive number.
3. Compute the largest self-descriptive prime number.

Contributions came from Giovanni Resta, Patrick Capelle & Anurag Sahay:

Giovanni wrote:

I assumed that each digit is "described" at most one time, i.e., I have excluded cases in which there are repeated pairs quantifier-digit.

Clearly, since the order of the description is not relevant, each solution made of n pairs belongs to a family of n! equivalent solutions.

Here is what I found. All in all there are 99 "basic" solutions:

There is 1 lenght 2*1 solution:
22

There are 35 length 2*4 solutions:
10213223 10311233 10313314 10313315 10313316 10313317
10313318 10313319 21322314 21322315 21322316 21322317
21322318 21322319 31123314 31123315 31123316 31123317
31123318 31123319 31331415 31331416 31331417 31331418
31331419 31331516 31331517 31331518 31331519 31331617
31331618 31331619 31331718 31331719 31331819

There are 21 length 2*5 solutions:
1031223314 1031223315 1031223316 1031223317 1031223318
1031223319 3122331415 3122331416 3122331417 3122331418
3122331419 3122331516 3122331517 3122331518 3122331519
3122331617 3122331618 3122331619 3122331718 3122331719
3122331819

There are 20 length 2*7 solutions:
10413223241516 10413223241517 10413223241518 10413223241519
10413223241617 10413223241618 10413223241619 10413223241718
10413223241719 10413223241819 41322324151617 41322324151618
41322324151619 41322324151718 41322324151719 41322324151819
41322324161718 41322324161719 41322324161819 41322324171819

There are 15 length 2*8 solutions:
1051322314251617 1051322314251618 1051322314251619
1051322314251718 1051322314251719 1051322314251819
1051322325161718 1051322325161719 1051322325161819
1051322325171819 5132231425161718 5132231425161719
5132231425161819 5132231425171819 5132232516171819

There are 6 length 2*9 solutions:
106132231415261718 106132231415261719 106132231415261819
106132231426171819 106132231526171819 613223141526171819

And finally there is only one length 2*10 solution, which contains all the digits:
10713223141516271819

Permuting the digits in this way we obtain the largest self-describing number :
71322723191816151410

and a brief search among all the 10!=3628800 permutations shows that the largest prime self-describing number is
71322723161814151019

Considering all the permutations of the 99 basic solutions, we obtain 1*1!+35*4!+21*5!+20*7!+15*8!+6*9!+1*10! = 6515041 different self-describing numbers.

***

Giovanni, Capelle & Sahay sent some results about self-descriptive primes IF an ugly thing such as 'repetition of description of digits' is allowed:

Giovanni wrote:

The case with multiple descriptors seems more difficult to enumerate.
I had not the time to think a lot about it. My very simple program to count solutions to the original problem took about a couple of minutes, while the naive program I hastily devised for the modified problem will take several days to complete the search.
I have stopped it at the first 1500 solutions, which were found quite fast.
Here is a sample of the solutions:

20 20 32 33
21 21 32 33
42 23 23 24
10 21 42 42 23 34
20 20 41 41 41 41 32 53 53 53 53 64 65 65 46 (30 digits)

Anurag wrote:

Assuming that a "description"(descriptive pair) can be repeated in a number, I found few SD numbers. For Q3, I dont know the largest self-descriptive prime, but I found a few SDPs like this 32-digit number: 29575757434372457221642943262143

Capelle wrote:

The self-descriptive numbers can also be described with the following general definition :

We say that a number N is 'self-descriptive’ when :

N has 2n digits.

Considering the string of digits on N grouped this way : (a1b1)(a2b2)…(anbn), the following sentence is true, regarding N : “N has a1 digits b1, a2 digits b2, …, an digits bn”.

1 <= ai <= 9, if N is in base 10.

0 <= bi <= 9, if N is in base 10.

if i <> j and bi = bj, then ai = bj.

It's a simple definition, which authorizes the fact that the same digit can be counted several times, i.e. bi can be equal to bj when i <> j. I don't know if it was not already a consequence of the original Mudge's definition (I don't have seen its formal aspects).
I give you an example : 92929292929292896128261410171513 (32 digits) is a self-descriptive prime because this prime has nine 2's, eight 9's, six 1's, two 8's, two 6's, one 4, one 0, one 7, one 5 and one 3.

But with this definition you can have the particular case in which the digits of a number N don't need to be counted more than one time (for instance, 16331831), because bi <> bj when i <> j.

For the numbers concerned by this particular situation you will find some characteristics and specific properties (for instance the property concerning the sum of all the digits of N : (a1+a2+…+an) + (b1+b2+ … +bn) = (a1 x b1)+(a2 x b2)+ …+(an x bn) ), as described in this puzzle.

In the context of my definition, the number 10153331 remains the smallest self-descriptive prime, but the number 71322723161814151019 is not the largest self-descriptive prime : it's the largest only when we look at the numbers N for which each bi is present once (situation without repetition).
It means that the limited definition used in the solution of this puzzle is a particular case of my definition.

To take again the first line of introduction of this puzzle, we can also say that we know at least four kinds of numbers that can be considered as 'self-descriptive' ...

***
A few days later (19/8/5), Capelle added:

I have found today (again without computer) another self-descriptive number (with repetition of pairs allowed), which is better than the number that I sent two days ago :
9998989898989898878675757575757575646262626262624341414141303030 (64 digits).

***

The 21/8/05, Anurag Sahay sent the following new 70 digits SD number record:

7070707070707051515151828282828282828213646464646464959595959576979899

***

One day later Patrick Capelle - knowing the Anurag's result - sent the following 70 digits ones:

9998979595959595828282828282828276707070707070706464646464645151515113

9998979595959595838383838383838376727272727272726464646464645151515110

9998979595959595848484848484848476737373737373736262626262625151515110

***

Scrambling the right part of the Capelle's largest result I simply calculated the largest prime, 70 digits large:

9998979595959595848484848484848476737373737373736262626251516210516251

***

Obviously it's time to obtain a rigorous proof shown what is the largest possible quantity of digits for a SD number, repetitions allowed.

***

Records | Conjectures | Problems | Puzzles