On the one hand if it works it works. On the other hand it looks like it works if you change x.
What if x is divisible by 4 for example?
It’s seems like it’s in between working for this number and working for any number 
It might be why I found it confusing
This one is interesting, using pythons idea that integers can be considered true in booleans operations like not (except zero which is false) and I guess that not(none) is true?
I should probably just write my own versions of some of these, but it’s kind of fun to comment or ask questions on some of the other code and languages to learn something.
I also don’t want to just write the same but possibly worse version of someone else’s code, possibly in the same or another language 
The thread moves faster than I do
Ah, indeed, because we only ask for division by two once. That part needed its own loop. Good catch.
You can include Math to put all the methods of Math into your current module.
That’s probably fine for these challenges. Trying to understand the exact implications (or why you can’t get just one method like in Python) will take you down a deep ruby rabbit hole though.
so f(n) can be calculated in O(ln(n)) by the fast power algorithmn
let
then
So let’s suppose F_2=2, like in that problem.
Then I want to compute C_n, the sum of every third term starting from F_2, since that’s supposed to be all the even ones?
Except how do I know what n is here? Would I need a bound on when F_{3n+2}< N where N is given like in the problem as 4e6?
So if one solves the three coupled equations and one knows the right bound then one does C_n for that n?
Edit: Actually if I want C_n it looks like from equation 1 and 3 it’s just (f(3n+4)-1)/2 ? So I still need the right n and some way to compute f like the one @antonTobi mentioned maybe with powers and rounding of the golden ratio?
@Glunkolin was pointing out that computing f(n) is done faster via the matrix representation since you can use exponentiation by squaring.
Computing n is still an interesting question but surely that can’t be the bottleneck…
I don’t really know how to analyze the complexity of calculating log(sqrt(5)*N, phi). Is there a nicer way without any fractional arithmetic?
n can be located by a binary search, and the fast power algorithm is itself a binary search.
I was just thinking about this, but if we do a binary search where we have to evaluate f(n) at every step, isn’t that O(log n log n)? I guess we get around this by saving earlier computed values for f(n)?
So I don’t know what I’m supposed to take out of this, that is the key points. Possibly because I’m jumping between posts a bit.
I try do a fast exponential on matrix multiplication to get the f(n)’s that I want quickly?
I’m not really proficient with Big Oh notation and algorithms, but computing f(n)‘s by repeated squaring in matrix multiplication is faster than just generating a list of the f(n)’s (by ordinary addition)?
Is that in this particular case because I want every third term only or generally?
Why do I need the A_n, B_n or C_n in that case?
Yes, O(log n) is much faster than O(n) for large n.
Because f(n) is only the single Fibonacci terms, we want the sum of every third term up to a certain point, which is given by C_n (which happens to be expressible in terms of f(n)).
I mean I know that much
I meant more computationally, to figure out if an algorithm has a certain O(…). I know one can discard slower growing terms and things to simplify.
Right right, so now C_n might only need to be computed from one term, and now one just has to figure out what n is, which either has a nice closed form or it needs to be found in some way without computing more Fibonacci terms in the process right? Or not many anyway.
Edit:
I guess this is what this is saying
I just hone in by checking if f(3n+2) is above or below the given number, trying to halve the number of options to check at each point?
So what we want is to find the largest f(n) below 4 million.
We can square to get f(1), f(2), f(4), f(8)… etc. until we surpass 4 million with f(2^(k+1)).
Then we go back one step to f(2^k). Now we can compute f(2^k + 1), f(2^k + 2), f(2^k + 4)… etc. (reusing the f(2^k) values we just computed) until we again surpass 4 million.
Repeat as necessary.
But again, this feels a little O(log n log n)-ish to me…
@Glunkolin could you explain a little more how to locate n by binary search?
The great thing about logs, is that log(n)^2 or log(n*log(n)) ?
Again maybe that’s clear if I understood how to compute it
I meant the former 
But also I was just throwing a second log in there without too much thought (hence the -ish), I’m not sure what the actual complexity there is.
I’m also hazy on some of the details of Big Oh. I generally assume that a single multiplication step is O(1), but of course that doesn’t hold when the numbers get really big.
If one performs an O(log(n)) operation at every step of a binary search, then yeah it would be O(log2(n))
Still faster than O(N) tho!
Right! Already a nice improvement. But it seems ridiculous that determining n would be the hardest part of the problem! 
Maybe this?
Feel free to move onto the next problem in a couple of hours, if you want.
I might be lounging with Netflix.
