There could be a way... or not.

A project log for PEAC Pisano with End-Around Carry algorithm

Add X to Y and Y to X, says the song. And carry on.

Yann Guidon / YGDESYann Guidon / YGDES 01/26/2022 at 06:130 Comments

Several logs, such as 106. More mathematics, have tried to "crack" the problems with "classic maths", using equations and such. I'm not gifted for this approach but I do my best and so far it has not been fruitful. The big problem is that there is no nice and tidy equation, as with the Fibonacci and Pisano cases. There is always this increment that comes up at seemingly random interval, though with a 1/2 probability.

Using the probability, it might be possible to estimate or approximate a result, though it falls apart "very quickly" as the errors accumulate. So I can't find one equation for the value of the Nth step.

However I just realised that there could be a way to short-circuit a lot of uncertainties. The main goal so far is to determine IF a given width provides a pair of orbits of maximal length. And we happen to know the main characteristics of such an orbit, in particular the length (L). So we can define a cyclic equation, given a hypothetical function PEAC(n) that returns the value of the nth step:

PEAC(n) = PEAC(n+L)

This should be true for all values of n from 0 to L-1. Let's now borrow the sampling idea from prime number folks: given a sufficiently large number of random n (10s ? 100s ?), we can have a sufficiently high confidence that PEAC(n) is cyclic with a period of L (or one of its multiples, as might be the case for w6 and w24) without scanning it completely...

The real problem is how to compute PEAC(n). It is derived from the Pisano formula, with the random increment. The trick would be to be sure of the number of increments during a full orbit. From my early explorations, it seems that the number of crossings of 0 is not exactly 1/2 but it would converge soon enough. So at least, we would have a sufficiently close estimate, and sampling more points / n would increase the confidence.

Another problem is that the Binet formula contains powers of φ, which is irrational, so computing its nth power increases the required precision to an irrealistic point, where computation and storage of the value exceed reason. Buuuuut.... φ is irrational, not transcendental, and contains sqrt(5). I just realised that all its even powers make a perfectly nice integer ! It is not a significant limitation to only consider even powers so yeah, I am relieved: no infinite precision arithmetic...

Exponentiation in modulo arithmetic is well known (again, it's used all the time in the prime number domain, for RSA computations for example). So there might be a way after all, even though I have not collected all the clues. Yet.


Oh I might have overlooked a little detail. Let's look at the known equations:

F(n) = ( φ^n - (-φ)^n ) / √5
     = ( ((1+√5)/2)^n  - ((1-√5)/2)^n ) / √5
     = ( (1+√5)^n − (1−√5)^n ) / (√5 * 2^n)


Pis(n,m) = F(n) mod m
              = (( φ^n - (-φ)^n ) / √5 ) mod m

That little pesky irrational divisor breaks my plans again. But there might be a way again, if we work modulo m×√5... or something like that.

Maybe the pattern of the carries can be deduced from the Continued fraction expansion...

OK I'm so bad at mathing that I overlooked that (1+√5)^n would still be irrational, even for even powers, simply because of the added 1, and (a+b)²=a²+2ab+b². The 2ab term is what keeps the sum from ever being an integer...

Damnit. Another dead end.