Pisot Sequences

Thanks to the number associated with my diurnal age today, 27204, I was introduced to so-called Pisot sequences that I'm still coming to terms with. Let's start with one of the properties of this number, namely its membership in OEIS A048589:

A048589

Pisot sequence L(7, 9).

The members of the sequence are derived using the following formula:

$$a(n)= \Biggl \lceil \frac{a(n - 1)^2}{a(n - 2)} \Biggr \rceil \\ \text{ where } n \geq 2 \text{ with }a(0)=7 \text{ and } a(1)=9$$The initial members of the sequence are:

7, 9, 12, 16, 22, 31, 44, 63, 91, 132, 192, 280, 409, 598, 875, 1281, 1876, 2748, 4026, 5899, 8644, 12667, 18563, 27204, 39868, 58428, 85629, 125494, 183919, 269545, 395036, 578952, 848494, 1243527, 1822476, 2670967, 3914491, 5736964, 8407928, 12322416, 18059377

However, exactly the same sequence of numbers can be derived from the recurrence relation:$$a(n)=2a(n-1)-  a(n-2) + a(n-3) - a(n-4)\\ \text{ with } a(0)=7, a(1)=9, a(2)=12 \text{ and } a(3)=16$$However, the equivalence may last only up to \(n=1000\) according to the OEIS comments. After that, there is uncertainty. Permalink.

Let's take another example using OEIS A018910:

A018910

Pisot sequence L(4, 5).

Once again, the previous formula can be used with different starting values:$$a(n)= \Biggl \lceil \frac{a(n - 1)^2}{a(n - 2)} \Biggr \rceil \\ \text{ where } n \geq 2 \text{ with }a(0)=4 \text{ and } a(1)=5 $$The initial members of the sequence are:

4, 5, 7, 10, 15, 23, 36, 57, 91, 146, 235, 379, 612, 989, 1599, 2586, 4183, 6767, 10948, 17713, 28659, 46370, 75027, 121395, 196420, 317813, 514231, 832042, 1346271, 2178311, 3524580, 5702889, 9227467, 14930354, 24157819, 39088171, 63245988, 102334157, 165580143

Again, the same sequence can be generated using the recurrence relation (permalink):$$a(n)=2a(n-1)- a(n-3)\\ \text{ with } a(0)=4, a(1)=5 \text{ and } a(2)=7 $$Just to confuse matters we can also generate the sequence using:$$a(n) = \text{ Fibonacci}(n+3)+2$$What the letter L signifies I don't know. Other letters are used with Pisot sequences, including E, P and T. Not all Pisot sequences use the ceiling function. Some use the floor function and others add or subtract a constant. There's not a great deal of introductory information out there about these sorts of sequences. You find yourself in deep mathematical matters very quickly once you start to explore the topic. 

Here is what Google's Bard had to say about them:

Pisot sequences are a type of infinite sequence of real numbers that have a number of interesting and useful properties. They are named after the French mathematician Charles Pisot, who first studied them in the 1930s.

Simple examples of Pisot sequences include:

• The Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
• The Lucas sequence: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ...
• The Parry sequence: 0.1101001000101101...

Pisot sequences are important because they have a number of unique properties. For example:

• They are all irrational numbers.
• They are all aperiodic (meaning that they never repeat themselves exactly).
• They are all dense in the real numbers (meaning that between any two real numbers, there is always a Pisot number).

Pisot sequences are connected to Pisot numbers and Salem numbers in the following way:

• A Pisot number is a real number that is greater than 1 and has the property that all of its conjugates are less than 1.
• A Salem number is a real number that is greater than 1 and has the property that all of its conjugates are either less than 1 or equal to 1.

Every Pisot number is the limit of a Pisot sequence, and every Pisot sequence converges to a Pisot number. Salem numbers are a special type of Pisot number.

Here are some of the applications of Pisot sequences:

• They can be used to generate random numbers.
• They can be used to model complex systems, such as the growth of populations and the spread of diseases.
• They can be used to design efficient algorithms for tasks such as sorting and searching.
• Pisot sequences are a fascinating and important area of mathematics, and they have a wide range of applications in other fields.

Double Iterations Involving Ceiling and Floor Functions

On May 21st 2022, I created a post titled Iterations of a Ceiling Function and the function being dealt with had this form:$$\lceil \sqrt{n} \, \rceil \times (\lceil \sqrt{n}\, \rceil^2 \, – \,n) $$The iteration, with output becoming the new input, leads to zero or a loop although this hasn't been rigorously proved. The number associated with my diurnal age today, 26872, has this property. The trajectory ends in a loop and is as follows:

26872, 3936, 2079, 1702, 2604, 5200, 9417, 18326, 23120, 44217, 64144, 94488, 115808, 161293, 125022, 104076, 81719, 22022, 26671, 36900, 67357, 63180, 81648, 42328, 22248, 37800, 43875, 47250, 59732, 71785, 10452, 16171, 27264, 48472, 81549, 70642, 30324, 52675, 51750, 53352, 2079

Figure 1 shows the trajectory of 26872 under this iteration.

Figure 1: trajectory of 26872 under the floor iteration

There is an associated function that involves the floor function and it has this form:$$\lfloor \sqrt{n} \, \rfloor \times (n-\lfloor \sqrt{n}\, \rfloor^2) $$When this function is iterated, with output serving as the new input, a loop is also reached:

26872, 49389, 23310, 31312, 59136, 21141, 16820, 23091, 43790, 22781, 42150, 25625, 4000, 1953, 748, 513, 638, 325, 18, 8, 8

Figure 2 shows the trajectory of 26872 under the floor iteration.

Figure 2: trajectory of 26872 under ceiling iteration

Here is a permalink to an algorithm that will confirm these two trajectories. Numbers like 26872 that do not end in zero under both iterations but instead end in loops are members of OEIS A219963:

A219963

Numbers n which do not reach zero under either of the iterations: \( n \rightarrow \lfloor \sqrt{n} \rfloor \times  (n - \lfloor \sqrt{n}) \rfloor\ ^2) \) or  \( n \rightarrow \lceil \sqrt{n} \rceil \times ( \lceil \sqrt{n} \rceil ^2- n ) \).

Not surprisingly, these numbers are rather rare. Here are the initial members of the sequence:

2897, 3159, 3183, 4004, 6335, 7025, 8163, 8237, 8621, 9234, 12204, 12963, 13381, 14340, 15217, 16191, 16438, 17474, 17763, 17972, 18065, 18990, 19677, 19848, 20345, 20803, 21426, 21539, 22022, 25834, 26872, 27175, 28052, 28929, 28996, 29295, 30511, 30991

The first pair of consecutive integers belonging to this sequence is (89971, 89972). As with all these sorts of trajectories, the issue of records arise. For example, what number produces the longest sequence? What number produces the maximum peak? The calculation at each step of the algorithm seems somewhat processor intensive so that calculations over large ranges cause it to time out (on SageMathCell at least). Still, these are interesting statistics to explore. It will be 303 days before my diurnal age again matches a member of this sequence.

An Interesting Iteration

Having turned 26506 days old today, my attention was drawn to this OEIS sequence:

A219960

Numbers which do not reach zero under the repeated iteration \(x \rightarrow \lceil \sqrt{x} \, \rceil \times  (\lceil \sqrt{x}\, \rceil ^2 - x) \).

Figure 1 shows that 26506 is the 511th such number and thus the frequency of such numbers is about 1.93%.

Figure 1

The first members of this sequence are as follows:

366, 680, 691, 1026, 1136, 1298, 1323, 1417, 1464, 1583, 1604, 1702, 2079, 2125, 2222, 2223, 2374, 2507, 2604, 2627, 2821, 2844, 2897, 3152, 3157, 3159, 3183, 3210, 3231, 3459, 3697, 3715, 3762, 3802, 3866, 3888, 3936, 3948, 4004, 4111, 4133, 4145, 4231, 4299, ...

Here is a permalink to the algorithm on SageMathCell that will return all members of OEIS A219960 up to and including 26506. 

The OEIS comments include the following conjectures:

• Conjecture 1: All numbers under the iteration reach 0 or, like the elements of this sequence, reach a finite loop, and none expand indefinitely to infinity. 

• Conjecture 2: There are an infinite number of such finite loops, though there is often significant distance between them. 

• Conjecture 3: There are an infinite number of pairs of consecutive integers in this sequence despite being less abundant than in A219303.

OEIS A219303 refers to the iterative process where the ceiling function is replaced by the floor function. So what happens to 26506 under this iteration? Here is the trajectory:

26506, 10269, 13770, 18172, 7155, 5950, 10452, 16171, 27264, 48472, 81549, 70642, 30324, 52675, 51750, 53352, 2079, 1702, 2604, 5200, 9417, 18326, 23120, 44217, 64144, 94488, 115808, 161293, 125022, 104076, 81719, 22022, 26671, 36900, 67357, 63180, 81648, 42328, 22248, 37800, 43875, 47250, 59732, 71785, 10452

As can be seen, after five steps a loop of length 38 is entered with a length of 43 steps overall. Figure 2 shows this trajectory using a log scale for the vertical axis.

Figure 2

Up to 26506, the trajectory of maximum length is associated with the number 25923 that has a trajectory of length 86 and ends in 0:

25923, 52002, 100531, 188574, 283185, 481832, 829135, 716046, 1154461, 1251300, 963459, 849430, 602988, 575757, 245916, 49600, 28767, 22610, 28841, 10030, 17271, 20196, 36179, 57682, 96159, 174782, 326401, 447876, 686080, 962469, 1821610, 1201500, 2094173, 3664888, 4475355, 4445716, 4565985, 1675408, 2094015, 3893672, 5929896, 10231200, 7680799, 8828820, 11781008, 15383273, 26111488, 3127320, 3610529, 6220072, 12357735, 15895836, 1327671, 2003914, 1617072, 1160064, 2177560, 1499616, 1236025, 577128, 358720, 48519, 71162, 33909, 58460, 25168, 17967, 34830, 25993, 40662, 28684, 36720, 27648, 40247, 30954, 3872, 6111, 10270, 13668, 2457, 2150, 2773, 1908, 1232, 2304, 0

Figure 3 shows the trajectory of 25923 using a log scale for the vertical axis.

Figure 3

Figure 4 shows the distribution of trajectory lengths between 1 and 26506. All square numbers immediately become zero under the iteration. Using 25 as an example, we get:

\( \lceil \sqrt{25} \rceil \times ( \lceil \sqrt{25} \, \rceil ^2 - 25) = 5 \times (25 - 25) = 5 \times 0 = 0 \)

Figure 4

So far only the numbers up to and including 26506 have been examined because the algorithm is processor intensive. However, if we search from 26507 to 50000, we find that the record length increases slightly to 91, again ending in 0. Here is the record length attained by 35727:

35727, 70870, 111873, 117920, 143104, 203523, 353012, 602735, 772338, 266337, 492184, 435240, 237600, 265472, 404544, 780325, 999804, 196000, 110307, 193806, 297675, 240786, 144845, 120396, 4511, 7684, 5280, 3577, 1380, 2432, 3400, 4779, 8470, 16647, 32890, 42588, 54027, 61046, 113584, 223080, 306977, 581640, 403627, 552684, 633888, 1052837, 1943084, 211888, 291813, 469588, 691488, 612352, 577071, 402040, 752475, 823732, 664656, 979200, 891000, 128384, 178423, 214038, 153253, 161112, 197784, 107245, 111192, 121576, 78525, 122516, 240435, 317186, 513240, 608733, 959068, 1305360, 1244727, 813564, 36080, 3800, 2728, 4293, 4158, 4355, 66, 135, 108, 143, 12, 16, 0

Here is the permalink for this calculation. Note that the penultimate number in the trajectory is 16 which is a square number (\(4^2\)), just as the penultimate number for the previous record trajectory was 2304, also a square number (\(48^2\)). Clearly, it is only when a square number is reached in the trajectory that a result of zero will arise in the next iteration. However, in the case of over 98% of numbers (at least in the range up to 26506), the trajectory does not terminate at zero but instead enters a loop.

Conjecture 3, included earlier, states that "there are an infinite number of pairs of consecutive integers" so let's investigate this further. In the range up to 26506, the following pairs occur:

• 2222 2223 
• 8399 8400 
• 11457 11458 
• 12950 12951 
• 19005 19006 
• 19847 19848 
• 22444 22445 
• 23597 23598 
• 25089 25090 
• 25175 25176 
• 25742 25743 

So eleven pairs in that range shows that pairs of such numbers are not that common and of course there's no way to confirm that there are an infinite number of them.

Iterations that lead to a Constant or a Loop

One of my first encounters with an iterative process that leads to either a constant or a loop was with so-called happy numbers. See my post of 28th June 2018 titled Happy Numbers. The iterative process involved with these numbers is to repeatedly add the sums of squares of digits to either reach a constant (1) or enter a loop (4, 16, 37, 58, 89, 145, 42, 20, 4, ... ). Approximately, 15% of numbers are happy.

25286 is a happy number because the process leads to 1: 

25286 --> 133 --> 19 --> 82 --> 68 --> 100 --> 1

89 is a nominally unhappy number because the process leads to a loop:

89 --> 145 -->  42 --> 20 --> 4

Today I turned 26187 days old and this number forms part of OEIS A219960:

A219960

Numbers which do not reach zero under the repeated iteration x -> ceiling(sqrt(x)) * (ceiling(sqrt(x))^2 - x).

In the case of 26187 the iteration proceeds as follows:

[26187, 9234, 16975, 24366, 44431, 18990, 7452, 10179, 2222, 3936]

whereupon it enters the loop:

[2079, 1702, 2604, 5200, 9417, 18326, 23120, 44217, 64144, 94488, 115808, 161293, 125022, 104076, 81719, 22022, 26671, 36900, 67357, 63180, 81648, 42328, 22248, 37800, 43875, 47250, 59732, 71785, 10452, 16171, 27264, 48472, 81549, 70642, 30324, 52675, 51750, 53352, 2079]

Graphically the situation is as in Figure 1 with 161293 being the highest value reached:

Figure 1

Of the numbers up to 26187, 504 do not reach zero which represents a little under 2% of the total.

There is a similar iterative process involving the floor function (OEIS A219303):

A219303

Numbers which do not reach zero under the repeated iteration x -> floor(sqrt(x)) * (x - floor(sqrt(x))^2).

In the comments for OEIS A219960 (with the ceiling function), the following is stated:

Conjecture 1: All numbers under the iteration reach 0 or, like the elements of this sequence, reach a finite loop, and none expand indefinitely to infinity.

Conjecture 2: There are an infinite number of such finite loops, though there is often significant distance between them.

Conjecture 3: There are an infinite number of pairs of consecutive integers in this sequence despite being less abundant than in A219303.

In regard to Conjecture 3, we find that in the range from 1 to 26187, the following pairs occur:

(2222, 2223), (8399, 8400), (11457, 11458), (12950, 12951), (19005, 19006), (19847, 19848), (22444, 22445), (23597, 23598), (25089, 25090), (25175, 25176), (25742, 25743)

In the comments for OEIS A219303 (with the floor function), the following is stated:

Collatz-like hailstone behavior is evident, but the iteration more closely resembles the iteration used to determine happy numbers (A007770), albeit in a non-base-specific manner. Unlike happy numbers, and despite being approximately as dense in the integers, these numbers do not reach their iterative goal.

Conjecture 1: All numbers under the iteration reach 0 or, like the elements of this sequence, reach a finite loop, and none expand indefinitely to infinity.

Conjecture 2: There are an infinite number of such finite loops, though there is often significant distance between them.

Conjecture 3: There are an infinite number of pairs of consecutive integers in this sequence, e.g. 14 and 15, 197 and 198. This argument is strengthened by the fact there are other groupings such as triples - The first of these is 11527, 11528 and 11529 - and also that for randomly chosen numbers of hundreds of digits, N, the nearest pair or grouping appears to be within N +/- 1000.

We find that the 10,000th member of OEIS A219303 is 211,264 so the numbers have a density of around 4.73% which is well over twice the density of numbers in OEIS A219960. Figure 2 shows a plot of the trajectory of 211,264 using a log scale for the y axis. Notice that once it reaches 8 it flatlines and stay on 8 forever because floor(sqrt(8)) * (8 - floor(sqrt(8))^2) = 8:

Figure 2: permalink