A nine digit number has the property where the first digit equals the number of zeros and ones used in the number, the second digit equals the number of ones and twos used in the number, the third digit equals the number of twos and threes used in the number, etc. through the ninth digit equals the number of eights and nines used in the number. What could the number be?
A ten digit number has a similar property to the nine digit number. The first digit equals the number of zeros and ones used in the number, the second digit equals the number of ones and twos used in the number, etc. through the ninth digit. And also, the tenth digit equals the number of zeros and nines used in the number. What could this number be?
(In reply to
re(2): Attn: Ken Haley by Ken Haley)
A little more thought reveals that the 10-digit sum has to be 20. We're counting every digit twice and there are 10 digits. 2x10 = 20.
The 9-digit sum is different. We're counting every digit twice except the zeros, which we're only counting once. So the sum is 18 minus the number of zeros. There happen to be 3 zeros in each solution; so the sum is 15 in each case.
-----(later that day)-----
We can reason that there cannot be more than 2 8s and 9s, so the 9th digit (i9) can't be more than 2. (Otherwise the sum of the digits would be more than 20, which we showed above cannot be.) Similarly there can't be more than 2 7s and 8s, so the 8th digit can't be more than 2. And there can't be more than 3 6s and 7s so the 7th digit can't be more than 3, the 6th digit can't be more than 4, the 5th 5, the 4th 7, and the 3rd 8. By putting this knowledge into my program, it now runs in about 3.5 seconds. (I also figured out how to measure time intervals in fractions of a second.) Here's the revised version (with Penny's optimization as well...i.e., setting i10 = 20 - sum(i1-i9). ).
Option Strict On
Imports System.Math
Module Module1
'This program solves the following problems:
' A nine digit number has the property where the first digit equals
' the number of zeros and ones used in the number, the second digit
' equals the number of ones and twos used in the number, the third
' digit equals the number of twos and threes used in the number, etc.
' through the ninth digit equals the number of eights and nines used
' in the number. What could the number be?
' A ten digit number has a similar property to the nine digit number.
' The first digit equals the number of zeros and ones used in the number,
' the second digit equals the number of ones and twos used in the number,
' etc. through the ninth digit. And also, the tenth digit equals the
' number of zeros and nines used in the number. What could this number be?
Dim i1 As Integer
Dim i2 As Integer
Dim i3 As Integer
Dim i4 As Integer
Dim i5 As Integer
Dim i6 As Integer
Dim i7 As Integer
Dim i8 As Integer
Dim i9 As Integer
Dim i10 As Integer
Dim check9count As Integer = 0
Dim check10count As Integer = 0
Sub main()
Dim startTime As DateTime = Now
For i1 = 0 To 9
For i2 = 0 To 9
For i3 = 0 To Min(8, 20 - i1 - i2)
For i4 = 0 To Min(7, 20 - i1 - i2 - i3)
For i5 = 0 To Min(5, 20 - i1 - i2 - i3 - i4)
For i6 = 0 To Min(4, 20 - i1 - i2 - i3 - i4 - i5)
For i7 = 0 To Min(3, 20 - i1 - i2 - i3 - i4 - i5 - i6)
For i8 = 0 To Min(2, 20 - i1 - i2 - i3 - i4 - i5 - i6 - i7)
For i9 = 0 To Min(2, 20 - i1 - i2 - i3 - i4 - i5 - i6 - i7 - i8)
'i9 = 0
check9()
i10 = 20 - i1 - i2 - i3 - i4 - i5 - i6 - i7 - i8 - i9
If i10 < 10 Then check10()
Next
Next
Next
Next
Next
Next
Next
Next
Next
Console.WriteLine()
Console.WriteLine("check9 calls: {0} check10 calls: {1}", check9count, check10count)
Console.WriteLine("Seconds elapsed: {0}", Now.Subtract(startTime).TotalSeconds)
Console.ReadLine()
End Sub
Sub check9()
check9count += 1
Dim digits(11) As Integer
digits(i1) += 1 : digits(i1 + 1) += 1
digits(i2) += 1 : digits(i2 + 1) += 1
digits(i3) += 1 : digits(i3 + 1) += 1
digits(i4) += 1 : digits(i4 + 1) += 1
digits(i5) += 1 : digits(i5 + 1) += 1
digits(i6) += 1 : digits(i6 + 1) += 1
digits(i7) += 1 : digits(i7 + 1) += 1
digits(i8) += 1 : digits(i8 + 1) += 1
digits(i9) += 1 : digits(i9 + 1) += 1
If i1 <> digits(1) Then Return
If i2 <> digits(2) Then Return
If i3 <> digits(3) Then Return
If i4 <> digits(4) Then Return
If i5 <> digits(5) Then Return
If i6 <> digits(6) Then Return
If i7 <> digits(7) Then Return
If i8 <> digits(8) Then Return
If i9 <> digits(9) Then Return
Console.WriteLine("{0} {1} {2} {3} {4} {5} {6} {7} {8}", i1, i2, i3, i4, i5, i6, i7, i8, i9)
End Sub
Sub check10()
check10count += 1
Dim digits(11) As Integer
digits(i1) += 1 : digits(i1 + 1) += 1
digits(i2) += 1 : digits(i2 + 1) += 1
digits(i3) += 1 : digits(i3 + 1) += 1
digits(i4) += 1 : digits(i4 + 1) += 1
digits(i5) += 1 : digits(i5 + 1) += 1
digits(i6) += 1 : digits(i6 + 1) += 1
digits(i7) += 1 : digits(i7 + 1) += 1
digits(i8) += 1 : digits(i8 + 1) += 1
digits(i9) += 1 : digits(i9 + 1) += 1
digits(i10) += 1 : digits(i10 + 1) += 1
digits(10) += digits(0) 'adds the count of 0's to the count of 9's.
If i1 <> digits(1) Then Return
If i2 <> digits(2) Then Return
If i3 <> digits(3) Then Return
If i4 <> digits(4) Then Return
If i5 <> digits(5) Then Return
If i6 <> digits(6) Then Return
If i7 <> digits(7) Then Return
If i8 <> digits(8) Then Return
If i9 <> digits(9) Then Return
If i10 <> digits(10) Then Return
Console.WriteLine("{0} {1} {2} {3} {4} {5} {6} {7} {8} {9}", i1, i2, i3, i4, i5, i6, i7, i8, i9, i10)
End Sub
End Module
Edited on September 25, 2005, 1:18 am
re(3): Attn: Ken Haley
