1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
#!/usr/bin/perl
# ch-2.pl
=begin comment
* https://theweeklychallenge.org/blog/perl-weekly-challenge-133/
*
* Task 2 > Smith Numbers
* ======================
*
* Write a script to generate the first 10 `Smith Numbers` in 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.
=end comment
=cut
use strict;
use warnings;
use utf8;
use Data::Dumper;
################################################################################
# Our PWC solution, along with some help subroutines
################################################################################
# First, we need a utility function to find and return our prime factors
sub prime_factors {
my $number = shift;
$number =~ s{ # Trim whitespace, probably unnecessary, but it won't hurt
\A # Start of the line
\s+ # Leading whitespace
| # Alternating with
\s+ # Trailing whitespace
\z # End of line
}{}gx;
# Validate our input is an integer
if ( !$number =~ m/\A\d+\z/ ) {
# Bail
return 0;
}
my @factors;
my $divisor = 2; # Starting with 2, we'll divide and check for modulo
while ( $number >= 2 ) {
if ( $number % $divisor == 0 ) {
# If modulo is zero, push $divisor to @factors
push @factors, $divisor;
$number /= $divisor;
}
else {
# Else, increment $divisor and try again
$divisor += 1;
}
}
return \@factors;
}
# Helper to reduce number to sum of its digits
sub sum_digits {
my $number = shift;
# Trim
$number =~ s{ \A \s+ | \s+ \z }{}gx;
# Split digits
my @digits = split //, $number;
# Reduce
my $sum = 0;
foreach my $digit (@digits) {
$sum += $digit;
}
return $sum;
}
# Find `Smith Numbers` with the help of our two subroutines, `prime_factors`
# and `sum_digits`
sub find_smith_numbers {
# We need to find the first ten, but we might as well write it to find more
my $limit = shift // '10';
my @smith_numbers;
# Smith Numbers are not prime numbers, so we might as well start at 4
my $test = '4';
# Search until we hit our limit
while ( scalar @smith_numbers < $limit ) {
my @primes = @{ prime_factors($test) };
my $factor_sum = 0;
# Reduce @primes to sum of its digits
foreach my $prime (@primes) {
$factor_sum += sum_digits($prime);
}
my $digit_sum = sum_digits($test);
# Check for matching sums and for prime number (if scalar @primes == 1,
# $test is a prime number)
if ( $factor_sum == $digit_sum && scalar @primes != 1 ) {
push @smith_numbers, $test;
}
$test += 1;
}
return \@smith_numbers;
}
################################################################################
# Utilities
################################################################################
sub list_with_oxford {
my @list = @{ +shift };
my $last_number = $list[-1];
return join( ', ', @list[ 0 .. $#list - 1 ] ) . ', and ' . $last_number;
}
################################################################################
# Main
################################################################################
sub main {
my $limit = shift @ARGV // '10';
my $smith_numbers = find_smith_numbers $limit;
my $result_string = list_with_oxford $smith_numbers;
print "The first $limit Smith Numbers are $result_string.\n";
return 1;
}
main();
|
