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.

Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech 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 crime crystal cthulhu eternal cycling dead of winter doctor who documentary drama driving drone ecchi economics en garde espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 essen 2022 essen 2023 essen 2024 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 2021 hugo 2022 hugo 2023 hugo 2024 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards mpd museum music mystery naval noir 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 scala science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge 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