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


include "cowgol.coh";
typedef N is uint16;   # 16-bit math is good enough
 
# Print a value right-justified in a field of length N
sub print_right(n: N, width: uint8) is
    var arr: uint8[16];
    var buf := &arr[0];
    var nxt := UIToA(n as uint32, 10, buf);
    var len := (nxt - buf) as uint8;
    while len < width loop
        print_char(' ');
        len := len + 1;
    end loop;
    print(buf);
end sub;
 
# Find the sum of the digits of a number
sub digit_sum(n: N): (sum: N) is
    sum := 0;
    while n > 0 loop
        sum := sum + n % 10;
        n := n / 10;
    end loop;
end sub;
 
# Factorize a number, write the factors into the buffer,
# return the amount of factors.
sub factorize(n: N, buf: [N]): (count: N) is
    count := 0;
    # Take care of the factors of 2 first
    while n>0 and n & 1 == 0 loop 
        n := n >> 1;
        count := count + 1;
        [buf] := 2;
        buf := @next buf;
    end loop;
    # Then do the odd factors
    var fac: N := 3;
    while n >= fac loop
        while n % fac == 0 loop
            n := n / fac;
            count := count + 1;
            [buf] := fac;
            buf := @next buf;
        end loop;
        fac := fac + 2;
    end loop;
end sub;
 
# See if a number is a Smith number
sub smith(n: N): (rslt: uint8) is
    rslt := 0;
    var facs: N[16];
    var n_facs := factorize(n, &facs[0]) as @indexof facs;
    if n_facs > 1 then
        # Only composite numbers are Smith numbers
        var dsum := digit_sum(n);
        var facsum: N := 0;
        var i: @indexof facs := 0;
        while i < n_facs loop
            facsum := facsum + digit_sum(facs[i]);
            i := i + 1;
        end loop;
        if facsum == dsum then rslt := 1; end if;
    end if;
end sub;
 
# Display all Smith numbers below 10000
var i: N := 2;
var count: N := 0;
while i < 10000 loop
    if smith(i) != 0 then
        count := count + 1;
        print_right(i, 5);
        if count & 0xF == 0 then print_nl(); end if;
    end if;
    i := i + 1;
end loop;
print_nl();
print("Found ");
print_i32(count as uint32);
print(" Smith numbers.\n");