The worst case is with all p[i][x] equal to each other, which gives N^2 (N(N-1)/2 distance calculations). It appears the average complexity is logarithmic though, which is pretty cool!

Nice. https://oeis.org/A016189 for any wondering

I was bored and scraped a bunch of the javascript submissions to this problem, and this one appears to be the fastest out of all the ones I tested! (280 out of the 547 js submissions). Commenting mostly as a bookmark :)

Fun! But it's not quite right! For example your version of productFib(24) gives (4,6,true), when 4 and 6 aren't fibonacci numbers. Other examples are 60, 77, 135, 160, and 198. These are the product of two numbers that very closely have a golden ratio between them, but they don't appear in the fibonacci sequence.

See https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression

phi=(sqrt(5)+1)/2 = 2/(sqrt(5)-1) ~= F(n+1)/F(n) for large n. So F(n) ~= F(n+1)/phi, where by ~= I mean "approximately equals". It turns out the round function can be used since F(n+1)/phi will be within 0.5 of F(n).