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; }
If you want the truth to stand clear before you, never be for or against. - Sent-ts'an
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; }
If you want the truth to stand clear before you, never be for or against. - Sent-ts'an
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!
If you want the truth to stand clear before you, never be for or against. - Sent-ts'an
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.
If you want the truth to stand clear before you, never be for or against. - Sent-ts'an