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].


DisableDebugger
#ECHO=#True ; #True: Print all results
Global NewList f.i()
 
Procedure.i ePotenz(Wert.i)  
  Define.i var=Wert, i  
  While var
    i+1
    var/10    
  Wend  
  ProcedureReturn i  
EndProcedure
 
Procedure.i n_Element(Wert.i,Stelle.i=1)  
  If Stelle>0
    ProcedureReturn (Wert%Int(Pow(10,Stelle))-Wert%Int(Pow(10,Stelle-1)))/Int(Pow(10,Stelle-1))    
  Else
    ProcedureReturn 0    
  EndIf  
EndProcedure
 
Procedure.i qSumma(Wert.i)  
  Define.i sum, pos  
  For pos=1 To ePotenz(Wert)
    sum+ n_Element(Wert,pos)    
  Next pos  
  ProcedureReturn sum  
EndProcedure
 
Procedure.b IsPrime(n.i)
  Define.i i=5
  If n<2 : ProcedureReturn #False : EndIf
  If n%2=0 : ProcedureReturn Bool(n=2) : EndIf
  If n%3=0 : ProcedureReturn Bool(n=3) : EndIf
  While i*i<=n
    If n%i=0 : ProcedureReturn #False : EndIf
    i+2
    If n%i=0 : ProcedureReturn #False : EndIf
    i+4
  Wend  
  ProcedureReturn #True
EndProcedure
 
Procedure PFZ(n.i,pf.i=2)
  If n>1 And n<>pf
    If n%pf=0      
      AddElement(f()) : f()=pf
      PFZ(n/pf,pf)
    Else
      While Not IsPrime(pf+1) : pf+1 : Wend
      PFZ(n,pf+1)
    EndIf
  ElseIf n=pf
    AddElement(f()) : f()=pf
  EndIf   
EndProcedure
 
OpenConsole("Smith numbers")
;upto=100 : sn=0 : Gosub Smith_loop
;upto=1000 : sn=0 : Gosub Smith_loop
upto=10000 : sn=0 : Gosub Smith_loop
Input()
End
 
Smith_loop:
  For i=2 To upto
    ClearList(f()) : qs=0
    PFZ(i)
    CompilerIf #ECHO : Print(Str(i)+~": \t") : CompilerEndIf
    ForEach f()
      CompilerIf #ECHO : Print(Str(F())+~"\t") : CompilerEndIf
      qs+qSumma(f())
    Next
    If ListSize(f())>1 And qSumma(i)=qs 
      CompilerIf #ECHO : Print("SMITH-NUMBER") : CompilerEndIf
      sn+1
    EndIf
    CompilerIf #ECHO : PrintN("") : CompilerEndIf
  Next
  Print(~"\n"+Str(sn)+" Smith number up to "+Str(upto))
Return