Find a ten-digit number with the number of zeros in it as the most significant (leftmost) digit, the number of ones as the second most significant digit etc.
$\begingroup$
$\endgroup$
2
-
9$\begingroup$ en.wikipedia.org/wiki/Self-descriptive_number $\endgroup$– Ross MillikanCommented Apr 13, 2015 at 15:23
-
$\begingroup$ Already solved in code: stackoverflow.com/questions/12704061/… $\endgroup$– user12496Commented Sep 9, 2015 at 21:56
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
11
I found this one:
6210001000
My method was to start with 9000000000 and go from there.
9000000000 — start by counting nine 0s
9000000001 — count one 9
9100000001 — count one 1
9200000001 — count two 1s
9210000001 — count one 2
6210000001 — count six 0s
6210001000 — count one 6, zero 9s
This is where the numbers settle.
A different set of steps that counts digits left-to-right, starting from 0000000000. This takes no shortcuts and is complete.
0000000000
How many 0s? A
A000000000 — count A 0s
How many 1s? 0
How many 2s? 0
...
How many 9s? 0
Restart at 0
How many 0s? 9
9000000000 — count nine 0s
How many 1s? 0
How many 2s? 0
...
How many 9s? 1
9000000001 — count one 9
Restart at 0
How many 0s? 8
8000000001 — count eight 0s
How many 1s? 1
How many 2s? 0
...
How many 8s? 1
8100000011 — count one 8
How many 9s? 0
8100000010 — count zero 9s
Restart at 0
How many 0s? 7
7100000010 — count seven 0s
How many 1s? 2
7200000010 — count two 1s
How many 2s? 1
7210000010 — count one 2
How many 3s? 0
...
How many 7s? 1
7210000110 — count one 7
How many 8s? 0
7210000100 — count zero 8s
How many 9s? 0
Restart at 0
How many 0s? 6
6210000100 — count six 0s
How many 1s? 2
6210000100 — no change
How many 2s? 1
6210000100 — no change
How many 3s? 0
...
How many 6s? 1
6210001100 — count one 6
How many 7s? 0
6210001000 — count zero 7s
How many 8s? 0
How many 9s? 0
Restart at 0
How many 0s? 6
6210001000 — no change
How many 1s? 2
6210001000 — no change
How many 2s? 1
6210001000 — no change
How many 3s? 0
...
How many 6s? 1
6210001000 — no change
How many 7s? 0
6210001000 — no change
How many 8s? 0
How many 9s? 0
Reached the end with no change.
Result is 6210001000.
answered Apr 13, 2015 at 13:41
-
$\begingroup$ You are miscounting the number of ones quite at several points. Effectivly uou start with 7210000010. Since 7200000010 should have been followed by 7110000010. $\endgroup$– TaemyrCommented Apr 13, 2015 at 14:15
-
1$\begingroup$ @Taemyr, It is in fact impossible to not miscount the numbers at all of the non-final points since the final result is the point at which the numbers are consistent. I simply showed my thought process as I was settling the number. $\endgroup$ Commented Apr 13, 2015 at 14:18
-
$\begingroup$ How did you go from 9000000001 to 8000000001? $\endgroup$– TaemyrCommented Apr 13, 2015 at 14:20
-
$\begingroup$ @Taemyr, Because there are only 8 0s shown in 9000000001. $\endgroup$ Commented Apr 13, 2015 at 14:20
-
1$\begingroup$ But there are 1 1, so why not to 8100000001? $\endgroup$– TaemyrCommented Apr 13, 2015 at 14:22
$\begingroup$
$\endgroup$
3
Such a number is
6210001000
That is,
six 0's, two 1's, one 2 and one 6.
I was going to try and add how I got to this, but I realized I had gotten there by trial and error. Pity that omitting that honesty cost me the tick :P
-
$\begingroup$ And zero threes, zero fours, etc. $\endgroup$– blakeoftCommented Apr 13, 2015 at 13:53
-
$\begingroup$ @blakeoft: yes, I left out the obvious repeating stuff :P $\endgroup$ Commented Apr 13, 2015 at 13:56
-
$\begingroup$ ... and one 6 (you forgot to add) $\endgroup$ Commented Apr 13, 2015 at 15:06
$\begingroup$
$\endgroup$
1
I used VBA in Excel workbook module (because it was convenient for me). Feel free to convert it to work in cscript. I think all you have to do is change the debug.print with the appropriate Write statement.
First off, here is the function which tests to see if the number is self-referential. It's hard-coded for 10-digit numbers, but it could be adapted for smaller widths or even other number bases if desired.
Public Function IsSelfReferential(strNumber As String) As Boolean
'This tests to see if a 10-digit string is a self-referential number.
Dim i, intLength As Integer
intLength = Len(strNumber)
If intLength <> 10 Then Stop
For i = 0 To 9
'VBA hack to find number of occurrances by removing what we are looking for and comparing the new length.
If (intLength - Len(Replace(strNumber, Trim$(Str$(i)), ""))) _
<> Val(Mid$(strNumber, i + 1, 1)) Then
'Since the length doesn't match the digit stored, then this number can't be self-referential
IsSelfReferential = False
Exit Function
End If
Next
'If we made it this far, the number is self-referential.
IsSelfReferential = True
End Function
I decided to exploit the fact that whatever the answer is, the digits will add up to 10, since we are describing the number of digits in 10-digit number. Anything higher or lower can not be a correct answer. This greatly reduces the number of possibilities the routine has to check compared to a brute-force count. This function generates numbers whose digits add up to a certain goal.
Public Sub NumbersThatAddUpTo(intGoal As Integer, intWidth As Integer, Optional strPrefix As String)
'Recursive function to find all combinations of intWidth digits that add up to intGoal.
Dim i, intMax As Integer
If intWidth = 1 Then
If intGoal <= 9 And intGoal >= 0 Then
If IsSelfReferential(strPrefix & Trim$(Str$(intGoal))) Then
Debug.Print strPrefix & Trim$(Str$(intGoal))
End If
End If
Else
If intGoal < 9 Then intMax = intGoal Else intMax = 9
For i = 0 To intMax
NumbersThatAddUpTo intGoal - i, intWidth - 1, strPrefix & Trim$(Str$(i))
Next
End If
End Sub
To execute the function, I ran the sub from the debug window:
ThisWorkbook.NumbersThatAddUpTo 10,10
And a couple of seconds later, it produced a single result: 6210001000
-
$\begingroup$ For anyone who cares, the last function produced 92,368 10-digit numbers to consider, which sure beats 10,000,000,000. $\endgroup$ Commented Apr 14, 2015 at 3:53