[ArkPhaze]

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.

[invisal]

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.

[ArkPhaze]

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.

[invisal]

Here is the pattern I just drawn from the above observation:

[invisal]

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.

[ArkPhaze]

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.

[ArkPhaze]

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...

[ArkPhaze]

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) = 349525

My 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 = 450283905890997363

Code:

S(65535) = 1431655765

Then 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...

[invisal]

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

[invisal]

Another interest thing. I can compute F(2^n + 1) = 2^n + 1 where n > 0