Padovans Dog

Wherein as we give a man a dog, and see if he barks. They man that is: we already know that dogs bark.

THE WEEKLY CHALLENGE – PERL & RAKU #154 Task 2

---

““Science, Philosophy, Architecture”“

— Richard Padovan

---

Padovan Prime

Submitted by: Mohammad S Anwar

A Padovan Prime is a Padovan Number that’s also prime.

In number theory, the Padovan sequence is the sequence of integers P(n) defined by the initial values.

P(0) = P(1) = P(2) = 1

and then followed by

P(n) = P(n-2) + P(n-3)

First few Padovan Numbers are as below:

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, ...

Write a script to compute first 10 distinct Padovan Primes.

Expected Output

2, 3, 5, 7, 37, 151, 3329, 23833, 13091204281, 3093215881333057

ANALYSIS

The Padovan numbers are defined by a recurrence relation similar to that of the Fibonacci numbers, only in this case not using the sum of the two previous values but rather the result of skipping over the previous value and summing the two sequential positions previous to that.

There is one additional twist, however, in the unusual selection of the starting conditions. There are other equivalent extensions of the Fibonacci number recurrence relation, first as a generalized Lucas sequence and then later as the basis of what is known as the Perrin sequence. These differ only from the Padovan numbers in their initializaion parameters.

Once curious property of many found in the Fibonacci numbers is the ability to arrange a construction of squares, with side lengths the values of the Fibonacci numbers, to form a space-filling geometric pattern. Starting with the initial conditions (1,1), two squares are constructed with sides of one unit. Starting with the first square, the second is adjoined to it along an initially chosen axis and the composite shape is rotated 90°. From that point forward, new squares are constructed, sized according to the next Fibonacci number, and placed against the structure. As the shape is rotated the exposed length of the junction edge will always equal the side-length of the next square, and once we have the central kernel established we can add new, larger squares in this fashion indefinitely. Of course the rotational transformation is relative to the frame of reference, and we can as easily consider the origin to remain fixed and the edge defining the next junction to shift 90° between the addition of successive squares. Viewed this way the squares are joined along a circular track circumscribing the origin and expanding outwards.

By inscribing an arc within each square, each with the side-length as radius, the lines can be connected to form a spiral that closely mimics and converges on what is known as the golden spiral, a logarithmic spiral with a growth factor of the irrational number φ. This parallels the property that the ratio of sucessive Fibonacci numbers also converges to φ, the ratio (a + b)/a = b/a .

I personally find the space-filling aspect of the construction one of the most fascinating aspects of the sequence; that by circling around, the area can be expanded indefinitely both without gaps and without repeating any element size beyond the initial two blocks. Although the analogous construction of the golden spiral, using side-length ratios equal to φ, can be continued indefinitely towards the origin using fractionally smaller sizings, using the Fibonacci approximations we have a definitive starting point when we duplicate the first 1. This provides a complete 1 + 1 = 2 sized wall to start the spiral, but in a way even more curiously the construction remains completely space-filling.

The fractal surrounding the origin of the analogous golden spiral behaves slightly differently, and with the addition of each new smaller square always leaves a diminishing unfilled area in which to expand, circling and converging to the origin. The area of this unfilled space eventually only vanishes to zero after an infinite number of steps. Viewed as a continuous function, then, the squares sectioning a golden spiral are also space-filling on an infinite scale.

So how does this geometry relate to the Padovan numbers?

The careful selection of the initial conditions to construct the Padovan numbers remarkably allows us to form a similar figure based on equilateral triangles instead of squares, with side lengths corresponding to the successive elements of the sequence. This construction is also space-filling and can be expanded indefinitely.

A logarithmic spiral can also be inscribed in the construction, analogous to the Fibonaci spiral, that mimics the spiral with a growth factor of the convergence of that sequence. This number, known as the “plastic number”, or commonly just p, is approximately 1.32471, corresponding to the real solution to the equation

x³ = x + 1

This polynomial in turn brings us back to φ again, as that value is also defined as the solution to the expression

x² = x + 1

This is what forms the basis of the plastic number being a three-dimensional version of φ. But we’ll get to this later.

And what of the prime numbers?

The selection of the initial conditions (3, 0, 2) with the same recurrence relation as the Padovan numbers yields what is known as the Perrin sequence, which has a curious association with prime numbers: for all prime numbers p, P(p) % p = 0 .

Which is to say all primes are divisors of their corresponding Perrin number. This is exciting, and would make for a quick test of primality, except for the thorny existence of what are known as Perrin pseudoprimes, being composite numbers that also share this same property. At first only theorized for years, the first such number was only discovered in 1982 and is 521² = 271441. The next does not even follow the pattern of being a perfect square, either, which blows any theory based on that observation at the get-go. There have been shown to be an infinite number of Perrin pseudoprimes, although they are still relatively infrequent.

The association, or near-association, of Perrin numbers with the primes is a good example of why, given any sequence, some mathematician of another is going to come along and check its membership for primality. You never know whether you might find something new and interesting. Or not find, which can be interesting in its own right. So this, ultimately, is what we’re doing today.

METHOD

As no better scheme presents itself, we’ll solve the task by constructing a sequence of Padovan numbers using the recurrence relation, while checking new values for primality as we go. We can save some space by discarding obsolete members of the sequence and only maintaining a queue of the last three elements constructed.

One troublesome qualifier was that the returned results be distinct. In order for the final count to be correct this selection needed to be before the output as assembled, so an extra conditional was inserted.

Determning more than the requested 10 values is problematic, as the final result of the 10 already reaches the value 3,093,215,881,333,057. As it turns out, thanks to the arbitrary precision integers in Raku, the next result was able to be calculated as

1363005552434666078217421284621279933627102780881053358473

In Perl, our manual method of checking for primality is going to break even if we arranged to somehow handle the required integer.

Observations and Commentary

The Padovan numbers, for all their interesting geometric associations, don’t seem to have much if anything to do with the primes. Hence the dog. And why are we looking for these geometric associations anyway? The answer circles around the idea of the plastic number p, and its association to the number φ. Ultimately it’s because people have been noticing, and been fascinated by φ, for quite some time. Many people have seen perfection in its defining properties beyond their underlying mathematical basis, and extended this patterning into the physical world and our perceptions of beauty.

The idea of the golden section, built from the ratio of 1 to φ , leading to a somehow “perfect” aesthetic is problematic, to say the least, and in my eyes rapidly degenerates into a Texas sharpshooter’s cloud of mysticism. There is undeniably a beauty in the mathematical underpinnings of the world — most certainly — but there has been quite a bit of effort spent force-fitting those models to our own perceptions of propriety in proportion. I believe the problem, and with it beauty, is diminished by reducing this complex balance to a simple, “perfect” ideal. Efforts to expand this thinking into three dimensions with the plastic number, while possibly pleasant in the results, have found themselves to be even more elusive and strained. One gets the idea of shoehorning the world into a preconceived idea of beauty and balance, touting validation when seemingly located and hand-waving over inconsistencies and imperfections.

The ratio in converting miles to kilometers is 1:1.60934. The golden ratio is about 1:1.618, less that a 0.5% difference. Does this make the two distances, taken together, as the basis of a “perfect” measurement system? The evidence is incontrovertible!

I find the tenuous grasp of this argumentation both exhausting and all too common. The human brain is a pattern-matching machine, and so I do not think the idea of recurring patterns in proportions to be entirely without merit, rather quite the opposite. The issue I have is one of hierarchy, and presenting one particular pattern as inherently superior, a somehow divine perfection. The extension of this thinking into the search of a three-dimensional analog to the golden section inherits all of the logical flaws from the arguments about φ. I like some of the results, but it’s a creative game, not a divine truth.

I think the real secret of the universe, the real insight to be observed here is in the recurrence of the thought-patterning that leads us to the idea that φ is proportional perfection in the first place. The influence of motivated thinking in the history of humanity cannot be overstated.

But back to the task at hand, perhaps a kinder take than the pejorative in using the word “dog” would be instead to say the title is a reference to the way dogs will run in circles when excited. The spirals, both the Fibonacci spiral and that from the inscription through the triangle space-filling pattern observed with the Padovan Numbers, mimic those crazy circles.

Yea, we’re going to go with that instead. Thinking about happy dogs is always better.

Better than most anything, when it comes down to it.

PERL 5 SOLUTION

In Perl we construct a neat little queue to maintain the necessary information to always be able to construct another Padovan number. After defining the queue once with initial conditions, we capitalize on the way Perl processes variable assignments, allowing us to compute the sum of the second element and the result of shifting the first off of the array. This would shorten the array to two elements, however we simultaneously push this sum back on the end to the array, keeping the element count at three. push returns the number of elements in the final array rather than the elements added, so we need to explicitly return the most-recently added element from the queue.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';

MAIN: {
    my @out = ();

    while ( @out < 10) {
        my $c = next_pad();
        next if (defined $out[-1] and $out[-1] == $c);
        push @out, $c if is_prime( $c ) ;
    }

    say "@out";
}

sub is_prime ($n) {
    my $sqrt = int sqrt $n;
    return 0 unless $n % 2 or $n == 2;
    
    for (my $x = 3; $x <= $sqrt; $x += 2) {
        return 0 unless $n % $x;
    }
    return 1;
}

sub next_pad {
    state @p = (1,1,1);
    push @p, $p[1] + shift @p;
    return $p[-1];
}

The result:

2 3 5 7 37 151 3329 23833 13091204281 3093215881333057

Raku Solution

In Raku the code is noticeably quicker, presumably due to the built-in .is-prime() method. By inlining the Padovan construction routine (which was only one line anyway) the subroutines are superfluous and the code is considerably compacted. The way Raku stores integers allows them to reach arbitrary length, which .is-prime()somehow manages quite well.

Some really big results:

2
3
5
7
37
151
3329
23833
13091204281
3093215881333057
1363005552434666078217421284621279933627102780881053358473
1558877695141608507751098941899265975115403618621811951868598809164180630185566719
9514203022010025394023102730908438531208701419096004247531838174629003586002086450683209161195000703512605873489625155263832444165133265702781668278617857

You get the idea.

unit sub MAIN ($max = 11) ;

my @pav = 1,1,1;
my @out;

while @out.elems < $max {
    @pav.push( @pav[1] + @pav.shift ) ;
    next if @out.elems and @pav[2] == @out[*-1];
    @pav[2].is-prime && @out.push: @pav[2] ;
}

.say for @out;