C++ - Euler 463 - Printable Version

C++ - Euler 463 - Printable Version

+- 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)

Pages: 1 2 3

C++ - Euler 463 - ArkPhaze - 03-16-2014

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 n * 0.5; }                   // 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*...
  std::cout << S(100) << std::endl;
}

Anyone else brave enough to try this one or have any suggestions? Smile

My function seems fine, I get S(8) = 22, but I'm wondering if there's something still wrong with it as I don't get 3604 with S(100), but rather 3716... Euler has been wrong in the past with wording and other example answers like this, I just don't know at this point though. It is the newest problem on the site... But I've looked this over a few times and I don't see how my function could be wrong.

The magnitude of the number is not what I'm worried about, it's the continual sum.

RE: C++ - Euler 463 - invisal - 03-16-2014

Code:
if (n % 2 == 0) { return n * 0.5; }

I think it should be

Code:
if (n % 2 == 0) return f(n / 2);

RE: C++ - Euler 463 - invisal - 03-16-2014

I think

Code:
if (n % 2 == 0) { return n * 0.5; }

should be

Code:
if (n % 2 == 0) { return f(n / 2); }

Another problem is:

Code:
for (size_t i = 1; i < n; ++i) sum += f(i);

It should be

Code:
for (size_t i = 1; i <= n; ++i) sum += f(i);

RE: C++ - Euler 463 - Ex094 - 03-16-2014

(03-16-2014, 01:54 PM)invisal Wrote:
Code:
if (n % 2 == 0) { return n * 0.5; }

I think it should be

Code:
if (n % 2 == 0) return f(n / 2);

I was able to reach 3665 by:

Code:
if (n % 2 == 0) { return n * 0.1; } //.1 instead of .5

RE: C++ - Euler 463 - ArkPhaze - 03-16-2014

Ahh fixed:

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 * 0.5); }                // 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*...
  std::cout << S(100) << std::endl;
}

I didn't see that, I ended up trying to start this problem at midnight yesterday. Half of the input should go into the function, correct.

@Ex094 - That's not how functions work though.

I think the next step would be to reduce the recursion here, but I still don't know how I'm supposed to get a result for the sum up to 3^37.

RE: C++ - Euler 463 - invisal - 03-16-2014

I don't know if this help, but

F(4n + 0) + F(4n + 1) + F(4n + 2) + F(4n + 3) = F(2n) + 6F(2n + 1) - 3F(n)

RE: C++ - Euler 463 - invisal - 03-16-2014

I strongly believe that the trick is in the SUM. Since the recursive has some negative terms.
It should somehow knock each other out.

RE: C++ - Euler 463 - ArkPhaze - 03-16-2014

I optimized the function a bit:

Code:
size_t f(size_t n)
{
  while (!(n & 1)) n /= 2; // all other functions take in an odd number
  if (n < 4) return n;
  size_t x = n / 4;
  size_t x4 = x * 4;
  if (n - x4 == 1) return (2 * f((2 * x) + 1)) - f(x);
  if (n - x4 == 3) return (3 * f((2 * x) + 1)) - (2 * f(x));
  return 0;
}

I'll take a look at the generalization of the sequence.

Here's some values:

Code:
> f(1) = 1
> f(2) = 1
> f(3) = 3
> f(4) = 1
> f(5) = 5
> f(6) = 3
> f(7) = 7
> f(8) = 1
> f(9) = 9
> f(10) = 5
> f(11) = 13
> f(12) = 3
> f(13) = 11
> f(14) = 7
> f(15) = 15
> f(16) = 1
> f(17) = 17
> f(18) = 9
> f(19) = 25
> f(20) = 5
> f(21) = 21
> f(22) = 13
> f(23) = 29
> f(24) = 3
> f(25) = 19
> f(26) = 11
> f(27) = 27
> f(28) = 7
> f(29) = 23
> f(30) = 15
> f(31) = 31
> f(32) = 1
> f(33) = 33
> f(34) = 17
> f(35) = 49
> f(36) = 9
> f(37) = 41
> f(38) = 25
> f(39) = 57
> f(40) = 5

Primes seem to be a bit more unique.

RE: C++ - Euler 463 - ArkPhaze - 03-16-2014

You can see the obvious pattern for this set of results, the rest are messed up.

Code:
> 1 = f(1)
> 1 = f(2)
> 1 = f(4)
> 1 = f(8)
> 1 = f(16)
> 1 = f(32)
> 3 = f(3)
> 3 = f(6)
> 3 = f(12)
> 3 = f(24)
> 5 = f(5)
> 5 = f(10)
> 5 = f(20)
> 5 = f(40)
> 7 = f(7)
> 7 = f(14)
> 7 = f(28)
> 9 = f(9)
> 9 = f(18)
> 9 = f(36)

RE: C++ - Euler 463 - invisal - 03-17-2014

Well, it is obvious that F(2^n) = 1.

Proof by Induction.

Base Case: F(2^0) = F(1) = 1
Inductive Step: we assume by induction that F(2^n) = 1 holds for n >= 0.
F(2^(n+1)) = F(2^n) = 1.
Therefore, by induction, F(2^n) = 1 for every integer n >= 0