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