The Weekly Challenge 022

Sexy Prime Pairs and LZW Compression

Solutions on GitHub

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