Stuck in an infinite loop? (May be)

Question

I'm trying to execute Project Euler Problem 14 in C ++, and I'm honestly stuck. Right now, when I run the problem, it is stuck on So Far: the number with the highest score: 113370 with the number 155 Until now: the number with the highest score, but when I try to change the value I am to 113371, it works. What's happening?

The question arises:

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 above rule and starting at 13, we create the following Sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 You can see that this sequence (starting from 13 and ending with 1) contains 10 terms. Although this has not yet been proven (Collatz problem), it thought that all start numbers end with 1. Which start number, less than a million, produces the longest chain?

#include<stdio.h>
int main() {
    int limit = 1000000;
    int highNum, number, i;
    int highCount = 0;
    int count = 0;
    for( number = 13; number <= 1000000; number++ )
    {
        i = number;
        while( i != 1 ) {
            if (( i % 2 ) != 0 ) {
                i = ( i * 3 ) + 1;
                count++;
            }
            else {
                count++;
                i /= 2;
            }
        }
        count++;
        printf( "So Far: the number with the highest count: %d with the count of %d\n",
                     number, count );
        if( highCount < count ) {
            highCount = count;
            highNum = number;
        }
        count = 0;
        //break;
    }
    printf( "The number with the highest count: %d with the count of %d\n",
            highNum, highCount );
}

Answer 1

You get integer overflow. Update your code and see for yourself:

if (( i % 2 ) != 0 ) {
    int prevI = i;
    i = ( i * 3 ) + 1;
    if (i < prevI) {
        printf("oops, i < prevI: %d\n", i);
        return 0;
    }
    count++;
}

You must change the type ito long longor unsigned long longto prevent overflow.

^{(And yes, cache intermediate results)}

Answer 2

( ).
, :

#include <stdio.h>

static int collatz[4000000];
unsigned long long collatzmax;

int comp(unsigned long long i) {
  if(i>=sizeof collatz/sizeof*collatz) {
      if(i>collatzmax)
        collatzmax = i;
      return 1 + comp(i&1 ? 3*i+1 : i/2);
  }
  if(!collatz[i])
      collatz[i] = 1 + comp(i&1 ? 3*i+1 : i/2);
  return collatz[i];
}

int main() {
  collatz[1] = 1;
  int highNumber= 1, highCount = 1, c;
  for(int i = 2; i < 1000000; i++)
    if((c = comp(i)) > highCount) {
      highCount = c;
      highNumber = i;
    }
  printf( "The number with the highest count: %d with the count of %d\n",
        highNumber, highCount );
  printf( "Highest intermediary number: %llu\n", collatzmax);
}

coliru: http://coliru.stacked-crooked.com/a/773bd8c5f4e7d5a9

: http://coliru.stacked-crooked.com/a/2132cb74e4605d5f

The number with the highest count: 837799 with the count of 525
Highest intermediary number: 56991483520

BTW: , 36 .

Answer 3

. .

- :

void compute(std::map<std::uint64_t, int>& counts, std::uint64_t i)
{
    std::vector<std::uint64_t> series;
    while (counts[i] == 0) {
        series.push_back(i);
        if ((i % 2) != 0) {
            i = (i * 3) + 1;
        } else {
            i /= 2;
        }
    }
    int count = counts[i];
    for (auto it = series.rbegin(); it != series.rend(); ++it)
    {
        counts[*it] = ++count;
    }
}

int main()
{
    const std::uint64_t limit = 1000000;

    std::map<std::uint64_t, int> counts;
    counts[1] = 1;
    for (std::size_t i = 2; i != limit; ++i) {
        compute(counts, i);
    }
    auto it = std::max_element(counts.begin(), counts.end(),
        [](const std::pair<std::uint64_t, int>& lhs, const std::pair<std::uint64_t, int>& rhs)
        {
            return lhs.second < rhs.second;
        });
    std::cout << it->first << ":" << it->second << std::endl;
    std::cout << limit-1 << ":" << counts[limit-1] << std::endl;
}

(10 )

Answer 4

!

typedef std::uint64_t num;  // largest reliable built-in unsigned integer type

num collatz(num x)
{
    return (x & 1) ? (3*x + 1) : (x/2);
}

Then the value collatz(x)depends only on x, and not on when you call it. (In other words, it collatzis a pure function .) As a result, you can memoize values collatz(x)for different values x. For this purpose you can use std::map<num, num>or std::unordered_map<num, num>.

For reference, here is a complete solution.

And here it is on Coliru with synchronization (2.6 seconds).