RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved a converging sequence and a fraction generator. (Note that this ends today.)

Task 1: Kaprekar Constant

Write a function that takes a 4-digit integer and returns how many iterations are required to reach Kaprekar's constant (6174). For more information about Kaprekar's Constant please follow the wikipedia page.

To summarise, x(n+1) is x(n) transformed thus: take all the digits of a four-digit number (including leading zeroes), sort ascending and descending, assemble those into new numbers, and take the difference.

This will end in either 6174 or 0. In the latter case I return -1.

Python:

Convert a list to a number:

def a2n(a):
  t = 0
  for d in a:
    t *= 10
    t += d
  return t

def kaprekarconstant(a):
  ct = 0
  b = a

Start the loop.

  while b != 6174:

If we hit the other attractor, return an error.

    if b == 0:
      return -1

Extract the digits.

    digits = []
    for _ in range(4):
      digits.append(b % 10)
      b //= 10

Sort them, and make a reversed copy.

    digits.sort()
    stigid = digits.copy()
    stigid.reverse()

Calculate the new value.

    b = a2n(stigid) - a2n(digits)
    ct += 1
  return ct

Since this is a pretty quick process (nothing that converges takes more than 7 cycles to do so) I thought I'd also plot a map of the domain. This is in reading order: top left is 0000, top right is 0099, and so on, and there are certainly patterns to be had here..

• 0 - red
• 1 - orange
• 2 - yellow
• 3 - green
• 4 - blue
• 5 - purple
• 6 - magenta
• 7 - grey
• no convergence - black

Task 2: Unique Fraction Generator

Given a positive integer N, generate all unique fractions you can create using integers from 1 to N and follow the rules below:

• Use numbers 1 through N only (no zero)
• Create fractions like numerator/denominator
• List them in ascending order (from smallest to largest)
• If two fractions have the same value (like 1/2 and 2/4), only show the one with the smallest numerator

So for N=3 I could have nine possibilities (1/1, 2/1, 3/1, 1/2, 2/2, etc.) which after deduplication and sorting would be:

1/3, 1/2, 2/3, 1/1, 3/2, 2/1, 3/1

My goal in this solution was to avoid floating-point divisions, indeed any floating point at all.

My approach is to find a common denominator that could stand in all the possible fractions, and build my list in terms of numerators over that. In this case it would be 6, and I'd generate 6/6, 12/6, 18/6, 3/6, 6/6, etc.

In Rust I can use a BTreeSet, and read off the entries in sorted order. Everything else needs a separate sorting step. Perl:

Library gcd function.

sub gcd($m,$n) {
  while ($n!=0) {
    ($m,$n)=($n,$m % $n);
  }
  return $m;
}

sub uniquefractiongenerator($a) {

Find a common denominator for the factions I'm going to generate. (This could be the GCD of all values from 2 to a but multiplying is just as easy and unlikely to run into trouble at this scale.)

  my $den = 1;
  foreach my $dn (2 .. $a) {
    $den *= $dn;
  }

Generate a set of numerators, one for each conceivable fraction. (Which deals with the deduplication, because 1/1 and 2/2 will both show up here as 6/6.)

  my %f;
  foreach my $d (1 .. $a) {
    my $nd = int($den / $d);
    foreach my $n (1 .. $a) {
      $f{$n * $nd} = 1;
    }
  }
  my @out;

Sort that list.

  foreach my $n (sort {$::a <=> $::b} keys %f) {

Express each value in reduced form.

    my $g = gcd($n, $den);
    my $nn = int($n/$g);
    my $nd = int($den/$g);
    push @out, "$nn/$nd";
  }
  \@out;
}

Full code on github.