1

I am trying to solve a problem from projecteuler.net http://projecteuler.net/problem=14

This is the problem:

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even) n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

I first used a recursive solution, but after 100,000 or so iterations there was a segmentation fault. So I made an iterative solution hoping that would solve the problem. A segmentation fault occurred at the same point. I looked at the stack trace and found that the problem showed up when a value was added to the vector I marked the line below. I thought the vector would automatically resize so I'm really confused about this problem. Thanks for your help. Here's the code:

#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
 int ITERATIONS=100000;

int main()
{
vector<int> maxArray;
vector<int> newArray;
int max_size = 0;
int n = 2;
int collatz = n;
while(n <= ITERATIONS){

#Stack trace error# 
newArray.push_back(collatz);
#Stack trace error#

if(collatz == 1){
++n;
if(newArray.size() > max_size){
maxArray.clear();
for(vector<int>::const_iterator i = newArray.begin(); i < newArray.end(); ++i){
maxArray.push_back(*i);
}
max_size = newArray.size();
}
newArray.clear();
collatz = n;
}
else if(collatz%2 == 0)
collatz = collatz/2;
else
collatz = 3*collatz+1;
}
for(vector<int>::const_iterator i = maxArray.begin(); i < maxArray.end(); ++i){
cout << *i << " "; 
}
cout << "\n" << max_size;
}

The stack Trace:

#0  0x00132416 in __kernel_vsyscall ()
#1  0x002641df in raise () from /lib/i386-linux-gnu/libc.so.6
#2  0x00267825 in abort () from /lib/i386-linux-gnu/libc.so.6 #3  0x001e013d in __gnu_cxx::__verbose_terminate_handler() ()  from /usr/lib/i386-linux-gnu/libstdc++.so.6
#4  0x001dded3 in ?? () from /usr/lib/i386-linux-gnu/libstdc++.so.6
#5  0x001ddf0f in std::terminate() ()  from /usr/lib/i386-linux-gnu/libstdc++.so.6
#6  0x001de05e in __cxa_throw () from /usr/lib/i386-linux-gnu/libstdc++.so.6
#7  0x001de67f in operator new(unsigned int) () from /usr/lib/i386-linux-gnu/libstdc++.so.6
#8  0x08049362 in __gnu_cxx::new_allocator<int>::allocate (this=0xbffff214, 
__n=536870912) at /usr/include/c++/4.6/ext/new_allocator.h:92
#9  0x0804923c in std::_Vector_base<int, std::allocator<int> >::_M_allocate (
this=0xbffff214, __n=536870912)   at /usr/include/c++/4.6/bits/stl_vector.h:150
#10 0x08048e7f in std::vector<int, std::allocator<int> >::_M_insert_aux (
this=0xbffff214, __position=..., __x=@0xbffff220: -91)
at /usr/include/c++/4.6/bits/vector.tcc:327
#11 0x08048bdd in std::vector<int, std::allocator<int> >::push_back (
this=0xbffff214, __x=@0xbffff220: -91)
at /usr/include/c++/4.6/bits/stl_vector.h:834
#12 0x08048897 in main () at iterativeCollatz.cpp:16

4 Answers 4

2

We make the following observations:

  1. The single smallest chain consists of just the number 1. Its length is 1.
  2. Long chains can only be formed by prepending x to a tail chain that begins at either x/2 (if x is even) or 3x+1 (if x is odd). The length of a long chain is 1 plus the length of its tail.
  3. Once the chain starts the terms are allowed to go above one million.
  4. Negative numbers are not really needed to solve this problem.
  5. No chain has length 0.

And we arrive at the following conclusions:

  1. From observations 1 and 2: Once we find the length of a chain beginning at x, we must memoize it. This avoids recomputing the lengths of tails. Furthermore, we can interpret a chain length being 0 (which results by default-constructing a std::size) as "this length has not been computed yet".
  2. From observation 3: For any x > 1000000, if we eventually need to compute the length of the chain beginning at x, nothing guarantees we will be interested in the length of every chain beginning at a y such that x > y >= 1000000. So we should use an associative data structure (such as std::map), not std::vector, for storing the memoized lengths:
  3. From observations 3 and 4: We shall use an unsigned integral type as big as possible. Without going as far as using a bignum library (such as GMP), the type we want is std::uint64_t.
  4. From observation 5: We can use a chain length value of 0 to denote "this chain length has not been computed yet". This is particularly convenient because C++'s associative containers default-construct a value when using operator [] with a key that does not exist in the container, and a default-constructed value of an integral type is initialized to 0.

The resulting program, written using C++11 constructs for convenience, is this:

#include <iostream>
#include <map>
#include <set>
#include <stack>

int main()
{
  typedef std::uint64_t num;

  // ys[x] is the length of the chain starting at x.
  // xms is the set of numbers that yield the longest chains.
  // ym is the length of the longest chain so far.
  std::map<num, num> ys = {{1,1}};
  std::set<num> xms = {1};
  num ym = 1;

  for (num i = 2; i < 1000000; ++i)
  {
    std::stack<num> xs;
    num x = i, y = ys[x];

    // Compute successive chain elements until
    // a base element is reached whose chain
    // length has already been memoized.
    while (!y)
    {
      xs.push(x);
      x = (x & 1) ? (3*x + 1) : (x/2);
      y = ys[x];
    }

    // The lengths of the newly computed elements
    // can be found by repeatedly incrementing
    // the base element's chain length.
    while (!xs.empty())
    {
      x = xs.top();
      ys[x] = ++y;
      xs.pop();
    }

    // Keep track of which number(s)
    // yield the longest chain(s).
    if (y >= ym)
    {
      if (y > ym)
      {
        xms.clear();
        ym = y;
      }
      xms.insert(x);
    }
  }

  for (num xm : xms)
    std::cout << xm << ' ';

  return 0;
}
11
  • Wow incredible. I will be learning from this for weeks. Thanks so much.
    – KarlCobb
    Dec 13, 2013 at 18:07
  • I just updated the collatz variable to uint64_t and my code works without segmentation fault. I'm a little confused why this would matter though. I thought an int would just take up a 4 byte piece of memory and keep updating that one piece. With try catch I can see that the collatz number becomes negative. It seems that the number it should be at would be much below 2 billion which I thought was the limit of a signed int. But it looks like its surpassing that and becoming negative. Thanks for any insight into this.
    – KarlCobb
    Dec 13, 2013 at 19:07
  • It's also really confusing because I'm putting a uint64_t inside of a vector of ints. This also doesn't seem logical that that's acceptable. And it seems the vector wasn't the problem, which also raises a lot of questions about what the real problem was.
    – KarlCobb
    Dec 13, 2013 at 19:23
  • @KarlCobb: The segmentation fault error was most likely trying to access an array (the std::vector's underlying array) using a negative index. To completely rule ever having to deal with negative numbers, I used an unsigned type (std::uint64_t). I should add that to the answer.
    – isekaijin
    Dec 13, 2013 at 19:50
  • @EduardoLeón, I'm sorry to say that when I try to run your code, it doesn't compile and produces a 2552 error: non-aggregates cannot be initialized with initializer list.
    – Chiffa
    Dec 27, 2013 at 19:07
2

The condition i < newArray.end() should be i != newArray.end(). And of course the same applies to i < maxArray.end().

1
  • There never was an issue here, inequalities work fine on random-access iterators.
    – Ben Voigt
    Dec 13, 2013 at 1:18
2
#6  0x001de05e in __cxa_throw () from /usr/lib/i386-linux-gnu/libstdc++.so.6

This call to __cxa_throw indicates a C++ exception is being thrown.

#5  0x001ddf0f in std::terminate() ()  from /usr/lib/i386-linux-gnu/libstdc++.so.6

The std::terminate function exits the application immediately. This can be due to several reasons:

  1. The exception is being thrown in the destructor of an object while another exception is being thrown.
  2. The program does not have a try...catch handler.

In this case, option 2 is the most likely. Running the program should result in something like:

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Program received signal SIGABRT, Aborted.

This gives you the message of the exception (the what output).

#7  0x001de67f in operator new(unsigned int) () from /usr/lib/i386-linux-gnu/libstdc++.so.6

This line indicates that the exception was triggered when allocating memory (most likely a std::bad_alloc, indicating out-of-memory).

Therefore, I would check that you are not allocating large vectors that are running out of memory.

NOTE: You can add your own try...catch handler by writing something like:

try
{
    // Your code here.
}
catch (const std::exception &e)
{
    std::cout << "Error: " << e.what() << std::endl;
}

The vector implementations will increase the size of the vectors whenever they no longer have any room. This is typically done by doubling the space (2, 4, 8, 16, ...). This will get very large quickly, and you have 2 vectors growing to fit 100000 elements. Also note that while growing the vector, it needs to keep the old data around to copy into the new vector.

You can use the reserve method on maxArray and newArray to set the desired size before the loop. That is:

maxArray.reserve(ITERATIONS);
newArray.reserve(ITERATIONS);

This will also ensure cleaner performance as the vectors don't have to increase the internal data array to add the new elements.

4
  • I can check that I'm not allocating too much memory to the vector. But then the program will just close down. I would still like a method to find the answer. Is there a way to get the answer without a segmentation fault? Thanks
    – KarlCobb
    Dec 13, 2013 at 1:02
  • @KarlCobb If you put the vectors before the try...catch, you can print the capacity and size values. You could also use a memory allocation visualizer -- comething simple like GNOME's system monitor (or the equivalent application on the OS you are using)
    – reece
    Dec 13, 2013 at 1:09
  • You can also use gdb commands to goto the operator new stack frame and print out the size value passed to it.
    – reece
    Dec 13, 2013 at 1:21
  • Thanks a lot reece. I used the top command and saw that my program was taking 25% of the memory and didn't seem to increase after that point. Basically I think this program has reached its limit on my system. Even reserving more memory than the number held in ITERATORS doesn't allow my memory to increase much and actually decreases at a certain point. If your machine can get an answer please inform me. I'm not sure the goto statement will give me any more information than printing .size() or .capacity() but I will look into that. Thanks again.
    – KarlCobb
    Dec 13, 2013 at 2:03
0

I've tested your code and there is no SIGSEGV, maybe you should give out more information.

Here is my suggest:

The vector class has a member function called capacity(), maybe you should check this out.

1
  • If the ITERATOR variable is set to 1,000,000 it crashes. The program as is does not crash. Sorry about that.
    – KarlCobb
    Dec 13, 2013 at 1:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.