A047841: Autobiographical numbers

Question

Definition

Here is the process to describe a number:

• For each number from 0 to 9 that is present in the number:
• Write down the frequency of that digit and then the digit.

For example, for the number 10213223:

• There is 1 occurrence of 0,
• 2 occurrences of 1,
• 3 occurrences of 2,
• 2 occurrences of 3.

Therefore, the number that describes 10213223 is 10213223 (10 from the first property, 21 from the second, etc.).

Note that the number of occurrences of a digit may be greater than 9.

Task

You are to print/output all numbers that describe themselves.

Specs

• Standard loopholes apply, except that you are allowed to hardcode the output or store information related to the output in your program.
• The numbers in the output can be in any order.
• The numbers in the output are allowed to have duplicates.
• You may use any separator, if you choose to print instead of output.
• You are allowed to prefix and/or postfix output if you choose to print instead of output.
• The separator and the prefix and the postfix may not contain any digits (U+0030 to U+0039).
• The solution must compute in one day.

Full list (109 items)

22
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
1031223314
1031223315
1031223316
1031223317
1031223318
1031223319
3122331415
3122331416
3122331417
3122331418
3122331419
3122331516
3122331517
3122331518
3122331519
3122331617
3122331618
3122331619
3122331718
3122331719
3122331819
10413223241516
10413223241517
10413223241518
10413223241519
10413223241617
10413223241618
10413223241619
10413223241718
10413223241719
10413223241819
41322324151617
41322324151618
41322324151619
41322324151718
41322324151719
41322324151819
41322324161718
41322324161719
41322324161819
41322324171819
1051322314251617
1051322314251618
1051322314251619
1051322314251718
1051322314251719
1051322314251819
1051322325161718
1051322325161719
1051322325161819
1051322325171819
5132231425161718
5132231425161719
5132231425161819
5132231425171819
5132232516171819
106132231415261718
106132231415261719
106132231415261819
106132231426171819
106132231526171819
613223141526171819
1011112131415161718
1011112131415161719
1011112131415161819
1011112131415171819
1011112131416171819
1011112131516171819
1011112141516171819
1011113141516171819
1111213141516171819
10713223141516271819
101112213141516171819

References

• Autobiographical numbers: OEIS A047841
• Biographical number: OEIS A047842

Answer 1

gawk, 161 bytes

BEGIN{
    for(split("0 10 2 2 1 1 1 1",a);c=c<11;n=o=_){
        while(++$c>a[c]+1)$(c++)=0;
        for(i in a)n=$i?n$i i-1:n;
        for(i=10;i--;)if(d=gsub(i,i,n))o=d i o;
        if(n==o)print n
    }
}

(line breaks and tabs for clarity)

It's a simple counter which uses the fact that each number has a limited occurrence. For instance is 0 no more than one time in any number, 1 no more than 11 times, 2 no more than 3 times ... and so on.

This way there are only 124415 numbers to check.

It then creates all numbers and checks their validity.

Completes in a few seconds.

Answer 2

dc, 487 bytes

Hardcoded the solution. I start with 22 and add the differences to get the the next numbers. Some returning operations like adding 1 five times in a row are stored in registers.

This is my first program ever written in dc so it can probably golfed a lot more.

[1+d1+d1+d1+d1+d]sa[1+d1+d1+d1+d97+d]sb[1+d1+d99+d1+d100+d]sc[1+d1+d1+d98+dlcx]sd[1+d100+d10000+d]se22d10213201+d98010+d2081+dlax11008995+dlax9800995+dlax208096+dlbxldx999891495+dlax2091108096+dlbxldx10410100909697+dldx30909100909798+dlcx9899+dlex1009999990079798+dlcx10909899+dlex4080909099989899+dlex1091000000+d100999998899089899+d1+d100+d10910000+d10 8^+d50709091 10 10^*+d397888989888989899+dlex10 6^+d10 8^+d10 10^+d10 12^+d1001 10 14^*+d9602010000000100000+d90398989999999900000+f

You can execute the program using dc -e "[solution]", where [solution] is the string above. It outputs the numbers in reverse order. dc -e "[solution]" | sort -n for output in the same order as the list.

Answer 3

Haskell, 157 bytes

c=concat
d!n=['1'..n]>>[d]
r n=['0'..n]
a=r '9'
b s=c[shows n[d]|d<-a,n<-[sum[1|x<-s,x==d]],n>0]
main=print[x|x<-b.c.zipWith(!)a<$>mapM r"1;33222211",x==b x]

Try it online!

Inspired by the gawk answer, this loops over all strings of 0–1 zeros, then 0–11 ones, then 0–3 twos, .... It "biographs" the string (b "01111122" == "105122") and prints that result if is, itself, autobiographical (b x == x).

Answer 4

Ruby, 776 bytes

The rules say that "you are allowed to hardcode the output", so this solution does just that.

x="m|62wkn|65075|651sy|651sz|651t0|651t1|651t2|651t3|cp0ei|cp0ej|cp0ek|cp0el|cp0em|cp0en|ij2wi|ij2wj|ij2wk|ij2wl|ij2wm|ij2wnAh3Ah4Ah5Ah6Ah7AjwAjxAjyAjzAmpAmqAmrApiApjAsb|h1yp02|h1yp03|h1yp04|h1yp05|h1yp06|h1yp07Bc7Bc8Bc9BcaBcbBf0Bf1Bf2Bf3BhtBhuBhvBkmBknBnfFh8Fh9FhaFhbFk1Fk2Fk3FmuFmvFpnC08xC08yC08zC0bqC0brC0ejC81iC81jC84bCfu3EsxkfohEsxkfoiEsxkfojEsxkfraEsxkfrbEsxkfu3Et429yuEt429yvEt42a1nEt42hrf|1ej82kg93hy|1ej82kg93hz|1ej82kg93kr|1ej82kg9baj|1ej832ht8a3|t10qi0rmwpi|t10qi0rmwpj|t10qi0rmwsb|t10qi0y4qzv|t10qi2lo3hn|4nq1gm5kd1grG4p2zeraG4p2zerbG4p2zeu3G4p2zmjvG4p3l25nG4qr4enfG9c4v417|7ojtp0qb1maz|8fxg6lw9mtyj|29e6onjxe94gb|lc7bc5zbz4je3";a="|inj,|1fmye,|enb7ow,|enb7,|acnu,|3ovro98,|7ojtc".split',';b="ABCDEFG";7.times{|i|x.gsub! b[i],a[i]};x.split('|').map{|x|p x.to_i 36}

---

Ruby, 116 bytes

A much shorter program that takes way too long to run, but given long enough should be able to do it. I do not know if it fits the time constraint.

f=->n{(?0..?9).map{|x|[n.to_s.chars.count{|c|c==x},x]}.select{|a|a[0]>0}.join.to_i}
(10**9).times{|i|p i if i==f[i]}

Answer 5

///, 542 bytes

/:/\/\///^/13223:!/31:*/
10:#/!223!:&/4^241:$/1819:(/51617:)/
!3!:%/5^142:@/111:-/*@121!:_/51:+/
!123!:=/41:A/617:B/19:C/*!3!:D/18:E/6^1=52:F/
#:G/
2^:H/*5^2:I/1!=($:J/_6:K/
&:L/*&:M/_7/22*2^*!1233C4C5C6C7C8C9G14G15G16G17GDGB+4+5+6+7+8+9)=5)=6)=7)=8)=9)J)M)_8)_9)A)6D)6B)7D)7B)8B*#4*#5*#6*#7*#8*#9F=5F=6F=7F=8F=9FJF_7F_8F_9FAF6DF6BF7DF7BF8BLJLML_8L_9LAL6DL6BL7DL7BL8BK(KJDKJBKMDKMBK5$KADKABK6$K7$*%(*%JD*%JB*%MD*%MB*%5$H(DH(BHJ$HM$
%(D
%(B
%J$
%M$
5^2($*EAD*EAB*E6$*6^142A$*6^152A$
EA$-=(D-=(B-=J$-=_7$-=617$-($*@121=($*@I
@12I*7^1=_627$*@22I

Try it online!

Definitely less than 1440 bytes for sure!!! Uses 28 constants along with the literal, an unusually high amount for ///.

Answer 6

Husk, ²¹ 20 bytes

f₁N
=⁰dΣf←Ṡzem#d⁰ŀ10

Try it online!

Not sure if it will complete in one day, but it does a straightforward test and filters the infinite list of natural numbers by it. No hardcoding.

Theoretically, it will definitely print all autobiographical numbers, and proceed to check till the heat death of the universe.

-1 byte after correcting the algorithm.

Answer 7

Jelly, 34 bytes

DFṢŒrU
3x8“¢¿‘;µ,€"J’$ŒPŒp€ẎḊÇƑƇVV

This program is too slow for TIO, but finished in 2 minutes 8.375 seconds on my computer (thus, less than one day, as required by the question). It can easily be optimized to work on TIO too:

Jelly (Try It Online!), 36 bytes

DFṢŒrU
2x6“¢¿¤¤‘;µ,€"J’$ŒPŒp€ẎḊÇƑƇVV

Try it online! (The footer prints the list of results, plus a count of how many results there are.)

Algorithm

The basic idea is to generate lists of (frequency, number) pairs and then check to see if they correspond to an autobiographical number (by collapsing them into a list of digits, then calculating how many times each digit appears and seeing if it matched the original list of (frequency, number) pairs). We have to generate every list that corresponds to an autobiographical number, but are allowed to also generate extras, as long as we can check and reject them within the time limit.

Any answer has at most one 0, eleven 1s, three 2s, three 3s, and two of any other digit. \$2×12×4×4×3^6=279936\$, a small enough list to check in a minute, so we can just generate all (frequency, number) lists with less than these frequencies to get the TIO version of the program. For the "main" submission, we also generate (useless) lists which can have up to four copies of digits in the 4…9 range, because doing so is slightly shorter to express in Jelly; that's \$2×12×4^8=1572864\$ lists which is still a small enough number to check within a day.

Explanation

Helper function 1Ŀ

The helper function takes an arbitrary list of (frequency, digit) pairs, counts how many times each digit appears within the frequencies and digits, and returns the appropriate list of (frequency, digit) pairs, sorted by the digit.

If this function is run on a list of (frequency, digit) pairs that represent those of an autobiographical number and are sorted by the digit, the output will be the same as the input. Otherwise, the output will differ from the input.

DFṢŒrU
D        Split each number within the frequencies and digits into digits
 F       Recursive flatten, into a flat list of digits
  Ṣ      Sort the list of digits
   Œr    Run-length-encode, into (element, frequency) format
     U   Reverse each interior list, producing (frequency, digit) format

Main program

3x8“¢¿‘;µ,€"J’$ŒPŒp€ẎḊÇƑƇVV
3x8                           [3,3,3,3,3,3,3,3]
       ;                      prepend
   “¢¿‘                       [1,11]
           "                  to each element
          €                     for all numbers from 1 to that element
         ,                      pair that number with
        µ                       the element's
            J’$                 0-based index
               ŒP  €Ỷ         for each subsequence of the resulting list
                 Œp             take its Cartesian product
                     Ḋ        discard the first result (the empty list [])
                        Ƈ     filter the lists, keeping those that
                       Ƒ        are unchanged upon
                      Ç         running the helper function 1Ŀ
                         V    numerical concatenation of frequency with digit
                          V   numerical concatenation of those concatenations

This is mostly very straightforward, with the only confusing part being the various amounts of flattening and unflattening that go on. In particular, the ŒPŒp€Ẏ portion is the best way I found to write "from these sublists, select one or possibly no elements from each, and concatenate them"; the ŒP chooses which sublists will have no elements selected, the Œp€ selects one element from each of the rest, and the Ẏ collapses the structure which the ŒP introduced.

If there were no time limit…

you could do the task in 13 bytes:

ṢŒrUFV
2*JÇƑƇ

Try it online! (starts the search from just before a valid answer, and returns only 7 answers, so that you can see the program working)

The idea here is to search every possible number from 1 to 2¹⁰⁰⁰, returning only those which are autobiographical. Obviously, this won't finish in a reasonable length of time. (The choice of 2¹⁰⁰⁰ is mostly arbitrary – it's a number that can be calculated in Jelly using only three bytes. I couldn't find a way to calculate a number large enough using only two.)

I have a suspicion that there are a range of possible answers to this question which make different speed/brevity tradeoffs, so it's probably going to be possible to beat 34 bytes by making a program that takes longer to run but still fits within a single day. It's hard to know exactly where the byte savings should go, though.

Answer 8

Python 2.7 - 684 bytes

o=[22]
i=[[10213223,100096],[21322314,5],[31123314,5],[31331415,404],[1031223314,5],[3122331415,404],[10413223241516,303],[41322324151617,20202],[1051322314251617,202],[1051322325161718,10101],[5132231425161718,10101],[5132232516171819,0],[106132231415261718,101],[106132231426171819,0],[106132231526171819,0],[613223141526171819,0],[1011112131415161718,10101]]
l=[1011112131416171819,1011112131516171819,1011112141516171819,1011113141516171819,1111213141516171819,10713223141516271819,101112213141516171819]
for n in i:
 for x in range(n[0],n[0]+n[1]):
  m="";x=str(x)
  for v in range(10):
   v=str(v);c=x.count(v)
   if c!=0:
    m=m+str(c)+v
    if m==x:o.append(m)
o+=l
print o

Kind of half hard coded and half computed. It takes the approach of splitting the numbers into groups of a manageable size with an upper and lower limit. The list i stores the lower limit and the difference between it and the upper limit as a nested list, All potential candidates are then checked within the range added to the output list o. The last 7 numbers are so far apart that it is cheaper to store them in their own list and add it at the end.

It currently runs in a couple of seconds and obviously increasing the group size would reduce the byte count but increase the run time. Not sure what it would come down to and still be within the one day limit.