The Weekly Challenge 023

Forward Difference and Prime Decomposition

Solutions on GitHub

Task 1: Forward Difference

Write a script to calculate the forward difference of a given list of numbers. The first-order difference is calculated as: $D_1(i) = A(i+1) - A(i)$. Subsequent orders are calculated recursively from the previous order.

Example Output

For list (5, 9, 2, 8, 1, 6) and order 1: 4, -7, 6, -7, 5 For list (5, 9, 2, 8, 1, 6) and order 2: -11, 13, -13, 12

Logic

Iterate through the array and calculate the difference between each element and its predecessor. For higher order differences, repeat this calculation $n$ times where $n$ is the requested order.

Perl Solution

ch-1.pl

sub forward_difference { my ($order, $nums_ref) = @_; my @nums = @$nums_ref; # Check if valid order is passed die "Order should be a positive integer\n" if $order < 1; my @diff = @nums; # Calculate the nth order forward difference series for (my $i = 1; $i <= $order; $i++) { my @temp = (); for (my $j = 0; $j < $#diff; $j++) { push @temp, $diff[$j+1] - $diff[$j]; } @diff = @temp; } # Return the final series return @diff; }

Python Solution

ch-1.py

def forward_difference(order, nums): # Check if valid order is passed if order < 1: raise ValueError("Order should be a positive integer") diff = nums # Calculate the nth order forward difference series for i in range(order): temp = [] for j in range(len(diff) - 1): try: temp.append(diff[j + 1] - diff[j]) except TypeError: raise TypeError(f"not a number") diff = temp # Return the final series return diff

Task 2: Prime Decomposition

Write a script to compute the prime factors of a given integer. For example, the prime decomposition of 228 is [2, 2, 3, 19].

Example Output

prime decomposition of 228 is: 2, 2, 3, 19 prime decomposition of 131 is: 131

Logic

We divide the number by the smallest possible prime factor (starting with 2). We keep dividing as long as it divides cleanly. If it does, we record the factor and update the number. If not, we increment the divisor. We can optimize this by stopping early when the square of the divisor exceeds the remaining number, adding the remaining number as the final prime factor if it's greater than 1.

Perl Solution

ch-2.pl

sub prime_decomposition { my $n = shift; # Check if number is less than 2 if ($n < 2) { die "Number should be greater than or equal to 2\n"; } my @factors = (); my $d = 2; # Divide the number by prime factors while ($n > 1) { while ($n % $d == 0) { push @factors, $d; $n /= $d; } $d++; if ($d * $d > $n && $n > 1) { push @factors, $n; last; } } return @factors; }

Python Solution

ch-2.py

def prime_decomposition(n: int) -> List[int]: if n < 2: raise ValueError("Number should be greater than or equal to 2") factors = [] d = 2 # Divide the number by prime factors while n > 1: while n % d == 0: factors.append(d) n //= d d += 1 if d * d > n and n > 1: factors.append(n) break return factors