This task allowed me to revisit a technique that I was recently considering writing about; using patterns of output of idioms to recognize visualize the decomposition.

Six is three, three is five, five is four, four is magic.

- Comma-separated ==> build a list, then join() on comma.
- All elements are "Foo is Bar" ==> map with interpolation or map with join, with input of pairs or two-element lists.
- First element of each list is the second element of prior list ==> rotor(), or Z with an initial .skip.
- Each element the list is determined by the prior element ==> Seq via
`...`

At the bottom of the code, I detail some quirks in the language. For a BASIC implementation, YaBasic works fine; I may even use it for an early introduction to programming with my grandchildren. "If it was good enough for me,...!"

For my own use, I never expect to inflict any variant of BASIC on myself again.

Things I *really* missed in YaBasic:

- Returning arrays from sub (complex returns)
- Dynamic arrays
- Interpolation in strings
- TAP test harness
- Simple array equality with
`eqv`

- Array initialization and array assignment
- Initializing while declaring a local variable
- Block-scoping of variables
- Zero-based array indexes
- Having a scalar type that can handle strings and numbers.
- Having a array type that can handle strings and numbers.
- Code as a parameter, and
`map()`

- Shrinkable arrays. (Can never reduce the size on an array?, Oh wait, you can. But only via
`split`

???) - Empty arrays. You cannot have an initial zero-element array expanded to non-zero, which limits the usefulness of fake-push.
- Postfix
`if`

; even though YaBasic has a one-line form, it give no early indication that you are using it, so your eyes keep reading to end-of-line, and hopefully you see that`then`

is missing.

You can tell I missed these things, from all the code I wrote to emulate them.

I am the author of one of the three Raku solutions to this problem, and had studied the other two extensively (12 years ago).

To make up for it, I tried to do some clever things by updating the FP solution with `:k`

and `R+`

into a one-liner, and by solving the broader problem of possible equilibrium at half-way points and finding smallest imbalances.

]]>It's a Human insult. It's devastating. You're devastated right now. -- audio Michael, "The Good Place"

(Still editing)

]]> TWC Task #1 - Fortunate NumbersProduce first 8 Fortunate Numbers (unique and sorted).

Find the period of the 3rd Pisano Period.

(or maybe a chatchka in a haystack),

and delight in some lazy CPAN comfort. ]]> TWC Task #1 - Missing Permutation

Find all permutations missing from a list.

I have

`snip`

ped most of the task permutations to make the code fit better in the blog post.I don't want to write my own permutation code

**again**.Raku has built-in

`.permutations`

method, and`(-)`

set-difference operator.Perl has several CPAN modules for permutations;

`List::Permutor`

is the first one Google returned, and its`->next`

method allowed me to write a loop that was different than my Raku solution.Python has

`Set`

s, and the`itertools`

library handles permutations. itertools has*lots*of features that I miss when working outside of Raku, but they cannot be*combined*as nicely as Raku's, due to the`basic(underlying(Python(function(call(syntax()))))`

.

The partial list of juggled letters is in `@in`

.

```
my @in = <PELR PREL ...snip...
```

Take the first word; we could have used any of them.

With no argument, `.comb`

splits into a list of single characters.

`.permutations`

gives all the possible rearrangements of those characters.

The `».`

makes a *hyper* method call that will be run on each item in the list of permuted characters, `join`

ing them back into words.

```
my @all = @in[0].comb.permutations».join;
```

When we do a set operation on a List, it is automatically converted to a Set.

`(-)`

is the ASCII version of the `set difference`

operator; it returns a Set of items present in the left-hand Set that are absent from the right-hand Set.

Iterating over the resulting Set gives us `Pair`

objects, where the `.value`

is always `True`

, and the `.key`

is the part we are interested in.

```
say .key for @all (-) @in;
```

The Perl version of Raku's `Set`

is a hash,

initialized via `my %h = map { $_ => 1 } @stuff;`

.

```
use List::Permutor;
my @in = qw<PELR PREL ...snip...>;
my %in_set = map { $_ => 1 } @in;
my $permutor = List::Permutor->new( split '', $in[0] );
while ( my @letters = $permutor->next() ) {
my $word = join '', @letters;
say $word if not $in_set{$word};
}
```

The Python code mirrors the Perl solution. When given only a single string, `list`

breaks it into characters.

In hindsight, I really should have named the last variable `word`

instead of `s`

.

```
from itertools import permutations
input_words = "PELR PREL ...snip...".split()
input_set = set(input_words)
for i in permutations(list(input_words[0])):
s = "".join(i)
if s not in input_set:
print(s)
```

Compute the first 10 distinct *prime* Padovan Numbers.

- I don't want to write my own
`is_prime()`

code**again**.

There were several ways to write the code block. I chose one that highlights `$c`

being requested then deliberately unused.

`.squish`

only suppresses *consecutive* duplicates, so it works efficiently with lazy lists.

```
constant @Padovan = 1, 1, 1, { sink $^c; $^a + $^b } ... *;
say @Padovan.grep(&is-prime).squish.head(10);
```

I was very happy to discover List::Lazy, which make easy both the generation of the Padovan Numbers, and filtering them for primes.

It was going to be more trouble than it was worth to make a version of Raku's `.squish`

that would work with `List::Lazy`

, so I used the foreknowledge that there is exactly one duplicate, and just called `uniq`

on the 10+1 numbers returned by `->next`

.

```
use List::Util qw<uniq head>;
use List::Lazy qw<lazy_list>;
use ntheory qw<is_prime>;
my $Padovan = lazy_list {
push @$_, $_->[-2] + $_->[-3];
shift @$_;
} [1, 1, 1];
my $prime_pad = $Padovan->grep( sub { is_prime($_) } );
say join ', ', uniq $prime_pad->next(11);
```

I am pleased with the brevity of the `Padovan()`

generator.

`head()`

is from an `itertools`

recipe; it is not my own code.

Comparing the final `print`

line to the second line of the Raku code makes me wish for Raku's flexibility of choosing method calls vs function calls.

```
from sympy import isprime
from itertools import islice
def Padovan():
p = [1, 1, 1]
while True:
p.append(p[-2] + p[-3])
yield p.pop(0)
def squish(a):
last = None
for i in a:
if i != last:
yield i
last = i
def head(n, iterable):
return list(islice(iterable, n))
print(head(10, squish(filter(isprime, Padovan()))))
```

]]>Primes, Primes, everywhere a Prime.

Making all the Integers, alone or combined

Sieve N, to the square root.

Can't you see its Prime?

-- audio by the Five Man Electric Band

(Placeholder; still editing)

In which we see that you don't need *all* the Fibs, and have trouble turning 21.

Given an input $N, generate the first $N numbers for which the sum of their digits is a Fibonacci number.

(i.e. Generate OEIS A028840)

(i.e. Generate OEIS A287298)

Given a number base, derive the largest perfect square with no repeated digits and return it as a string. (For base>10, use ‘A’..‘Z’.)

`e`

, and realize that `first`

implies an ordering.
]]>
TWC Task #1 - Eban Numbers
Eban: A number that has no letter `e`

when spelled in English.

Since the `Lingua::EN::Numbers`

exists for both Perl and Raku, the solutions are just expanded one-liners. Both output:

```
2 4 6 30 32 34 36 40 42 44 46 50 52 54 56 60 62 64 66
```

```
use Lingua::EN::Numbers;
put grep *.&cardinal.contains('e').not, 0..100;
```

```
use Modern::Perl;
use Lingua::EN::Numbers qw<num2en>;
say join ' ', grep { !(num2en($_) =~ /e/) } 0..100;
```

Note: I missed using Perl's `!~`

operator, which would have been clearer than negating the whole expression: `grep { num2en($_) !~ /e/ }`

```
________ ________
³√ 𝑎 + 𝑏√𝑐 + ³√ 𝑎 - 𝑏√𝑐 == 1
```

Most of my calculations are in the README.

Exact wording of the task is "Write a script to generate

**first**5 Cardano Triplets".The order that triplets occur depends on the method you use to search for them. Therefore, if more than one method exists to search for Cardano triplets, the output of all the participants might not match each other.

*Several*methods exists to search for Cardano triplets.`a`

,`b`

,`c`

are independent and not interchangeable; they each play a different role in the equation. So, we cannot use the common technique of "for a = 1..Inf", then have inner loops that bound`b`

and`c`

to`<= a`

, or we risk missing some triplets.Whenever searching for N-tuples (in this case, triples) that satisfy some condition, a good approach is to see if one piece of the tuple can be calculated from the other pieces. If so, you can remove a loop!

`c`

can be calculated from`a,b`

.

WolframAlpha says that

`Solve[CubeRoot[a + b Sqrt[c]] + CubeRoot[a - b Sqrt[c]] == 1, c]`

has the solution`c = (8a - 1)(a + 1)² / 27b²`

.

So, if`(8a - 1)(a + 1)²`

is evenly divisible by`27b²`

, then we have found a triplet*and*computed`c`

.All triplets must have

`𝑎 ≡ 2 𝑚𝑜𝑑 3`

, which is the same as saying`a = 3k+2`

where`k`

is a positive integer.

(Stated halfway through Jean Marie's StackExchange answer to Parametrization of Cardano triplet)Combining the last two points, we can replace

`a`

with`3k+2`

in`(8a - 1)(a + 1)²`

, and simplify it to`27(8k + 5)(k + 1)²`

.

Since that has a factor of`27`

, and every triple must be evenly divisible by`27b²`

, then*every*valid`a`

(that is,`𝑎 ≡ 2 𝑚𝑜𝑑 3`

) has a least one triple, where`b=1`

. If`a`

has square divisors, then there are multiple triples for that`a`

.A straightforward coding of

`is_Cardano_triplet()`

uses floating-point math then checks for an equality, which is the classic FP bug. We must compare to some tolerance, so that we do not exclude a valid triple.say "Bad!" if sqrt(3)**2 != 3' # Output: Bad!

Since the math involves more than just division, even Raku's invisible Rat(s) will not save us;

`($r - 1).abs < $some_tolerance`

, or maybe`$r =~= 1`

.Raku's is-almost-equal-to operator,

`=~=`

uses the current`$*TOLERANCE`

setting, whose default of 1e-15 is too strict to find some triplets.

(Aside: if you do something like`my $*TOLERANCE = 1e-14;`

and*omit*the minus sign, then suddenly*every*triple is a Cardano triple, because now one is almost equal to a trillion. Blew my mind until I saw my error.)I found it concise to use two uncommon techniques:

`find_Cardano_triplet()`

and`is_Cardano_triplet()`

both take a single argument of a triplet (notice the doubled parenthesis in the`sub`

declarations), and return either a complete triplet or Nil. You might expect`find_Cardano_triplet()`

to return`c`

,`is_Cardano_triplet()`

to return a`Bool`

and both to take 3 arguments. This allowed a slick combining of candidate sources and filters/generators via`map`

and`grep`

.While I used

`$m % $n`

in the Perl code to check for divisibility, Raku's Rat types always reduce to GCD, so I can just divide and then examine`.denominator == 1`

. The`.narrow`

method is needed so that I don't return a`Rat`

where one would expect an`Int`

.Similar to using Unicode superscript numerals to express exponents (

`$n²`

), you can use Unicode "vulgar fractions" in Raku. This was convenient for cube roots, although special handling was needed for negatives.`say [15 * ⅖, 27 ** ⅓]; # Output: [6 3]`

`sub cbrt (\n) { n.sign * n.abs ** ⅓ }`

# Handles positives and negatives uniformly.While Raku provides the Cross operator (and meta-operator), it does not work usefully with more than one infinite list, so we can only use it (or the equivalent three nested

`for`

loops) if we*already*know the answer to the problem. I have always disliked this limitation (across many problems), but I did use the pre-knowledge this time for comparison, as constants`@fixed_X_triplets`

and`@fixed_X_doublets`

with`1..21`

ranges.I invented (probably

*rediscovered*) an algorithm to iterate over N-tuple cross-products of N infinite lazy lists, never generating (or even having to check for) duplicates. It works well in any language with generators, and is a good fit here, but the ordering that it produces the tuples looks irregular to humans.

I expanded the output count from 5 triplets to 6, to better show the differences in the orderings. Here are the 4 lines that my program produces (plus one from elsewhere).

```
(2 1 5) (5 2 13) (17 18 5) (17 9 20) ( 8 3 21) (11 4 29) # 1
(2 1 5) (5 2 13) ( 8 3 21) (17 9 20) (17 18 5) # 2
(2 1 5) (5 1 52) ( 5 2 13) ( 8 1 189) ( 8 3 21) (11 1 464) # 3
(2 1 5) (5 1 52) ( 8 1 189) (11 1 464) (14 1 925) (17 1 1620) # 4
(2 1 5) (5 2 13) ( 8 3 21) (11 4 29) (14 5 37) (17 6 45) # 5
```

`triplet_generator().grep( &is_Cardano_triplet)`

"smallest" for minimizing`max(a,b,c)`

`@fixed_X_triplets.grep( &is_Cardano_triplet)`

Notice that it omits the 6th triplet, because the (1..21) that was just enough for 5; it "ran out" of triplets before finding the 6th!`@fixed_X_doublets.map(&find_Cardano_triplet)`

`a,b`

can be smaller because calculated`c`

is not restricted by a range. This one will "run out" too.`(^Inf).map({find_Cardano_triplet( (3 * $_ + 2, 1), )})`

Locks`b=1`

, and walks through all the`a=3k+2`

since we know they all work with`b=1`

, finding the correct`c`

. This is reasonable; you would get the same answer from a big enough triple-loop if`b`

was the outer variable,`find_Cardano_triplet`

would return`Nil`

for all the`a`

that were not`𝑎 ≡ 2 𝑚𝑜𝑑 3`

and therefore be suppressed.This line does not come from my challenge solution; Flavio Poletti adapted Jean Marie's complete answer (that I only managed half of, above) to derive a formula that, given

`b`

, produces the smallest-working`a`

and its corresponding`c`

. Splendid! And also, yet*another*ordering, with a reasonable take on "first 5", that gives different output from any of my four. The cost in finding`(5 2 13)`

so easily, is never seeing other`b=2`

like`(11 2 116)`

.`say (1..Inf).map({ 3 * $_ - 1, $_, 8 * $_ - 3 }).head(6)`

Inspired by Flavio, I wrote this just before posting. It was experimentally arrived-at (

`doublet_generator+find_Cardano_triplet|sort`

, OEIS), not algebraically derived, but it produces correct output (with tolerance=1e-12) for the first 1000 triplets, locking`c=5`

.say (1..Inf).map(-> \n { (15 * (2 * n - 1)² + 1)/8, (2 * n - 1)*(5 * n² - 5 * n + 2)/2, 5 }).head(6)

Output: ((2 1 5) (17 18 5) (47 80 5) (92 217 5) (152 459 5) (227 836 5))

Six first 5's, all for valid interpretations of "first". Surprising, and Fun!

I simply translated `find_Cardano_triplet`

from Raku, and called it with `a=0..4, b=1`

for the most humorous definition of "first 5".

```
sub find_Cardano_triplet ( $x, $y ) {
my $m = ($x + 1)**2 * (8*$x - 1);
my $n = 27 * $y * $y;
return if $m % $n;
return [ $x, $y, $m / $n ];
}
say sprintf('%3d %3d %3d', @{$_}) for map { find_Cardano_triplet( (3 * $_ + 2, 1), ) } 0..4;
```

Output is the same triples as #4 in the Raku section.

]]>"Left-truncatable prime" is not fully defined by the task; are leading zeros valid?

e.g. 103 -> 03 -> 3 ; all are prime, but is `03`

considered a "number"?

**UPDATE**: SF.pm's Raku Study Group just pointed out that task description *does* *say* "contains no 0", so the task *was* fully defined, and I had no need for the "filter" half of the solutions below. Mea culpa!

OEIS has separate pages for each definition, but both start with:

(2, 3, 5, 7, 13, 17, 23, 37, 43, 47):

A033664 …, 53, 67, 73, 83, 97, 103, 107, 113, …

A024785 …, 53, 67, 73, 83, 97, 113, …

Since one definition is more easily written as a filter, and the other definition is best written as a generator, I wrote both.

My Raku program starts with the "filter" approach:

```
sub is-left-truncatable-prime ( UInt \N --> Bool ) {
return (0 ..^ N.chars) # Start of each substring
.map( { N.substr($_) }) # All left-truncated substrings
.first({ .is-prime.not }) # Find the first non-prime
.defined.not; # If no non-primes, then True
}
constant @LTP_A033664 = grep &is-left-truncatable-prime, ^Inf;
```

The `.first`

method, combined with the laziness of the `.map`

method, allows an early `return`

without `.substr`

having to generate every single substring.
Rephrasing to use `.all`

is only *slightly* clearer, so I used `.first`

.

The "generator" approach starts with the single digit primes as the first "generation", and pre-pends 1..9 to each element of gen#1 (and filters out non-primes) to create all-double-digit gen#2. Gen#3 will all be triple-digits, and so on.

```
my @LTP_A024785 = lazy gather loop {
state @current_gen = grep &is-prime, ^10;
.take for @current_gen;
@current_gen = grep &is-prime, ((1..9) X~ @current_gen);
}
```

Since each number in a generation has the same number digits, and the first generation is in numeric order, each subsequent `(1..9) X~ @current_gen`

generation will also be in order.

Both arrays are lazy, so they get their elements populated on demand. Final output is just:

```
put @LTP_A033664.head(20);
put @LTP_A024785.head(20);
2 3 5 7 13 17 23 37 43 47 53 67 73 83 97 103 107 113 137 167
2 3 5 7 13 17 23 37 43 47 53 67 73 83 97 113 137 167 173 197
```

My Perl program is just a conversion of the Raku, with adaptations to loosely replace the laziness that Perl lacks.

The ntheory (Number Theory) module has `is_prime`

, which saves me much code.

Some obvious problems:

- Not only do we need to scan all 2-combinations (O²) of a list, we also have to scan the list of pents to find the difference and the sum (O³ and bigger, unless we binary search and/or hash).
- Unless we pre-build the list to a pre-known limit (which we could only do if we already knew the answer), then at the time that we want to check
`A+B`

for presence in the list of pents, the value will not*exist*in the list yet. - We need all 2-combinations, and Raku has a
`.combinations`

method that we can invoke with`(2)`

, but it will not work with the lazy infinite list that idiomatic for`@pents`

.

If we *did* already know how big to pre-build the pents, then the solution would be simple:

```
constant @pents = map { $_ * (3 * $_ - 1) div 2 }, 1..*;
my %p = @pents.head(2400).Set;
say @pents.head(2400).combinations(2).first: {
%p{ [+] .list } and
%p{ [R-] .list }
};
```

I don't want to do that.

If we "solve" the pent equation of `n(3n-1)/2 = P`

via quadratic formula (a=3,b=-1,c=-2P), we can write a `is_pentagon_number`

sub, which would solve the first two problems!

```
sub is-pentagon-number ( \p ) {
my \inner = 24 * p + 1;
my \near_root = inner.sqrt.round;
return near_root ** 2 == inner
&& near_root % 6 == 5
}
```

This would work perfectly.

I chose not to do that, either.

Instead, let's call the sum of the two pents "A", and the difference "D". Then re-arrange like so:

```
# Where A,B,C,D are all pentagonal numbers:
# B + C == A , B - C == D Original problem statement
# C == A - B , B - C == D Rearranged as two differences
# C == A - B , B-(A-B)==D (C,D), expressed only in A and B
```

So, if we find any two pentagonal numbers A,B where A-B is pentagonal and B-(A-B) is pentagonal, then we have a solution. The desired numbers will be the inner two: (B,C).

With this reorganization, we will always be "looking backwards" into parts of `@pent`

that have already been generated. The cost will be in generating all the way to A; a solution using `is-pentagon-number`

would only need to generate to B.

My Raku program uses `for @pents.kv`

as a outer loop, and `for @pents.head(i)`

as the inner loop, to replicate the disallowed `.combinations(2)`

.

```
sub find-first-plus-and-minus-pentagon_numbers ( ) {
constant @pents = map ->\n { n *(3*n - 1) div 2 }, 1..*;
my %p;
for @pents.kv -> \i, \A {
%p{A} = 1;
for @pents.head(i) -> \B {
my \D = A - B;
my \C = B - D;
return B, C if %p{C} and %p{D};
}
}
}
put find-first-plus-and-minus-pentagon_numbers();
```

The three body lines of the inner loop could be replace with one line (`return B, C if %p{A - B} and %p{B - (A - B)}`

), and then the whole inner loop could become a `return … with first {…}`

statement, but then I suspect it would "spark joy" in no one.

Aside: SF.pm's Raku Study Group just pointed out that the `constant`

line uses a sigil-less `n`

, which means it gets defined as `-> \n`

, which confusingly looks like a *newline* character. Good point!

My Perl solution needed almost no structural changes from the Raku, because the lazy generation of the pents can just be appended at the same pace as the outer loop.

```
sub find_first_plus_and_minus_pentagon_numbers ( ) {
my @pents;
my %p;
for ( my $i = 1 ; ; $i++ ) {
my $A = $i * (3*$i - 1) / 2; # Pentagon number
for my $B (@pents) {
my $D = $A - $B;
my $C = $B - $D;
return $B, $C if $p{$C} and $p{$D};
}
$p{$A} = 1;
push @pents, $A;
}
}
say join ' ', find_first_plus_and_minus_pentagon_numbers();
```

*Five is right out.* -- Monty Python and the Holy Grail

Task 1: 10001st Prime Number - One-liners (expanded) in Raku and Perl.

Task 2: Curious Fraction Tree - Solutions in Raku and Perl (with 200+ tests), and another Perl solution using a CPAN module.

]]> TWC Task #1, 10001st Prime NumberMy Perl program is a 3-line version of this one-liner:

```
perl -Mntheory=nth_prime -wE 'say nth_prime(10_001)'
```

The ntheory (Number Theory) module has many routines that would solve the problem. `nth_prime`

is the most direct.

```
constant @primes = (2, 3, 5, 7 ... *).grep(&is-prime);
say @primes.skip(10_000).head;
```

That first line creates a "constant" lazy infinte array of primes. It is constant in the sense that the program code cannot alter a value, but it is lazy, so the elements of `@primes[0..N]`

are not generated until something tries to use `@primes[N]`

. All the prior elements are cached and delivered on request without recalculation. If a higher element is requested later in the program's execution, then the generation of `@primes`

elements will resume where it left off.

I studied the patterns of parent->children and child->parent, slung some code to solve the task, wrote more to extend the tree, and searched OEIS and the Web.

The "Curious Fraction Tree" is properly named the "Calkin-Wilf Tree", but is easily confused with the 150+year-earlier "Stern-Brocot tree".

(by "easily confused", I mean that I confused them. Also confused C-W with Kepler's tree of harmonic fractions.)Coolest illustration of the C-W tree: https://www.jasondavies.com/calkin-wilf-tree/

C-W tree covers every rational number.

(Infinite in two dimensions? No big deal, I can do that easily via diagonals; we just get lots of duplicates.)- C-W tree does not need diagonals, and
*never*has duplicates.

- ...I can't do that.
- Apparently, I can't even understand the proof!

- ...I can't do that.

- C-W tree does not need diagonals, and
Raku has rational numbers as a built-in type: Rat. Rat is auto-normalizing (3/6 becomes 1/2), has .numerator and .denominator methods, and a .nude method to get a list of both (Nu/De) at once.

If you follow a fraction's C-W lineage all the way back to (but not including) the 1/1 root, reverse that lineage to be root-to-descendant, and map each fraction along-the-way as proper-fraction==L, improper-fraction==R (i.e. more than 1 or less than 1), then you get a navigation tree of which branch to follow, all the way to the original number. e.g. 8/19 has the navigation of RLRRLL.

- To a percussionist, those navigations look just like snare drum rudiments and exercises: 'RLRRLL' is a single paradiddle-diddle
- Those navigations can translate back-and-forth (if we are careful) to binary numbers, and so to plain decimal integers. (More on this when I discover the Curious Module below.)

- To a percussionist, those navigations look just like snare drum rudiments and exercises: 'RLRRLL' is a single paradiddle-diddle
Exploring the tree via regular patterns of L(s) and R(s) finds some interesting properties:

- 'LLLLLL'... and 'RRRRRR'... are the left and right edges of the tree, with top or bottom == 1.

1/101 # 'L' x 100

101/1 # 'R' x 100 - R,'LLLLLL'... and L,'RRRRRR'... are the two center-most numbers ("framing" the half-way point) on any level after the first. Top or bottom will be '2'.
- LR,'LLLLLL'... and LL,'RRRRRR'... frame the quarter-way point;

RR,'LLLLLL'... and RL,'RRRRRR'... frame the three-quarter-way point on any level after the second. Top or bottom will be '3'. - (and so on, for row divisions by 8, 16, 32, ...)
- Single-bit set (or unset) produce the top (or bottom) sequence 2,3,4...(size+1) as we slide the position of the bit:

2/31 # RLLLLLLLLLLLLLLL

3/44 # LRLLLLLLLLLLLLLL

4/55 # LLRLLLLLLLLLLLLL

...

31/2 # LRRRRRRRRRRRRRRR

44/3 # RLRRRRRRRRRRRRRR

55/4 # RRLRRRRRRRRRRRRR - Alternating L and R reaches the 1/3-point and 2/3-point in a row, producing approximations of the Golden Ratio φ ("The most irrational number"; 1.618033988749...), and its inverse|conjugate.

These numbers are all ratios of successive Fibonacci numbers.

e.g. LRLRLRLRLRLRLRLRLRL => 6765/10946 == F(20)/F(21) == 0.618034

- 'LLLLLL'... and 'RRRRRR'... are the left and right edges of the tree, with top or bottom == 1.

After satisfying my urge for percussive exploration, I formalized the findings into a file of tests that the Perl and Raku solutions could both access, then wrote utility routines to help anyone who wants to explore more deeply.

I later found mention in a paper (URL?) that, unlike the Stern-Brocot tree, the C-W tree can be navigated directly *across* a row, also moving from the end of one row to the start of the next row. I added the calculation to the utility routines as `next-Calkin-Wilf-neighbor.

After *all* *that*, I found a Perl module on CPAN that solves the problem: Math::PlanePath::RationalsTree.
This lead to a proof-of-concept one-liner, that calculates the parent but not the grandparent:

```
perl -MMath::PlanePath::RationalsTree -wE 'my $CW = Math::PlanePath::RationalsTree->new( tree_type => "CW" ); say join "/", $CW->n_to_xy( $CW->tree_n_parent( $CW->xy_to_n(@ARGV) ) );' 4817 5410
```

I cloned my original Perl solution and replaced my algorithm with calls to the module, as ch-2*via*module.pl, so I could be sure that the module could play in my drumming circle.

It worked perfectly, except where it didn't. Of 202 tests, only 166 passed.

Looking deeper into the 36 test failures, the problem became obvious. The module handles all types of rational trees with the efficient method of translating the LR navigation into zeros and ones to make (when decoded from binary) an integer. That integer represents the linear position of the rational.

```
$ perl -MMath::PlanePath::RationalsTree -wE 'my $CW = Math::PlanePath::RationalsTree->new( tree_type => "CW" ); say "N=$_ : tree_element=", join "/", $CW->n_to_xy( $_ ) for 1..5;'
N=1 : tree_element=1/1
N=2 : tree_element=1/2
N=3 : tree_element=2/1
N=4 : tree_element=1/3
N=5 : tree_element=3/2
```

The tree gets *twice* as big for every row (level?) you go down. Exponential growth! Around row 64, N will be around 2^64, and overflow the integer size of 64-bit Perl. All the tests below N=2^64 passed, as did some beyond that point (vagaries of rounding?), but you cannot rely on accuracy past that point. E.g.: finding the parent of "1/65" gives the wrong answer using the "convert to N" method, while 1/10001 and beyond all work with the direct calculations in Perl and Raku. (To be fair, Raku starts having problems past level 90 when drilling down along the Golden Ratio, due to Rat auto-collapsing into a more efficient Num. This could be prevented by using FatRat.)

Of note in my Raku solution :

- Clean separation of types: Calkin-Wilf-tree-parent() takes and returns Rat, and task2() takes and returns Str.
- Symmetry: task2() splits on slash at the start, and joins on slash at the end.
- Sequence: @lineage is a lazy Seq going all the way back to the root, generated by repeated calls to get the parent of the last result. This "keep feeding the result back in as the next argument" (iterated function) is a common-enough pattern that Raku directly supports it via the
`...`

or "sequence" operator. Since the Seq is lazy, and we only ask for the first two ancestors (via .head), only two are calculated. - Contain to Name: Placing the difference in its own variable allows not only DRY in the return statement, but also the symmetry between the two possible results. I particularly like how
`diff`

and`-diff`

read, compared to`n-d`

and d-n. (If I had not already committed, I might change`diff/d`

to`+diff/d`

to call attention the sign change). - multi sub MAIN clearly shows the two ways to run the program.

Of note in my Perl solution :

- Clean separation of types: Calkin
*Wilf*tree_parent() takes and returns a two-element [numerator,denominator] arrayref, and task2() takes and returns a "numerator/denominator" string. - map==grep++ :
`map`

is also serving as`grep`

via the empty-list trick; if no non-whitespace characters exist in the line, then`map`

produces*nothing*for that line, not even`undef`

; the line is skipped. - /r : Using the
`r`

modifier (part of s{...}{...}msxr) on the substitution lets me return a changed copy, instead of modifying the original.

Kudos to manwar, and thanks to the whole team at The Weekly Challenge!

Elwood: What kind of music do you usually have here?

Claire: Oh, we got both kinds. We got Country *and* Western.

*Rawhide!*

Task 1: Swap Nibbles - basic and extended solutions in Raku and Perl.

Task 2: Sequence of symbols 123 without adjacent 1’s. Solutions in Raku and Perl, then a radically different approach that I would have never discovered in anything but Raku.

]]> Special thanks to TheYeti of CodeFights (now CodeSignal), who invited me to start participating in the Weekly Challenge way back in October 2019. That site no longer has messaging or forums, and I don’t know how to let them know directly, but this week is my response to their invitation. Thank you!Observations:

- A nibble (which I learned as “nybble”) is 4 bits, which is
*exactly**one*hex digit. So, in any approach that starts with translating to a binary string, I should consider hexadecimal instead of binary, in case it is clearer or more concise to code for 1|2 hex digits instead of groups of 4|8 bits. - The task deliberately avoids discussing N>=256, so we have some freedom to decide on behavior if we also want to solve for an extended domain. I may choose differently for Perl than for Raku.

See Util’s Raku solution for complete program.

```
multi sub nib ( Int $n where ^256 ) {
return ( ($n +& 0xF0) +> 4 )
+ ( ($n +& 0x0F) +< 4 );
}
multi sub nib ( Int $n where * >= 0 ) {
my Str $hex = $n.base(16);
$hex [R~]= '0' if $hex.chars !%% 2;
return $hex.comb(2)».flip.join.parse-base(16);
}
```

Thoughts, and notable elements:

`multi`

allows subroutines with “duplicate” names; the ambiguity is resolved by comparing the subs’ parameter lists to the arguments used in the actual subroutine call.`^256`

means the range`0..255`

- “Bit-twiddling” is an approach from the C language. Masking with
`+& 0xF0`

is not strictly needed, since`+>`

will right-shift those low bits into the bit bucket. I kept it there for clarity of intent. - To extend the task past 255 (for my own curiosity), I decided to swap nybbles in each byte. This is different from my decision in the Perl code.
- The second
`nib`

sub would work just fine by itself. I took advantage of Raku’s`multi`

to separate the solution for the task from my solution to the (invented) extended task. `.comb(N)`

splits a string into a list of sub-strings of length N.`.flip`

reverses a string;`'XYZ'.flip`

gives you`'ZYX'`

.`».`

makes a method (that would work on one thing) work on*each*thing in a list.`.join`

, without a parameter, joins its list using the empty string as a separator.`!%% N`

means “is not evenly divisible by N”, and returns`True`

or`False`

, without needing to tell you what the remainder would be.- Pre-pending zero when
`$hex`

is an odd length is the easiest way to assure alignment before breaking into 2-character substrings. - The
`R`

meta-operator reverses the operands of its operator.`4 / 5`

is 0.80, but`4 R/ 5`

is the same as`5 / 4`

, or 1.25 . - Just like
`$foo ~= 9`

would*append*nine to the contents of foo,`$foo [R~]= 9`

will*prepend*nine.`R`

is my least favorite meta-operator, but I have wanted a prepending op for a long time, and I think this could become a good idiom in Raku. Maybe. - I could have used
`.fmt`

or`sprintf`

instead of`.base(16)`

. Those would have given opportunity to specify that I want a leading zero, without needing that extra line of`[R~]=`

. However, how can we tell how many digits to request? We cannot just say “even number of digits”. We have to calculate the size, which is`2*$n.log(16²).ceiling`

. That code is long enough to need its own line, so nothing is gained in brevity, and some clarity would be lost. - The whole sub could be in one expression by using sprintf’s
`.*`

syntax for separate specification of size, which automatically has leading-zero turned on for hex digits:`return sprintf( '%.*X', 2*$n.log(16²).ceiling, $n ).comb(2)».flip.join.parse-base(16);`

. Now, let’s pretend I never wrote that.

Also, in the code (shown in the GitHub link above, not shown here) that auto-runs a test suite when no argument is given, I use two tricks:

- Since
`0x65`

and`101`

are just two different ways of “spelling” the*exact**same*number, I use hex format for the test data. That allows a human to easily calculate by hand the expected result. - Since
`nib(nib(X))`

should equal`X`

, any pairs of input and expected output should also be tested in reverse. Instead of repeating the`is`

line with reverse arguments, I kept it DRY (Don’t Repeat Yourself) by combining the “hyper-method” syntax with the`.antipair`

method that swaps key-and-value in a Pair object.

See Util’s Perl solution for complete program.

```
sub nib ( $n ) {
return ($n & 0xFFFFFF00)
+ ( ($n & 0xF0) >> 4 )
+ ( ($n & 0x0F) << 4 );
}
```

See Util’s Perl `bigint`

solution for complete program.

```
use bigint;
sub nib ( $n ) {
return ($n & ~0xFF)
+ ( ($n & 0xF0) >> 4 )
+ ( ($n & 0x0F) << 4 );
}
```

Thoughts, and notable elements:

- Clearly, this Perl code was influenced by my Raku solution.
- Instead of exchanging nybbles within every byte, I decided to only swap within the
*last*byte. This is different from my decision in the Raku code. - I used
`0xFFFFFF00`

in my original code, thinking that the mask is large enough to cover all input below`bigint`

range, and that I would figure out how big to extend it later, when I would add larger test cases and`use bigint`

. Then I forgot to extend it, and got failures in the new larger test cases. I learned the trick from Abigail of how to make the mask however-big-you-need-it: bitwise negation via`~0xFF`

. - No 7+ character English words can be made from only the letters A-F,
`perl -wlnE 'print if /^[a-f]{6,}$/i' unixdict.txt`

, drastically limiting our options for test constants more clever than`0xDEADBEEF`

.

Observations:

- Scanning through 1..∞ , and grep’ing for the right pattern, will be dirt-simple to write, and dog-slow to run. At N=258, you are already wasting 99.78% of the numbers to get ‘121212’, and the percentage of waste goes up as N grows. In Big-O notation, I think this approach is O(N²). The highest test number we are given is
`60`

, so both Perl and Raku will complete it in sub-second speed. I think I can do better, so I will see how much performance I can gain without completely abandoning clarity. - Changing to base-4 (and filtering on
`!/0|11/`

) will greatly reduce the percentage of waste, but still have a worse-than-linear performance. I can’t decide if it’s Big-O just has a much smaller vanished constant, or is still N-squared for some lowered value of “squared”. :^) - Base-3 seems ideal, but is unworkable because we will need to
`tr/012/123/`

, and no standard base has leading zeros, so we cannot generate any number with a leading`1`

. - 1,2,3 are not “numbers” in this problem; they are “symbols”. The task could have specified A,B,C or Foo,Bar,Baz or ζ,η,θ and (after tr/// or s///g) the algorithms would be the same. I found it convenient to use 0,1,2 in some circular (modulo) manipulations, to use “first symbol”,”second symbol”,”third symbol” in my thinking, and 1,2,3 mainly in the output.
- All the combinations of symbols of length 5 can be generated from all of length 4, by pre-pending 1 to all of length 4, then 2 to all of length 4, then 3 to all of length 4, then filtering out any with adjacent ones. Because you can
*generate*everything of length N from length N-1, I started thinking of each of those groups of same-length combinations as a “generation”. - The numbers that represent the start of each generation (like where the final length-5 value
`33333`

increments to the first length-6 value`121212`

) are:`1,4,12,34,94,258,706,1930,5274,14410,...`

. That is the OEIS sequence A293005, which gives a formula that will quickly generate the rest that generation-size sequence, but I did not find it helpful in producing individual elements of the generations. - The count of members of each generation are:
`1,3,8,22,60,164,448,1224,3344,9136,...`

. That is the OEIS sequence A028859, of which the first comment is “Number of words of length n without adjacent 0’s from the alphabet {0,1,2}”. Bingo! Also, the partial sums of this sequence produce A293005 above. - ::: (In writing this blog post, I now see that A028859 points us to the fxtbook: “Matters Computational” (formerly titled “Algorithms for Programmers”), section 14.9: “Strings with no two consecutive zeros”. My 2 A.M. scanning of that section yields no insights, but then I don’t understand Generating Functions even when I am awake.)
- Raku has the
`Xop`

meta-operator, which is ideal for combining 1,2,3 with a prior generation to create the next generation. - Raku’s
`...`

sequence operator is designed to concisely support this “generate the next from the prior” computation, and allow it to be “lazy” (deferred until needed, and generating as much as demanded).

See Util’s Raku solution for complete program.

```
sub s123 ( Int $n where * > 0 ) {
sub next_generation ( @a ) {
return [ ( <1 2 3> X~ @a ).grep: {!/11/} ];
}
constant @s = ( [""], &next_generation ... * ).map(*.<>).flat;
return @s[$n];
}
```

Notable:

- The “decontainerizing” operator
`.<>`

has to be mapped to undo the “hard” containerization that happens to each generation. Otherwise,`.flat`

will fail to flatten them all into one nice long lazy stream. - We cannot change
`.map(*.<>)`

to`».<>`

, because the hyper-method syntax also implies that the method can be run on any element of the list in any order (the programmer is promising that parallel processing or out-of-order processing will cause no problems). This is not completely compatible with lazily-generated infinite lists, so the compiler disallows it (at least for now). - The
`@s`

array is auto-caching. For example, after`s123(10_000)`

is calculated,`s123(9_000)`

can be returned without calculation. - The only filtering needed the
`/11/`

specified in the task. There is no “waste” from generating non-123 digits. - The performance is now
*linear*: O(N). Whatever time it takes to calculate`s123(999)`

, it should only take 1000x as long to calculate`s123(999*1000)`

. That is a big win, compared to O(N²) which would take a 1000*1000x as long instead of just 1000x.

See Util’s Perl solution for complete program.

As I was translating the Raku solution to Perl, I re-read the `grep: {!/11/}`

code and had an epiphany. If /11/ does not already exist in a generation, then the only place it can occur during the production of the next generation is in those with a leading-1. If I keep each generation sub-grouped by leading digit, I can code to leave out the group containing leading-1 while creating the 1-group of the next generation. This will remove the need for the `grep`

completely, leaving only the direct generation of the combinations wanted by the task. I implemented this idea only in the Perl code.

```
sub s123 ( $n ) {
state @s;
state $last = [ [], [], [""] ];
while ( not defined $s[$n] ) {
push @s, @{$last->[0]},@{$last->[1]},@{$last->[2]};
$last = [
[ map { "1$_" } @{$last->[1]},@{$last->[2]} ],
[ map { "2$_" } @{$last->[0]},@{$last->[1]},@{$last->[2]} ],
[ map { "3$_" } @{$last->[0]},@{$last->[1]},@{$last->[2]} ],
];
}
return $s[$n];
}
```

I would have then used the sub-group idea to improve the Raku code, but the underlying idea pointed to deeper understanding.

More observations, and analysis:

- I want to use the same approach here that I would use to convert to base-N for any N: modulo, subtract, divide. This gives you one digit at a time, building from smallest digit to largest, in O(log N) time. That cannot work here, because the smallest digit is arrhythmic; every time a /11/ pattern occurs at a higher level, it disrupts the even rhythm of
`123123123123...`

that would allow the modulo operation to give the right answer. - Digit-at-a-time can be processed from the other direction. We usually don’t, because of the extra effort. For example, converting 361 to base 5, we first ask “what is the highest power of 5 that is not bigger than our target?”
`5**4=625`

*is*bigger.`5**3==125`

is*not*bigger. Now, how many 125’s can we get out of 361? We can extract 2 of them,`2*125==250`

, and`361-250=111`

, so the first digit will be`2`

, and we continue the process with the remaining`111`

. We continue on,*not*until the remainder is zero, but until we calculate 5**N all the way down to N==0 and so have handled the “ones” place. We could do the same thing here, if we just had a way to tell (ahead of time) what input numbers represented each “left-most digit”, like 3xxxx, 2xxxx, and 1xxxx. Also, we need the “distance” between 3xxxx and 2xxxx (and 2->1 and 1->0) in the source numbers. Instead of producing every number in every generation, we can calculate the

*counts*in each generation using the sub-group idea from above; something like`raku -e 'my @s1 = [0,0,1], { [ @^a.sum - @^a[0], @^a.sum, @^a.sum ] } ... *; say .raku for @s1.head(5);'`

[0, 0, 1] [1, 1, 1] [2, 3, 3] [6, 8, 8] [16, 22, 22] [44, 60, 60]

Using a flattened copy of those 3-sub-grouped counts, and a partial sum of the flattened copy, we can scan to find the first partial sum that cannot fit our target, and from its position calculate both the digit it should correspond to

*and*the amount of the original target that it represents. For example:

@s2 is a flattened copy of @s1: 0, 0, 1, 1, 1, 1, 2, 3, 3, 6, 8, 8, 16, 22, 22, 44, 60, 60, …

@s3 is the partial sum of @s2: 0, 0, 1, 2, 3, 4, 6, 9, 12, 18, 26, 34, 50, 72, 94, 138, 198, 258, …

200 is the target, and falls between @s3[16]==198 and @s3[17]==258; 17 % 3 == 2, so the first digit will be 2+1==”3”, and we will be subtracting from 200 the values of @s2[17]==60 (to reduce 200 from representation 3xxxx to 2xxxx), @s2[16]==60 (to reduce from representation 2xxxx to 1xxxx), and @s2[15]==44 (to reduce from representation 1xxxx to xxxx). 60+60+44==164. 200-164==36. So, first digit is “3”, and the remaining target is 36.

36 is the target, and falls between @s3[11]==34 and @s3[12]==50; 12 % 3 == 0, so the next digit will be 0+1==”1”, and we will be subtracting from 36 the values of @s2[12]==16 (to reduce 36 from representation 1xxx to xxx). 36-16==20 So, next digit is “1”, and the remaining target is 20.

20 is the target, and falls between @s3[9]==18 and @s3[10]==26; 10 % 3 == 1, so the next digit will be 1+1==”2”, and we will be subtracting from 20 the values of @s2[10]==8 (to reduce 20 from representation 2xx to 1xx) and @s2[9]==6 (to reduce from representation 1xx to xx). 6+8==14 20-14==6 So, next digit is “2”, and the remaining target is 6.

And so on, until target is zero.

See Util’s Raku solution for complete program.

```
sub s123 ( Int $n is copy where * > 0 ) {
constant @s1 = [0,0,1], { my \s = @^a.sum; [ s - @^a[0], s, s ] } ... *;
constant @s2 = @s1.map(*.<>).flat;
constant @s3 = [\+] @s2;
return join '', gather {
while $n > 0 {
my $k = @s3.first: :k, * > $n;
my $pos = $k % 3;
take $pos + 1; # Digit
$n -= @s2[ $k + (-$pos .. 0) ].sum
}
# Should be impossible, but I cannot prove it.
die "NEGATIVE N: ", $n if $n < 0;
}
}
```

Using even the fastest linear Perl code, `s123(10**120)`

would take longer than the heat death of the universe, *if* my laptop had enough memory.

Using this new logarithmic Raku code, `s123(10**120)`

takes less than 1 second.

See Util’s Perl solution for complete program.

This Perl code is a straight translation of the Raku logN code, except that @s1 is skipped in favor of generating @s2 directly. In Raku, generating @s2 directly is *much* harder to understand, due to shifting positions of “the 3 values of the last generation” as each element has to look-back a different offset amount. This is the first situation that I have seen Perl’s “flatten everything always” approach allow for clearly better code.

```
sub s2 ( $n ) {
state $s2 = [ 0, 0, 1 ];
while ( not defined $s2->[$n] ) {
my $s = sum0 @{$s2}[-3,-2,-1];
push @{$s2}, $s - $s2->[-3], $s, $s;
}
return $s2->[$n];
}
sub s3 ( $n ) {
state $s3 = [ s2(0) + s2(1) ];
while ( not defined $s3->[$n] ) {
push @{$s3}, $s3->[-1] + s2($#{$s3} + 1);
}
return $s3->[$n];
}
sub s123 ( $n ) {
my $r;
while ( $n > 0 ) {
my $k = first { s3($_) > $n } 0..4200; # Enough for 10**600
my $pos = $k % 3;
$r .= $pos + 1; # Digit
$n -= sum0 map { s2($_) } ($k-$pos) .. $k;
}
# Should be impossible, but I cannot prove it.
die "NEGATIVE N: ", $n if $n < 0;
return $r;
}
```

In closing, I want to point out that although all my Raku code is cleaner than its Perl equivalent, that is due in large part to my solutions having leaned on features that Raku added to its Perl origins, so translating them back to Perl makes them “wordier”.

The place where Raku was indispensable was in the support for higher-level thinking and lazy infinite lists.

Re-reading my logN Raku code, the three constant lazy infinite arrays, and the block that uses them, feel elegant, almost obvious. In reality, it was a treacherous, tortuous trek to tease that algorithm from the torrent of tri-digits. Not remotely obvious. Only elegant at the end.

I can now recreate this code in many languages, but I could not have *created* it in any language I know, except Raku.

*/me* *sleeps*