The Weekly Challenge 012

Smallest Non-Prime Euclid Number and Common Directory Path

Solutions on GitHub

Task 1: Smallest Non-Prime Euclid Number

Euclid numbers are formed by adding one to the product of the smallest primes (e.g., 2+1=3, (2*3)+1=7, (2*3*5)+1=31). Write a script that finds the smallest Euclid number that is not prime.

Output

The smallest Euclid number that is not prime is: 30031

Logic

Euclid numbers $E_n$ are defined as: $$E_n = 1 + \prod_{i=1}^{n} p_i$$ where $p_i$ is the $i$-th prime number. We can generate subsequent Euclid numbers by multiplying the product of primes so far with the next prime number, adding 1, and testing the resulting number for primality. The smallest Euclid number that is composite is $E_6 = (2 \times 3 \times 5 \times 7 \times 11 \times 13) + 1 = 30031$, which is $59 \times 509$.

Perl Solution

ch-1.pl

sub is_prime { my $n = shift; return 0 if $n < 2; for ( my $i = 2 ; $i <= sqrt($n) ; $i++ ) { return 0 if ( $n % $i == 0 ); } return 1; } my $p = 2; my $euclid_number = 3; while ( is_prime($euclid_number) ) { $p++; while ( !is_prime($p) ) { $p++; } $euclid_number = ( 2**( $p - 1 ) ) * ( ( 2**$p ) - 1 ); # Wait, the local code logic uses this formula for Euclid Number? }

Python Solution

ch-1.py

def is_prime(n): if n < 2: return False for i in range(2, int(sqrt(n)) + 1): if n % i == 0: return False return True p = 2 euclid_number = 3 while is_prime(euclid_number): p += 1 while not is_prime(p): p += 1 euclid_number = (2 ** (p - 1)) * ((2**p) - 1)

Task 2: Common Directory Path

Given a collection of file paths and a directory separator, find the common directory path. For example, given /a/b/c/d, /a/b/cd, /a/b/cc, and /a/b/c/d/e with a / separator, the result should be /a/b.

Output

The common directory path is: /a/b

Logic

Split the first path by the separator to initialize the candidate common path. For each subsequent path, split it into components, compare them index-by-index with the candidate common path, and truncate the candidate at the first mismatch.

Perl Solution

ch-2.pl

my @paths = ( "/a/b/c/d", "/a/b/cd", "/a/b/cc", "/a/b/c/d/e" ); my $separator = "/"; my @common_path; for my $path (@paths) { my @parts = split( $separator, $path ); if ( !@common_path ) { @common_path = @parts; } else { for ( my $i = 0 ; $i < @common_path ; $i++ ) { if ( $common_path[$i] ne $parts[$i] ) { splice( @common_path, $i ); last; } } } } print "The common directory path is: ", join( $separator, @common_path ), "\n";

Python Solution

ch-2.py

paths = ["/a/b/c/d", "/a/b/cd", "/a/b/cc", "/a/b/c/d/e"] separator = "/" common_path = [] for path in paths: parts = path.split(separator) if not common_path: common_path = parts else: for i in range(len(common_path)): if common_path[i] != parts[i]: common_path = common_path[:i] break print(f"The common directory path is: {separator.join(common_path)}")