Write a script to generate first 10
Smith Numbersin base 10.According to Wikipedia:
In number theory, a Smith number is a composite number for which, in a given number base, the sum of its digits is equal to the sum of the digits in its prime factorization in the given number base.
This is mostly about factorizing a number; something we have done in previous challenges.
We won't be writing our own factorization function. Instead, we will
use the module Math::Prime::Util which has a method factor.
This method takes a non-negative integer as argument, and returns
a list of factors of that number.
use Math::Prime::Util qw [factor];
We will write a subroutine to calculate the sum of the digits of a number. In fact, the subroutine will take a list of numbers, and returns the sum of all its digits.
We do the latter by concatenating all the given numbers, extracting the digits, and summing them:
sub digitsum (@n) {sum "@n" =~ /\d/ag}
Now it's just a matter of starting to count from 1, checking each
number whether it's a Smith Number, and stopping once we have ten of them:
my $c = 0;
my $n = 0;
do {
my @factors = factor ++ $n;
$c ++, say $n if @factors > 1 && digitsum ($n) == digitsum @factors;
} until $c == $COUNT;
Note that we filter out numbers which only have a single factor, as Smith Numbers are defined to be composite numbers.
Find the full program on GitHub.
We start off with a function which factorizes a number. We will use the fact that the ten Smith Numbers we have to produce are all less than 1000. This means we only have to check primes up to 31 to find factors, as \(31^2 < 1000 < 37^2\). We also know that no number less than 1000 has ten or more factors, but it can have nine factors, as \(2^9 < 1000 < 2^{10}\).
The function takes two arguments: a number to be factorize, and an array to populate with factors. The array will be large enough. The function returns the number of factors.
short small_primes [] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
# define SMALL_PRIMES_SIZE 11
# define MAX_FACTORS 9
size_t factorize (short n, short * factors) {
size_t f_i = 0; /* Index in output structure */
for (size_t i = 0; i < SMALL_PRIMES_SIZE && n > 1; i ++) {
short prime = small_primes [i];
while (n % prime == 0) {
factors [f_i ++] = prime;
n /= prime;
}
}
/*
* Possible left over large prime
*/
if (n > 1) {
factors [f_i ++] = n;
}
return (f_i);
}
We also have a digitsum function, which takes an array of numbers, and
returns the sum of all its digits. We do this by taking all the numbers
from the array, and repeatedly modding and dividing the number by 10,
summing the results of the mod operations:
# define BASE 10
short digitsum (size_t n, short * numbers) {
short out = 0;
char * tmp;
for (size_t i = 0; i < n; i ++) {
short number = numbers [i];
while (number) {
out += number % BASE;
number /= BASE;
}
}
return (out);
}
We can now create the main program. First, we have to malloc
memory for the array which gets populated with the factors:
short * factors;
if ((factors = (short *) malloc (MAX_FACTORS * sizeof (short))) == NULL) {
perror ("Malloc failed");
exit (1);
}
We can now try each number, check whether they are a Smith Number, and stop when we have ten of them:
# define COUNT 10
size_t c = 0;
short n = 0;
while (c < COUNT) {
size_t fc = factorize (++ n, factors);
if (fc > 1 && digitsum (1, &n) == digitsum (fc, factors)) {
printf ("%d\n", n);
c ++;
}
}
And don't forget to free the malloced memory!
free (factors);
Find the full program on GitHub.