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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
|
#!/usr/bin/perl
use strict;
use warnings;
use English;
################################################################################
# Begin main execution
################################################################################
# Given cases (some bases...)
my @bases = ( 2, 4, 10, 12 );
my $base;
# If you have some time on your hands, why not try
# them all?
# @bases = 2 .. 36;
print("\n");
foreach $base (@bases){
printf(
" f(%d)=\"%s\"\n",
$base,
calculate_largest_non_repeating_square_in_base($base)
);
}
print("\n");
exit(0);
################################################################################
# End main execution; subroutines follow
################################################################################
################################################################################
# Calculate the largest perfect square that does not contain a repeated digit
# in a specified base
# Takes one argument:
# * The specified base, which must range from 2 to 36, inclusive (e.g. 16)
# Returns on success:
# * A string representing the largest square with no repeated digits when
# expressed in the specified base (e.g. "FEB6795D4C32A801")
# Returns on error:
# * undef if the base is out of range
# * An empty string if there did not appear to be any squares without repeating
# digits in the specified base
################################################################################
sub calculate_largest_non_repeating_square_in_base{
my $base = int(shift());
return(undef)
if(($base < 2) || ($base > 36));
my $digit_string = "ZYXWVUTSRQPONMLKJIHGFEDCBA9876543210";
my $root;
# Grab all the possible digits in this base- which
# also happens (actually this is not a
# coincidence...) to be the largest number in this
# base with no repeating digits
$digit_string = substr($digit_string, -$base);
# Get the root of the largest square less than
# the aforementioned number
$root = int(sqrt(digit_string_to_number($digit_string, $base)));
# Loop while the root is not zero and the square,
# when expressed in the specified base, has a
# repeating digit
while(
$root
&&
(
# Assignment to capture digit string is deliberate
($digit_string = number_to_digit_string($root ** 2, $base))
=~
m/(.).{0,}\1/
)
){
# Decrement the root
$root--;
}
if($root){
# Root is not zero- return the square in the
# specified base
return($digit_string);
} else{
# Root is zero- return an empty string
return("");
}
}
################################################################################
# Convert a string of digits in a specified base from 2 to 36 into its
# computer-friendly numerical representation
# Takes two arguments:
# * The string of digits, which must consist solely of digits 0-9 and A-Z (e.g.
# "FF"); only those digits valid for the specified base (e.g. 0-F will be
# accepted
# * The base in which the number in the string is written, which must range
# from 2 to 36, inclusive (e.g. 16)
# Returns on success:
# * The numerical representation of the number encoded in the string (e.g. 255)
# Returns on error:
# * undef if the base is out of range or there are invalid digits in the string
# for the defined base
################################################################################
sub digit_string_to_number{
my $string = shift();
my $base = int(shift());
return(undef)
if(($base < 2) || ($base > 36));
my %digit_table = (
0 => 0, 1 => 1, 2 => 2, 3 => 3, 4 => 4,
5 => 5, 6 => 6, 7 => 7, 8 => 8, 9 => 9,
A => 10, B => 11, C => 12, D => 13, E => 14,
F => 15, G => 16, H => 17, I => 18, J => 19,
K => 20, L => 21, M => 22, N => 23, O => 24,
P => 25, Q => 26, R => 27, S => 28, T => 29,
U => 30, V => 31, W => 32, X => 33, Y => 34,
Z => 35
);
my @digits;
my $i = 0;
my $total = 0;
# Reverse the digits so the least-significant
# comes first, allowing their array indices to be
# used as exponents
@digits = reverse(split('', uc($string)));
# Repeatedly accumulate each digit- if it's valid-
# by adding its value raised to the power of its
# position within the number
for($i=0; $i<scalar(@digits); $i++){
return(undef)
unless(
defined($digit_table{$digits[$i]})
&&
($digit_table{$digits[$i]} < $base)
);
$total += ($base ** $i) * $digit_table{$digits[$i]};
}
return($total);
}
################################################################################
# Convert a computer-friendly number into a string of digits in a specified
# base from 2 to 36
# Takes two arguments:
# * The number to convert to a string of digits (e.g. 255)
# * The base in which the number should be written, which must range from 2 to
# 32, inclusive (e.g. 16)
# Returns on success:
# * A string representing the number in the specified base (e.g. "FF")
# Returns on error:
# * undef if the base is out of range
################################################################################
sub number_to_digit_string{
my $number = int(shift());
my $base = int(shift());
return(undef)
if(($base < 2) || ($base > 36));
my @digit_list = qw(
0 1 2 3 4 5 6 7 8 9
A B C D E F G H I J
K L M N O P Q R S T
U V W X Y Z
);
my $string = "";
# Special case of the number being zero
if($number == 0){
return("0");
}
# Not zero- repeatedly convert remainders to
# digits then truncate the dividend...
while($number){
$string = $digit_list[$number % $base] . $string;
$number = int($number / $base);
}
return($string);
}
|
