+- Sinisterly (https://sinister.li)
+-- Forum: Coding (https://sinister.li/Forum-Coding)
+--- Forum: C, C++, & Obj-C (https://sinister.li/Forum-C-C-Obj-C)
+--- Thread: C++ - Euler 463 (/Thread-C-Euler-463)
RE: C++ - Euler 463 - ArkPhaze - 03-17-2014
Yeah... That and the multiples as I hinted at, but it still doesn't quite get me *much* further. The sequence up to 3^37 is still daunting at this point. That's only in the case with powers of 2, the others are multiplied by 2 each time, and when you get a bit higher, there's almost no real obvious relation between the input and output.
Although an easy check for powers of 2, that's not nearly all of the numbers, and this becomes exponentially less significant once you get into the sufficiently larger numbers for input.
RE: C++ - Euler 463 - invisal - 03-17-2014
I think I am very close to solve this now. I just found
the very amazing pattern.
Code:
#include <iostream>
/*
The function f is defined for all positive integers as follows:
- f(1) = 1
- f(3) = 3
- f(2n) = f(n)
- f(4n + 1) = 2f(2n + 1) - f(n)
- f(4n + 3) = 3f(2n + 1) - 2f(n)
The function S(n) is defined as:
sigma(n, i=1) f(i)
Ex: S(8) = 22 and S(100) = 3604
Find S(3^37). Give the last 9 digits of your answer.
*/
size_t f(size_t n)
{
if (n == 1 || n == 3) return n; // f(1) or f(3)
if (n % 2 == 0) { return f(n / 2); } // f(2n)
size_t x = n / 4;
return n - (x * 4) == 1 ? (2 * f((2 * x) + 1)) - f(x) // f(4n + 1)
: (3 * f((2 * x) + 1)) - (2 * f(x)); // f(4n + 3)
}
size_t S(size_t n)
{
size_t sum = 0;
for (size_t i = 1; i <= n; ++i) sum += f(i);
return sum;
}
int main()
{
// 450283905890997363 = 3^37
// is it just me or is this never going to work with
// even the fastest bruteforst algorithm? Perhaps some
// mathematical trickery is required in this case?
// *most definitely*...
int s = 0;
for(int i = 1; i < 1000; i++) {
int t = f(i);
if (t == 1) {
std::cout << std::endl << "SUM: " << s << std::endl << std::endl;
s = 1;
} else {
s += t;
}
std::cout << t << " ";
}
std::cout << std::endl << "SUM: " << s << std::endl << std::endl;
}Try this, you will know.
RE: C++ - Euler 463 - ArkPhaze - 03-17-2014
Because of the magnitude of the number involved, I think the sum should be calculated by the nth term based on a simplified version of this recurrence algorithm. I knew my code was junk to begin with, because I was never expecting to brute force this problem, but as a test it was good to see the numbers in the sequenced output for more in depth analysis. Thus the goal is to transform this nonlinear expression into a closed form expression.
RE: C++ - Euler 463 - invisal - 03-17-2014
Here is the pattern I just drawn from the above observation:
RE: C++ - Euler 463 - invisal - 03-17-2014
There are two more interesting patterns that I have discovered that can potentially
a closer pattern to solve the problem. I need to confirm it a bit. Then, I will
post more.
RE: C++ - Euler 463 - ArkPhaze - 03-17-2014
(03-17-2014, 02:56 AM)invisal Wrote: I think I am very close to solve this now. I just found
the very amazing pattern.
Code:#include <iostream> /* The function f is defined for all positive integers as follows: - f(1) = 1 - f(3) = 3 - f(2n) = f(n) - f(4n + 1) = 2f(2n + 1) - f(n) - f(4n + 3) = 3f(2n + 1) - 2f(n) The function S(n) is defined as: sigma(n, i=1) f(i) Ex: S(8) = 22 and S(100) = 3604 Find S(3^37). Give the last 9 digits of your answer. */ size_t f(size_t n) { if (n == 1 || n == 3) return n; // f(1) or f(3) if (n % 2 == 0) { return f(n / 2); } // f(2n) size_t x = n / 4; return n - (x * 4) == 1 ? (2 * f((2 * x) + 1)) - f(x) // f(4n + 1) : (3 * f((2 * x) + 1)) - (2 * f(x)); // f(4n + 3) } size_t S(size_t n) { size_t sum = 0; for (size_t i = 1; i <= n; ++i) sum += f(i); return sum; } int main() { // 450283905890997363 = 3^37 // is it just me or is this never going to work with // even the fastest bruteforst algorithm? Perhaps some // mathematical trickery is required in this case? // *most definitely*... int s = 0; for(int i = 1; i < 1000; i++) { int t = f(i); if (t == 1) { std::cout << std::endl << "SUM: " << s << std::endl << std::endl; s = 1; } else { s += t; } std::cout << t << " "; } std::cout << std::endl << "SUM: " << s << std::endl << std::endl; }
Try this, you will know.
EDIT: Ahh you posted again, give me some time to digest the posts and run some tests.
EDIT: scratch that.. I think I can get this to work.
RE: C++ - Euler 463 - ArkPhaze - 03-17-2014
The shitty part is that 3^37 is not a power of 2, and the closest power of 2 just under 3^37 is 2^58. The gap is still significant.
** That power of 2 isn't going to be the term in the sequence anyways...
RE: C++ - Euler 463 - ArkPhaze - 03-17-2014
Otherwise, that might look like this:
Code:
int sum = 0; // summation of sequence
int t = 1; // term
int add = 2; // used to calculate next term
for (int n = 0; n < 10; ++n)
{
sum += pow(4, n);
std::cout << "S(" << t << ") = " << sum << std::endl;
t += add; add *= 2;
}Result from above code:
Code:
S(1) = 1
S(3) = 5
S(7) = 21
S(15) = 85
S(31) = 341
S(63) = 1365
S(127) = 5461
S(255) = 21845
S(511) = 87381
S(1023) = 349525My notes:
Code:
S(1) = 1
S(3) = 5
S(7) = 21
S(15) = 85
S(31) = 341
S(63) = 1365
+2, +4, +8, +16 <-- Powers of 2.
2^58 = 288230376151711744 (closest power of 2 under 3^37)
3^37 = 450283905890997363Code:
S(65535) = 1431655765Then we need a bigger datatype to store the result, not a problem though, I just need to see when to stop this sequence. Just need to write this...
RE: C++ - Euler 463 - invisal - 03-17-2014
Lets call this function R(n)
R(n) = f(2^n) + f(2^n + 1) + .... + f(2^n + n - 1).
The interest part is that if you sort the f(n) by its value. You will get
R(n) = 1 + 3 + 5 + 7 + ..... + 2^n - 1
RE: C++ - Euler 463 - invisal - 03-17-2014
Another interest thing. I can compute F(2^n + 1) = 2^n + 1 where n > 0