RogerBW's Blog

Perl Weekly Challenge 139: Jort Primes 18 November 2021

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.

Add A Comment

Your Name
Your Email
Your Comment

Your submission will be ignored if any field is left blank, but your email address will not be displayed. Comments will be processed through markdown.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action aeronautics aikakirja anecdote animation anime army astronomy audio audio tech aviation base commerce battletech beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 cycling dead of winter doctor who documentary drama driving drone ecchi economics espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo-nebula reread in brief avoid instrumented life julie enfield kickstarter learn to play leaving earth linux liquor lovecraftiana mecha men with beards museum music mystery naval non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs ruby rust science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1