RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved date calculations and numerical decompositions. (Note that this is open until 21 November 2021.)

Task 1: Jort Sort

You are given a list of numbers.

Write a script to implement JortSort. It should return true/false depending if the given list of numbers are already sorted.

Finally I'm allowed to return a Boolean rather than 1/0! Hurrah!

This is of course Jenn Schiffer's Javascript framework. It must be good, it's got a logo and everything! (More history here.) What's more, with my massive manly and testosterone-soaked brain, I have improved the algorithm.

Which of course isn't the point, and arguably a sort followed by an array comparison would be more in the spirit of the original. But I did get to learn some new language features, so there's that.

The basic idea of this approach is to compare pairs of entries: if an earlier one is higher than a later one, the list isn't sorted and we can return without doing the rest of the comparisons. In Perl (the only language here without explicit Boolean constants) and PostScript I lay that out by hand using array indices:

sub jortsort {
  my $a=shift;
  foreach my $i (1..$#{$a}) {
    if ($a->[$i-1] > $a->[$i]) {
      return 0;
    }
  }
  return 1;
}

/jortsort {
    /a exch def
    /ret true def
    1 1 a length 1 sub {
        dup
        1 sub a exch get exch
        a exch get
        gt {
            /ret false def
            exit
        } if
    } for
    ret
} bind def

In Python I have zip, which lets me merge two iterables into one.

def jortsort(a):

So I make two separately-iterable copies of the list

  j, k = tee(a)

step once through one of them

  next(k,None)

then iterate them in parallel

  for i in zip(j,k):
    if i[0] > i[1]:
      return False
  return True

And in Raku, Ruby and Rust, as well as zip as above I have explicit methods (with wildly different names) for taking overlapping N-sized chunks off a single iterable. (To be fair, Python gets pairwise to do the same thing in 3.10, at least for the case of 2-sized chunks, but I'm running 3.7 here on Debian/oldstable.) Probably one could wrap something like any round them to get rid of the explicit looping entirely, but eh.

sub jortsort(@a) {
  for @a.rotor(2 => -1) -> @i {
    if (@i[0] > @i[1]) {
      return False;
    }
  }
  return True;
}

def jortsort(a)
  a.each_cons(2) { |i|
    if i[0] > i[1] then
      return false
    end
  }
  return true
end

fn jortsort(a: Vec<i32>) -> bool {
    for i in a.windows(2) {
        if i[0] > i[1] {
            return false;
        }
    }
    true
}

Task 2: Long Primes

Write a script to generate first 5 Long Primes.

A prime number (p) is called Long Prime if (1/p) has an infinite decimal expansion repeating every (p-1) digits.

OK, there are clearly two steps here: generate primes, then check the decimal expansion. There's some disagreement in the more general case over whether 2 should count; it and 5 are the only two primes where (1/p) has a non-repeating expansion, but the example sets us right. So it's "full reptend primes" rather than "long-period primes". (By inspection, 3 and 5 won't qualify under either condition, and therefore I start at 7.)

Step one, a reasonably efficient primality tester, since I haven't got round to writing one for these things before. Shown in Python, for compactness, working on the basis that after 2 and 3 every prime number has the form (6k+1) or (6k-1) (because 6k+(0, 2, 3 or 4) will always be divisible by 2 or 3).

(Raku has a built-in probabilistic tester, but with numbers these small I want to be deterministic.)

def is_prime(n):
  if n>2 and n%2==0:
    return 0
  if n>3 and n%3==0:
    return 0
  lim=int(sqrt(n))
  k6=0
  while 1:
    k6+=6
    for t in [k6-1,k6+1]:
      if t <= lim:
        if n % t == 0:
          return False
      else:
        return True

Then it's a matter of finding the length of the decimal expansion. I found some fascinating blog posts on ways of doing this, and ended up using the simple one, optimising it further because I'm always dealing with fractions of the form (1/prime).

I use the 6k±1 technique again to find prime candidates, test them, then get the length of the decimal expansion using Brent's approach of repeated modulus calculation.

Python again, taking a parameter for the number to produce because a mere 5 was boring.

def longprime(n):
  nn=n
  ba=[7]
  k6=6
  while nn>0:
    if len(ba)==0:
      k6+=6
      ba=[k6+1,k6-1]
    b=ba.pop()
    if is_prime(b):
      k=1
      l=0
      while 1:
        k*=10
        l+=1
        k %= b
        if k==1:
          break
      if l==b-1:
        o.append(b)
        nn-=1
  return o

The other languages all work basically the same way.

Full code on github.