# 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.)

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 > i:
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 > @i) {
return False;
}
}
return True;
}

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

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

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=
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.