Smith numbers are numbers such that the sum of the decimal digits of the integers that make up that number is the same as the sum of the decimal digits of its prime factors excluding 1.

By definition, all primes are excluded as they (naturally) satisfy this condition!

Smith numbers are also known as   joke   numbers.



Example
Using the number 166

Find the prime factors of 166 which are: 2 x 83

Then, take those two prime factors and sum all their decimal digits: 2 + 8 + 3 which is 13

Then, take the decimal digits of 166 and add their decimal digits: 1 + 6 + 6 which is 13

Therefore, the number 166 is a Smith number.



Task
Write a program to find all Smith numbers below 10000.



See also
 from Wikipedia:   [Smith number].
 from MathWorld:   [Smith number]. 
 from OEIS A6753:   [OEIS sequence A6753].
 from OEIS A104170:   [Number of Smith numbers below 10^n]. 
 from The Prime pages:   [Smith numbers].


' FB 1.05.0 Win64
 
Sub getPrimeFactors(factors() As UInteger, n As UInteger)
  If n < 2 Then Return
  Dim factor As UInteger = 2
  Do
    If n Mod factor = 0 Then
      Redim Preserve factors(0 To UBound(factors) + 1)
      factors(UBound(factors)) = factor
      n \= factor
      If n = 1 Then Return
    Else
      ' non-prime factors will always give a remainder > 0 as their own factors have already been removed
      ' so it's not worth checking that the next potential factor is prime  
      factor += 1  
    End If    
  Loop
End Sub 
 
Function sumDigits(n As UInteger) As UInteger
  If n < 10 Then Return n
  Dim sum As UInteger = 0
  While n > 0
    sum += n Mod 10
    n \= 10
  Wend
  Return sum
End Function
 
Function isSmith(n As UInteger) As Boolean
  If n < 2 Then Return False
  Dim factors() As UInteger
  getPrimeFactors factors(), n
  If UBound(factors) = 0 Then Return False  '' n must be prime if there's only one factor
  Dim primeSum As UInteger = 0
  For i As UInteger = 0 To UBound(factors)
    primeSum += sumDigits(factors(i))
  Next
  Return sumDigits(n) = primeSum
End Function
 
Print "The Smith numbers below 10000 are : "
Print
Dim count As UInteger = 0
For i As UInteger = 2 To 9999
  If isSmith(i) Then  
    Print Using "#####"; i;
    count += 1
  End If
Next
Print : Print
Print count; " numbers found"
Print
Print "Press any key to quit"
Sleep