The Weekly Challenge 054

Nth Permutation and Collatz Conjecture

Solutions on GitHub

Task 1: Nth Permutation

Write a script to accept two integers $N and $K. It should then return the $K-th permutation sequence of numbers from 1 to $N.

Example Output

Input: $N = 3, $K = 4 Output: 231

Logic

Generate all permutations of numbers from 1 to $N, sort them lexicographically, and select the $K-1-th item (0-indexed).

Perl Solution

ch-1.pl

use Algorithm::Permute; sub get_nth_permutations { my ( $n, $k ) = @_; my @numbers = ( 1 .. $n ); my $p = Algorithm::Permute->new(\@numbers, $n); my @all_perms; while (my @res = $p->next) { push @all_perms, join("", @res); } my @sorted_perms = sort @all_perms; return $sorted_perms[$k-1]; }

Python Solution

ch-1.py

from itertools import permutations class NthPermut: def get_nth_permutations(self, n_integers: int, k_permutation: int): nth_perm = list(permutations(range(1, n_integers+1)))[k_permutation-1] return nth_perm

Task 2: Collatz Conjecture

Write a script to generate the Collatz sequence for 23, showing it is 16 elements long. Additionally, find the number under 1,000,000 that has the longest sequence length.

Example Output

Collatz sequence for 23: 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1 (Length: 16)

Logic

Collatz logic: if current number is even, divide it by 2. If odd, multiply by 3 and add 1. Repeat until it reaches 1. We can cache the lengths of sub-sequences to optimize calculation for numbers up to 1,000,000.

Perl Solution

ch-2.pl

sub get_next_sequence { my $seq_pos = shift; return 0 if $seq_pos == 1; return 3 * $seq_pos + 1 if $seq_pos % 2 == 1; return int( $seq_pos / 2 ); } sub single_sequence { my $seq_pos = shift; my @seq; while ( $seq_pos > 1 ) { push @seq, $seq_pos; $seq_pos = get_next_sequence($seq_pos); } push @seq, 1; return \@seq; }

Python Solution

ch-2.py

class Collatz: def get_next_sequence(self, seq_pos: int): if seq_pos % 2 == 0: return seq_pos // 2 return 3 * seq_pos + 1 def single_sequence(self, seq_pos: int): seq = [] while seq_pos > 1: seq.append(seq_pos) seq_pos = self.get_next_sequence(seq_pos) seq.append(1) return seq