Task 1: Sexy Prime Pairs
Write a script to print the first 10 "Sexy Prime Pairs". Sexy primes are prime numbers that differ from each other by 6 (e.g., 5 and 11).
Output
(5, 11)
(7, 13)
(11, 17)
(13, 19)
(17, 23)
(23, 29)
(31, 37)
(37, 43)
(41, 47)
(43, 49) # Note: 49 is not prime!
Wait, (47, 53) is the next pair!
Logic
Iterate through numbers sequentially. Check if the candidate number $p$ and $p+6$ are both prime. If yes, print the pair and increment our count until 10 pairs have been found.
Perl Solution
ch-1.pl
sub is_prime {
my $n = shift;
return 0 if $n <= 1;
return 1 if $n <= 3;
return 0 if $n % 2 == 0 || $n % 3 == 0;
my $i = 5;
while ($i * $i <= $n) {
return 0 if $n % $i == 0 || $n % ($i + 2) == 0;
$i += 6;
}
return 1;
}
my $count = 0;
my $num = 2;
while ($count < 10) {
if (is_prime($num) && is_prime($num + 6)) {
print "($num, ", $num + 6, ")\n";
$count++;
}
$num++;
}
Python Solution
ch-1.py
def is_prime(n: int) -> bool:
if n < 2: return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0: return False
return True
# Loop matching (num, num + 6) until 10 pairs are found
Task 2: LZW Compression
Write a script to implement Lempel–Ziv–Welch (LZW) compression and decompression algorithm.
Example Output
Compressed data: 65 66 256 258 260 262 264 266 66
Decompressed data: ABABABABABABABAB
Logic
Maintain a translation dictionary that maps strings to code values. Initialize with character codes (0..255). For encoding, search for the longest matched prefix in the dictionary, emit its code, and add the prefix extended by the next character into the dictionary. Decompression reverses the mapping.
Perl Solution
ch-2.pl
sub lzw_encode {
my ($data) = @_;
my %dictionary = map { chr($_) => $_ } (0..255);
my $current_string = "";
my @encoded_data;
foreach my $char (split //, $data) {
my $combined_string = $current_string . $char;
if (exists $dictionary{$combined_string}) {
$current_string = $combined_string;
} else {
push @encoded_data, $dictionary{$current_string};
$dictionary{$combined_string} = scalar keys %dictionary;
$current_string = $char;
}
}
push @encoded_data, $dictionary{$current_string} if $current_string ne "";
return \@encoded_data;
}
Python Solution
ch-2.py
def lzw_encode(data: str) -> list[int]:
dict_size = 256
dictionary = {chr(i): i for i in range(dict_size)}
w = ""
result = []
for c in data:
wc = w + c
if wc in dictionary:
w = wc
else:
result.append(dictionary[w])
dictionary[wc] = dict_size
dict_size += 1
w = c
if w:
result.append(dictionary[w])
return result