Advent of PBT 2021 - Day 7 - Solution

Our algorithm was: fibonacci.
Go to the subject itself for more details

CodeSandbox with a possible set of properties you may have come with: https://codesandbox.io/s/advent-of-pbt-day-7-solution-ts0nw?file=/src/index.spec.ts&previewwindow=tests

---

Fibonacci a function coming from mathematics, it comes with lots of properties out of the box. We can just enumerate some of them to confirm our code works fine.

As our implementation of fibonacci comes with a linear time-complexity we will cap the maximal value we pass to it to MaxN = 1000.

---

Property 1: should be equal to the sum of fibo(n-1) and fibo(n-2)

Written with fast-check:

it("should be equal to the sum of fibo(n-1) and fibo(n-2)", () => {
  fc.assert(
    fc.property(fc.integer({ min: 2, max: MaxN }), (n) => {
      expect(fibonacci(n)).toBe(fibonacci(n - 1) + fibonacci(n - 2));
    })
  );
});

Property 2: should fulfill fibo(p)*fibo(q+1)+fibo(p-1)*fibo(q) = fibo(p+q)

Written with fast-check:

it("should fulfill fibo(p)*fibo(q+1)+fibo(p-1)*fibo(q) = fibo(p+q)", () => {
  fc.assert(
    fc.property(
      fc.integer({ min: 1, max: MaxN }),
      fc.integer({ min: 0, max: MaxN }),
      (p, q) => {
        expect(fibonacci(p + q)).toBe(
          fibonacci(p) * fibonacci(q + 1) + fibonacci(p - 1) * fibonacci(q)
        );
      }
    )
  );
});

Property 3: should fulfill fibo(2p-1) = fibo²(p-1)+fibo²(p)

Written with fast-check:

it("should fulfill fibo(2p-1) = fibo²(p-1)+fibo²(p)", () => {
  // Special case of the property above
  fc.assert(
    fc.property(fc.integer({ min: 1, max: MaxN }), (p) => {
      expect(fibonacci(2 * p - 1)).toBe(
        fibonacci(p - 1) * fibonacci(p - 1) + fibonacci(p) * fibonacci(p)
      );
    })
  );
});

Property 4: should fulfill Catalan identity

Written with fast-check:

it("should fulfill Catalan identity", () => {
  fc.assert(
    fc.property(
      fc.integer({ min: 0, max: MaxN }),
      fc.integer({ min: 0, max: MaxN }),
      (a, b) => {
        const [p, q] = a < b ? [b, a] : [a, b];
        const sign = (p - q) % 2 === 0 ? 1n : -1n; // (-1)^(p-q)
        expect(
          fibonacci(p) * fibonacci(p) - fibonacci(p - q) * fibonacci(p + q)
        ).toBe(sign * fibonacci(q) * fibonacci(q));
      }
    )
  );
});

Property 5: should fulfill Cassini identity

Written with fast-check:

it("should fulfill Cassini identity", () => {
  fc.assert(
    fc.property(
      fc.integer({ min: 1, max: MaxN }),
      fc.integer({ min: 0, max: MaxN }),
      (p) => {
        const sign = p % 2 === 0 ? 1n : -1n; // (-1)^p
        expect(
          fibonacci(p + 1) * fibonacci(p - 1) - fibonacci(p) * fibonacci(p)
        ).toBe(sign);
      }
    )
  );
});

Property 6: should fibo(nk) divisible by fibo(n)

Written with fast-check:

it("should fibo(nk) divisible by fibo(n)", () => {
  fc.assert(
    fc.property(
      fc.integer({ min: 1, max: MaxN }),
      fc.integer({ min: 0, max: 100 }),
      (n, k) => {
        expect(fibonacci(n * k) % fibonacci(n)).toBe(0n);
      }
    )
  );
});

Property 7: should fulfill gcd(fibo(a), fibo(b)) = fibo(gcd(a,b))

Written with fast-check:

it("should fulfill gcd(fibo(a), fibo(b)) = fibo(gcd(a,b))", () => {
  fc.assert(
    fc.property(
      fc.integer({ min: 1, max: MaxN }),
      fc.integer({ min: 1, max: MaxN }),
      (a, b) => {
        const gcdAB = Number(gcd(BigInt(a), BigInt(b)));
        expect(gcd(fibonacci(a), fibonacci(b))).toBe(fibonacci(gcdAB));
      }
    )
  );
});

This property needs a helper function called gcd that could be written as follow:

function gcd(_a: bigint, _b: bigint): bigint {
  let a = _a < 0n ? -_a : _a;
  let b = _b < 0n ? -_b : _b;
  if (b > a) {
    const temp = a;
    a = b;
    b = temp;
  }
  while (true) {
    if (b === 0n) return a;
    a = a % b;
    if (a === 0n) return b;
    b = b % a;
  }
}

---

Back to "Advent of PBT 2021" to see topics covered during the other days and their solutions.

More about this serie on @ndubien or with the hashtag #AdventOfPBT.