DEV Community

Nicolas DUBIEN
Nicolas DUBIEN

Posted on • Updated on

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));
    })
  );
});
Enter fullscreen mode Exit fullscreen mode

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)
        );
      }
    )
  );
});
Enter fullscreen mode Exit fullscreen mode

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)
      );
    })
  );
});
Enter fullscreen mode Exit fullscreen mode

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));
      }
    )
  );
});
Enter fullscreen mode Exit fullscreen mode

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);
      }
    )
  );
});
Enter fullscreen mode Exit fullscreen mode

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);
      }
    )
  );
});
Enter fullscreen mode Exit fullscreen mode

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));
      }
    )
  );
});
Enter fullscreen mode Exit fullscreen mode

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;
  }
}
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)