I don't think I'm going to win any speed contests hahaha
Cobbled together from scraps of info on the web
Code:$ time ./euler_443 2744233049300770 real 0m27.233s user 0m27.152s sys 0m0.003s
I found a C++ solution online that works. It was written by a bad programmer but paring it down yields a 34 line program.
Code:#include <iostream> #include <vector> #include <cmath> typedef long long int64; template <typename T> T gcd(T x, T y) { for (T t; x; ) { t = x; x = y % x; y = t; } return y; } int64 find(int64 n) { int64 g = n * 3; int end = sqrt(n); for (int i = 1; i <= end; ++i) { g += gcd(g, n + i); if (g == (n + i) * 3) { n += i; i = 0; } } return n; } int main() { const int64 N = 1e15; int64 n = 9; do { int64 x = find(n); n = x * 2; } while (n <= N); std::cout << n + N << '\n'; return 0; }
A little inaccuracy saves tons of explanation. - H.H. Munro
It's no faster than mine :/ Is that actually fast enough for Project Euler?
Much better:
Edit: Hint the primes were important after allCode:$ time ./euler_443 2744233049300770 real 0m1.016s user 0m0.984s sys 0m0.029s
Something like this?
Code:#include <stdio.h> typedef long long Int; Int find_lowest_prime_factor(Int x) { if (x % 2 == 0) return 2; for (Int d = 3; d * d <= x; d += 2) if (x % d == 0) return d; return x; } int main() { Int limit = 1e15; Int i1 = 20; for (;;) { Int q = 2 * i1 - 1; Int p = find_lowest_prime_factor(q); Int k = (p - 3) / 2; Int i2 = i1 + k + 1; if (i2 > limit) break; i1 = i2; } printf("%lld\n", 3 * i1 + (Int)(1e15 - i1)); return 0; }
A little inaccuracy saves tons of explanation. - H.H. Munro
I hope the OP learned something from their homework. I guess at least a process of problem solving has been documented even if the intermediate steps towards arriving at a fast solution are somewhat vague or missing completely (mostly because there is no way I'm going to take a photo of my piece of paper with scribbles all over it).
It's nice to see the simpler solution win!
Maybe a segmented sieve would work better?
Anyway, it's bedtime for me.
Later!
A little inaccuracy saves tons of explanation. - H.H. Munro
Did you try printing out lists of numbers like john.c suggested? I ended up with a fourth list as well and looked at the numbers, made some observations, graphed them (this helped) and scribbled on paper. Doing this a pattern does emerge. Edit: did you read where I said that the primes are important? (and 9 is as well)
I can explain it, but you might want to try it yourself first.
What's this homework for?
Last edited by Hodor; 12-12-2019 at 04:41 PM.
I vote to not explain it to him. If he can't figure it out from what's been given so far then that's too bad.
A little inaccuracy saves tons of explanation. - H.H. Munro