generators anyone?
problem 2, Python
def fib(max_val):
a = b = 1
while a < max_val:
yield a
a, b = b, a+b
print(f'Solution: {sum(x for x in fib(4e6) if x % 2 == 0)}')
2 Likes
That’s roughly what I had in mind! Φ is probably a friendlier constant than the usual culprits, as you don’t have to compute nasty limits to get good decimal precision.
I’m still a bit confused as to where the sqrt(5) in the denominator comes from.
I did it with generators at first too but then decided to go back to the 1 function no loops solution instead. I didn’t like that you need 2 loops with the generator.
1 Like
haha i love the recursive soln!
p.s. does js have an equivalent to generators?
It comes from the closed form expression (“Binet’s formula”) linked by shinuito above:
Since |ψ| < 1, that term quickly becomes negligible, so φ^n/sqrt(5) rounded to the nearest integer is actually exactly F_n for all n >= 0.
Also, since ψ < 0, the “error” is alternately positive and negative, meaning that errors of successive terms cancel out a bit in the sum. I wasn’t really confident before running the calculation that my approach above would give exactly the right answer, but I was pretty sure it wouldn’t be off by more than 1.
4 Likes
Yes of course. I’m on my phone but it’s the “function*” notation. It can also be part of an object and an es6 class, and can be nested. The only thing it doesn’t have is the arrow function implementation of it. The rest is the same as it is in python.
1 Like
Nice tip about the 4e6 for 4000000 syntax. Especially since Python doesn’t support Ruby’s 4_000_000. I see benjito used it as well.
When I had a number that big in Python, I’d always end up commenting
4000000 # 4,000,000
2 Likes
Let’s move on.
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
Here, I’ll even supply commas:
600,851,475,143
I seem to remember that the word “sieving” comes up frequently when this problem is discussed.
I remember back in pascal days in the college I was doing it as 4*1000*1000.
2 Likes
One-liner
4 Likes
I kind of expect this to be the answer in some more high level languages or when importing a package 
Doesn’t return the largest prime factor, it returns all prime factors (among other things).
Perhaps it’s bad style to use a break statement, but the loop is simple and worked on the first try, so I’m fine with it.
There are, no doubt, more idiomatic ways to code. In another language I might well use a different loop structure. I’d probably do it the same way in at least C, though.
Python
def problem_3(x):
from math import sqrt;
from math import floor;
n = x;
sqrtX = floor(sqrt(x));
sqrtN = 0;
if n % 2 == 0:
n /= 2;
while n > sqrtX:
sqrtN = floor(sqrt(n));
for i in range(3, sqrtN, 2):
if n % i == 0:
n /= i;
break;
return int(n);
See PEP 515 – Underscores in Numeric Literals | peps.python.org. Not commas, but you can actually put underscores in the middle of numeric literals for similar effect: 4_000_000. I wasn’t aware of this before looking it up, but I knew there was something similar in C++ (4'000'000)
Possibly better in the sense that we wouldnt be doing float-int comparisons anymore.
1 Like
I feel like that relation isn’t immediately obvious but it’s quite cool
Ruby in the same style
def problem_3(x)
n = x;
sqrtX = Math.sqrt(x).floor();
sqrtN = 0;
if n % 2 == 0
n /= 2;
end
while n > sqrtX
sqrtN = Math.sqrt(n).floor();
for i in (3..sqrtN).step(2)
if n % i == 0
n /= i;
break;
end
end
end
return n;
end
Is there a way to call sqrt out of Math, so that I don’t have to use the full name Math.sqrt?
Like how Python has from math import sqrt.
Is the idea…
Take the number and keep dividing out all of the smallest factors until you’re left with the biggest prime?
Something like that?
Exactly.
Explanation
- Check whether n is even. If it is, divide by two.
- Count through the odd numbers in n until you reach a factor.
- Divide n by the factor.
- Keep on doing that until the n you’re left with is <= the square root of its original value.
I don’t actually need to calculate sqrtN, since we break on hitting a factor anyway. So it’s a wasted calculation, but it’s nice to put a sensible bound on the for loop.
Hmm, or perhaps I do need it. Throws an error when I try to get rid of it… whatever. The code works.
1 Like
Problem 3, unoptimized Python
def largestFactor(n):
for i in range(2, n):
if n % i == 0:
return n // i
def largestPrimeFactor(n):
f = largestFactor(n)
if not f: return n
return largestPrimeFactor(f)
print(largestPrimeFactor(600851475143))
Note how I saved some characters by looping up to n instead of sqrt(n) 
Edit:
Much shorter version
def f(n):
for i in range(2, n):
if n % i == 0:
return f(n // i)
return n
print(f(600851475143))
2 Likes
