C++

Forum

 
Ulam conjecture

Pages: 12
algmaster (13)
Hello, I have a problem. I have to find a starting number (under 10^18) based on the length of the sequence (it is a collatz problem where from the starting number if the number is even you have to divide it by 2 and if it is odd you have to multiply it by 3 and then add 1 to it. You do it until you get 1). For example if the number given in the input is 8, the possible output can be 3 (3 10 5 16 8 4 2 1). For the limits of 1, 800 for the length of the sequence you have 10 seconds to give the solution, so checking all the possibilities of the starting number from 1 to 10^18 is too slow. I tried to do it recursively starting from 1 (from the end (if (n-1)%3==0 && ((n-1)/3)%2!=0 && ((n-1)/3)%3!=0 && (n-1)/3!=1
we call function((n-1)/3))) and then just below if (n*2<=10^18) call function(n*2)) but the biggest length that it answered to was 840 (for bigger numbers it did not output anything) and my program did it in 7 seconds, so I have a feeling that doing it this way is also too slow. Thanks in advance.
Last edited on
Ganado (6812)
I don't believe there's a trick for the Collatz/Ulam problem to reduce the complexity. You can combine the *3+1 and /2 operations in to one combined operation, but that probably won't be good enough.

Whether you do recursion or iteration, you might want to implement some sort of memoization to keep track of number crunching that has already been done.
(Normal looping/iteration tends to be easier for us people to grasp, imo.)

https://en.wikipedia.org/wiki/Memoization

For example, you already calculated collatz(50), so you can store it in a map, instead of recalculating the entire sequence starting from 50.
Last edited on
kbw (9488)
BTW, your example isn't quite right.
For example if the number given in the input is 8, the possible output can be 3 (3 10 5 16 8 4 2 1).

I would have thought that for 8, the output is {4, 2, 1}.

But yeah, as @Ganado said above.
lastchance (6980)
@algmaster,
If you want a sequence of LENGTH 8, then starting at any of 3, 20, 21 or 128 would give a sequence of that length. Is any of those four a valid answer?

Could you explain your problem a bit better. Are you saying that you want the starting point for a sequence of length, say, 800?
algmaster (13)
Yes, any starting number will be good if the length of the sequence starting from it is the one given in the input. Also I would like to reply to Ganado. In this task we have to answer only to one number, so we do the calculations only once.
lastchance (6980)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
#include <iostream>
using namespace std;

using INT = unsigned long long;

//======================================================================

bool sequence( INT x, int L, INT &result )
{
   if ( L == 0 )
   {
      result = x;
      return true;
   }

   // Try the smaller predecessor first
   if ( x > 4 && x % 3 == 1 ) 
   {
      INT test = ( x - 1 ) / 3;
      if ( test % 2 && sequence( test, L - 1, result ) ) return true;
   }

   // Then try the larger predecessor;
   if ( x < 500000000000000000 ) return sequence( 2 * x, L - 1, result );

   // Otherwise, failure within the search range
   return false;
}

//======================================================================

int Collatz( INT x )
{
   int N = 1;
   for ( ; x != 1; N++ ) x = ( x % 2 ? 3 * x + 1 : x / 2 );
   return N;
}

//======================================================================

int main()
{
   int L;
   cout << "What length of sequence do you want? ";   cin >> L;
   INT result;
   if ( sequence( 1uLL, L - 1, result ) ) 
   {
      cout << "Sequence start: " << result << '\n';
      cout << "Check: length of sequence = " << Collatz( result ) << '\n';
   }
   else
   {
      cout << "Not found\n";
   }
}


What length of sequence do you want? 8
Sequence start: 3
Check: length of sequence = 8


What length of sequence do you want? 800
Sequence start: 125304824229875851
Check: length of sequence = 800


algmaster (13)
Thanks a lot. However the code that I have written is very similar. It answers in 7 seconds for 840 and does not output anything for bigger numbers (the limit is 1800). Unfortunately the tester gives only 60 points out of 100 for this way of solving the problem.
lastchance (6980)
Well, I tightened the bounds a bit and managed to get a sequence length of 900. But it took longer than 10 seconds.

So, a new method might be better. Perhaps you can look at two (or more) steps in one go.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
#include <iostream>
using namespace std;

using INT = unsigned long long;

//======================================================================

bool sequence( INT x, int L, INT &result )
{
   if ( L == 0 )
   {
      result = x;
      return true;
   }

   // Try the smaller predecessor first
   if ( x >= 16 && x % 6 == 4 )
   {
      if ( sequence( ( x - 1 ) / 3, L - 1, result ) ) return true;
   }

   // Then try the larger predecessor
   if ( x < 500000000000000000 ) return sequence( 2 * x, L - 1, result );

   // Otherwise, failure within the search range
   return false;
}

//======================================================================

int Collatz( INT x )
{
   int N = 1;
   for ( ; x != 1; N++ ) x = ( x % 2 ? 3 * x + 1 : x / 2 );
   return N;
}

//======================================================================

int main()
{
   int L;
   cout << "What length of sequence do you want? ";   cin >> L;
   INT result;
   if ( sequence( 1uLL, L - 1, result ) ) 
   {
      cout << "Sequence start: " << result << '\n';
      cout << "Check: length of sequence = " << Collatz( result ) << '\n';
   }
   else
   {
      cout << "Not found\n";
   }
}


What length of sequence do you want? 900
Sequence start: 427779377093643186
Check: length of sequence = 900

Last edited on
algmaster (13)
That is a great idea but how can we do two steps in one go if we want to look at every possibility?
lastchance (6980)
You don't have to look at every possibility.

Doing two steps in one go may (a) give you a better handle on the predecessor to try first; (b) allow you to temporarily go outside the calculable bounds, as long as the final number (which is the start of the Collatz sequence) is < 10^18.

Or they may simply be a much better way.
algmaster (13)
Would you be able to explain your concept to me in more detail? Not everything here is clear to me.
lastchance (6980)
algmaster wrote:
Would you be able to explain your concept to me in more detail?


Trying to do 2 steps back along the sequence might (in principle) make it slightly quicker and could also allow you to stray (temporarily) out of bounds of an unsigned long long (although that would make the sequence length difficult to check in c++; have to check it with Python instead, because the latter allows arbitrarily large integers).

The following code finds a sequence of length 1000, but it takes over a minute.

Are you sure that the limit is 1800 and not 800? 800 is easily accessible in 10 seconds, but 1800 is not. Actually, if you extrapolate from the table on the Collatz conjecture in Wikipedia then there may not be any under starting value 1018.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
#include <iostream>
#include <limits>
using namespace std;

using INT = unsigned long long;
INT BIG = numeric_limits<INT>::max();
INT HALF = BIG / 2;
INT QUARTER = BIG / 4;
INT ALLOWED = 1'000'000'000'000'000'000;

//======================================================================

bool sequence( INT x, int L, INT &result )
{
   if ( L == 0 )
   {
      result = x;
      return x < ALLOWED;
   }

   if ( L > 1 )                        // Try to do 2 steps at once
   {
      // Try the smallest predecessor first
      if ( x > 4 && x % 6 == 4 )
      {
         if ( sequence( x - ( x - 1 ) / 3 - 1, L - 2, result ) ) return true;
      }
   
      if ( x > 2 && x < HALF && x % 3 == 2 )    // The "HALF" is to allow the sequence to be checked!
      {
         if ( sequence( x - ( x - 2 ) / 3 - 1, L - 2, result ) ) return true;
      }
   
      if ( x <= QUARTER ) return sequence( 4 * x, L - 2, result );

   }
   else                                // Just one step
   {
      if ( x > 4 && x % 6 == 4 )
      {
         if ( sequence( ( x - 1 ) / 3, L - 1, result ) ) return true;
      }

      if ( x <= HALF ) return sequence( 2 * x, L - 1, result );
   }

   // Otherwise, failure within the search range
   return false;
}

//======================================================================

int Collatz( INT x )
{
   int N = 1;
   for ( ; x != 1; N++ ) x = ( x % 2 ? 3 * x + 1 : x / 2 );
   return N;
}

//======================================================================

int main()
{
   int L;
   cout << "What length of sequence do you want? ";   cin >> L;
   INT result;
   if ( sequence( 1uLL, L - 1, result ) ) 
   {
      cout << "Sequence start: " << result << '\n';
      cout << "Check: length of sequence = " << Collatz( result ) << '\n';
   }
   else
   {
      cout << "Not found\n";
   }
}


What length of sequence do you want? 1000
Sequence start: 243400039693541110
Check: length of sequence = 1000


Last edited on
algmaster (13)
Yes, the problem is that we do not allow the numbers in the sequence to be bigger than 10^18. In the task it is said that the starting number can not be bigger than 10^18, but other numbers can be arbitrarily large. When I changed the if statement, so it allows x to hit 9*10^18 it answered to 1000 in 13 second. But in that code the starting number did not have an additional limit for the starting number so it was also 9*10^18. When added a limit for the starting number of 10^18 my program did not output anything again, but I think we have to find a trick like using only the modulo or something. I am not really familiar with bit masks and if we can do the operations we need on them (I’m talking about bit masks that hold more than 66 bits if it makes any difference), but maybe we should go in this direction. Thanks a lot.
mbozzi (3933)
These sequences always converge to 1, so that means (heuristically) that the process of getting to 1 involves at least three divisions by two for each two multiplications by three. Can this be used to search the most-promising branches first?

Maybe the most-promising branches are those that optimize the multiplications/divisions ratio?
Last edited on
lastchance (6980)
...
Last edited on
lastchance (6980)
Finally got to sequence length 1800.

But it still takes excessive time for large sequence lengths (and requires user input for L > 1300).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
#include <iostream>
#include <limits>
#include <set>
using namespace std;

using INT = unsigned long long;
INT BIG = numeric_limits<INT>::max();
INT HALF = BIG / 2;
INT QUARTER = HALF / 2;   INT THREEQUARTERS = 3 * QUARTER;
INT EIGHTH = QUARTER / 2;
INT ALLOWED = 1'000'000'000'000'000'000;

//======================================================================

int Collatz( INT x )
{
   int N = 1;
   for ( ; x != 1; N++ ) x = ( x % 2 ? 3 * x + 1 : x / 2 );
   return N;
}

//======================================================================

int main()
{
   int L;
   cout << "What length of sequence do you want? ";   cin >> L;

   int MAX_CANDIDATES = 1000;       // (OK up to at least L=1300)
   if ( L > 1300 )
   {
      cout << "Maximum number of candidates to keep at each step? ";
      cin >> MAX_CANDIDATES;
   }

   set<INT> S = { 1 };
   int i = 2;
   while ( i <= L )
   {
      // Work from the smallest MAX_CANDIDATES elements
      set<INT> oldS;
      auto it = S.begin();
      int num = 0;
      while ( num < MAX_CANDIDATES and it != S.end() )
      {
         oldS.insert( *it );
         it++;
         num++;
      }

      S.clear();
      for ( INT x : oldS )
      {
         if ( i == L )           // last step
         {
            if ( x > 4 && x % 6 == 4 ) S.insert( ( x - 1 ) / 3 );
            if ( x <= HALF ) S.insert( 2 * x );
         }
         else if ( i == L - 1 )  // last two steps
         {
            if ( x > 4 && x % 6 == 4 ) S.insert( x - ( x - 1 ) / 3 - 1 );
            if ( x > 2 && x <= HALF && x % 3 == 2 ) S.insert( x - ( x - 2 ) / 3 - 1 );
            if ( x <= QUARTER ) S.insert( 4 * x );
         }
         else                    // three steps in one go
         {
            if ( x > 7 && x % 18 == 16 ) S.insert( ( x - 7 ) / 9 * 2 + 1 );
            if ( x > 4 && x <= THREEQUARTERS && x % 6 == 4 ) S.insert( ( x - 1 ) / 3 * 4 );
            if ( x > 2 && x <= HALF && x % 3 == 2 ) S.insert( ( x - 2 ) / 3 * 4 + 2 );
            if ( x > 1 && x <= QUARTER && x % 3 == 1 ) S.insert( ( x - 1 ) / 3 * 4 + 1 );
            if ( x <= EIGHTH ) S.insert( 8 * x );
         }
      }
      i += 3;
//    cout << i << '\t' << S.size() << '\t' << *S.begin() << '\n';        // Keep tabs on this for behaviour
      if ( !S.size() ) break;
   }

   if ( S.size() && *S.begin() < ALLOWED )
   {
      INT result = *S.begin();
      cout << "Sequence start: " << result << "    " << double( result ) << '\n';
      cout << "Check: length of sequence = " << Collatz( result ) << '\n';
   }
   else
   {
      cout << "Not found when holding smallest " << MAX_CANDIDATES << " at each step\n";
   }
}


What length of sequence do you want? 1200
Sequence start: 13529381324304041    1.35294e+16
Check: length of sequence = 1200


What length of sequence do you want? 1800
Maximum number of candidates to keep at each step? 150000
Sequence start: 627059094791614859    6.27059e+17
Check: length of sequence = 1800


Last edited on
seeplus (6597)
Using a std::vector for oldS rather than a std::set reduces the time take a little bit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
 
#include <iostream>
#include <limits>
#include <set>
#include <algorithm>
#include <chrono>
#include <vector>
using namespace std;

template<class TimeUnit = std::chrono::milliseconds>
class Timer {
public:
	Timer() {
		m_start = std::chrono::steady_clock::now();
	}

	~Timer() {
		std::chrono::steady_clock::time_point stop = std::chrono::steady_clock::now();
		std::cout << "\n** Running time: " << std::chrono::duration_cast<TimeUnit>(stop - m_start).count() << '\n';
	}

private:
	std::chrono::steady_clock::time_point m_start;
};

using INT = unsigned long long;
INT BIG = numeric_limits<INT>::max();
INT HALF = BIG / 2;
INT QUARTER = HALF / 2;   INT THREEQUARTERS = 3 * QUARTER;
INT EIGHTH = QUARTER / 2;
INT ALLOWED = 1'000'000'000'000'000'000;

//======================================================================

int Collatz(INT x) {
	int N = 1;
	for (; x != 1; N++) x = (x % 2 ? 3 * x + 1 : x / 2);
	return N;
}

//======================================================================

int main() {
	int L;
	cout << "What length of sequence do you want? ";   cin >> L;

	int MAX_CANDIDATES = 1000;       // (OK up to at least L=1300)
	if (L > 1300) {
		cout << "Maximum number of candidates to keep at each step? ";
		cin >> MAX_CANDIDATES;
	}

	set<INT> S = { 1 };

	{
		Timer t;

		int i = 2;
		while (i <= L) {
		   // Work from the smallest MAX_CANDIDATES elements
			//set<INT> oldS;

			std::vector<INT> oldS(S.begin(), S.end());

			if (oldS.size() > MAX_CANDIDATES)
				oldS.resize(MAX_CANDIDATES);

			/*
			auto it = S.begin();
			int num = 0;
			while (num < MAX_CANDIDATES and it != S.end()) {
				oldS.insert(*it);
				it++;
				num++;
			}
			*/

			S.clear();
			for (INT x : oldS) {
				if (i == L)           // last step
				{
					if (x > 4 && x % 6 == 4) S.insert((x - 1) / 3);
					if (x <= HALF) S.insert(2 * x);
				} else if (i == L - 1)  // last two steps
				{
					if (x > 4 && x % 6 == 4) S.insert(x - (x - 1) / 3 - 1);
					if (x > 2 && x <= HALF && x % 3 == 2) S.insert(x - (x - 2) / 3 - 1);
					if (x <= QUARTER) S.insert(4 * x);
				} else                    // three steps in one go
				{
					if (x > 7 && x % 18 == 16) S.insert((x - 7) / 9 * 2 + 1);
					if (x > 4 && x <= THREEQUARTERS && x % 6 == 4) S.insert((x - 1) / 3 * 4);
					if (x > 2 && x <= HALF && x % 3 == 2) S.insert((x - 2) / 3 * 4 + 2);
					if (x > 1 && x <= QUARTER && x % 3 == 1) S.insert((x - 1) / 3 * 4 + 1);
					if (x <= EIGHTH) S.insert(8 * x);
				}
			}
			i += 3;
	  //    cout << i << '\t' << S.size() << '\t' << *S.begin() << '\n';        // Keep tabs on this for behaviour
			if (!S.size()) break;
		}
	}

	if (S.size() && *S.begin() < ALLOWED) {
		INT result = *S.begin();
		cout << "Sequence start: " << result << "    " << double(result) << '\n';
		cout << "Check: length of sequence = " << Collatz(result) << '\n';
	} else {
		cout << "Not found when holding smallest " << MAX_CANDIDATES << " at each step\n";
	}
}


which for me for using set gives:


What length of sequence do you want? 1800
Maximum number of candidates to keep at each step? 150000

** Running time: 40207
Sequence start: 627059094791614859    6.27059e+17
Check: length of sequence = 1800


and using vector gives:


What length of sequence do you want? 1800
Maximum number of candidates to keep at each step? 150000

** Running time: 33964
Sequence start: 627059094791614859    6.27059e+17
Check: length of sequence = 1800


But this is for my laptop Intel I7 2.6GHZ processor. A faster processor would give faster timings - but it's still a away off the 10 secs given...
lastchance (6980)
Refactor with a straight set copy. The iteration through elements can be done from that.

It's very fast up to length L=1300, but you need to hold back more candidates at each stage after that, and I still need to optimise the number (possibly allowing it to vary with iteration as the minimum element gets closer to the largest allowed - see commented-out debug line).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
 
#include <iostream>
#include <limits>
#include <set>
#include <algorithm>
using namespace std;

using INT = unsigned long long;
INT BIG = numeric_limits<INT>::max();
INT HALF = BIG / 2;
INT QUARTER = HALF / 2;   INT THREEQUARTERS = 3 * QUARTER;
INT EIGHTH = QUARTER / 2;
INT ALLOWED = 1'000'000'000'000'000'000;

//======================================================================

int Collatz( INT x )
{
   int N = 1;
   for ( ; x != 1; N++ ) x = ( x % 2 ? 3 * x + 1 : x / 2 );
   return N;
}

//======================================================================

bool sequenceStart( int L, INT &result )
{
   int MAX_CANDIDATES = 1000;       // (OK up to at least L=1300)
   if ( L > 1300 )
   {
      cout << "Maximum number of candidates to keep at each step? ";
      cin >> MAX_CANDIDATES;
   }

   set<INT> S = { 1 };
   int i = 2;
   while ( i <= L )
   {
      // Work from the smallest MAX_CANDIDATES elements in (a copy of) the current set
      set<INT> oldS = S;
      S.clear();

      // Elements of the set at the next iteration
      auto it = oldS.begin();
      for ( int num = 0; num < MAX_CANDIDATES && it != oldS.end(); it++, num++ )
      {
         INT x = *it;

         if ( i == L )           // last step
         {
            if ( x > 4 && x % 6 == 4 ) S.insert( ( x - 1 ) / 3 );
            if ( x <= HALF ) S.insert( 2 * x );
         }
         else if ( i == L - 1 )  // last two steps
         {
            if ( x > 4 && x % 6 == 4 ) S.insert( x - ( x - 1 ) / 3 - 1 );
            if ( x > 2 && x <= HALF && x % 3 == 2 ) S.insert( x - ( x - 2 ) / 3 - 1 );
            if ( x <= QUARTER ) S.insert( 4 * x );
         }
         else                    // three steps in one go
         {
            if ( x > 7 && x % 18 == 16 ) S.insert( ( x - 7 ) / 9 * 2 + 1 );
            if ( x > 4 && x <= THREEQUARTERS && x % 6 == 4 ) S.insert( ( x - 1 ) / 3 * 4 );
            if ( x > 2 && x <= HALF && x % 3 == 2 ) S.insert( ( x - 2 ) / 3 * 4 + 2 );
            if ( x > 1 && x <= QUARTER && x % 3 == 1 ) S.insert( ( x - 1 ) / 3 * 4 + 1 );
            if ( x <= EIGHTH ) S.insert( 8 * x );
         }
      }
      i += 3;
//    cout << i << '\t' << S.size() << '\t' << *S.begin() << '\n';   // Keep tabs on this for behaviour
      if ( !S.size() ) break;
   }

   bool OK = S.size() && *S.begin() < ALLOWED;
   result = OK ? *S.begin() : 0;
   return OK;
}

//======================================================================

int main()
{
   int L;
   cout << "What length of sequence do you want? ";   cin >> L;

   INT result;
   if ( sequenceStart( L, result ) )
   {
      cout << "Sequence start: " << result << "   " << double( result ) << '\n';
      cout << "Check: length of sequence = " << Collatz( result ) << '\n';
   }
   else
   {
      cout << "Not found with given MAX_CANDIDATES\n";
   }
}


What length of sequence do you want? 1200
Sequence start: 13529381324304041    1.35294e+16
Check: length of sequence = 1200


What length of sequence do you want? 1500
Maximum number of candidates to keep at each step? 5000
Sequence start: 534146241844441967   5.34146e+17
Check: length of sequence = 1500


What length of sequence do you want? 1800
Maximum number of candidates to keep at each step? 150000
Sequence start: 627059094791614859    6.27059e+17
Check: length of sequence = 1800

Last edited on
seeplus (6597)
It's still faster to use a std::vector for oldS.

1
2
3
4
5
6
 
//set<INT> oldS = S;

std::vector<INT> oldS;

oldS.reserve(S.size());
oldS.assign(S.begin(), S.end());


For my laptop, the set version gives:


What length of sequence do you want? 1800
Maximum number of candidates to keep at each step? 150000

** Running time: 42033
Sequence start: 627059094791614859   6.27059e+17
Check: length of sequence = 1800


and with std::vector:


What length of sequence do you want? 1800
Maximum number of candidates to keep at each step? 150000

** Running time: 33763
Sequence start: 627059094791614859   6.27059e+17
Check: length of sequence = 1800


which is about a 20% speed improvement.
lastchance (6980)
Actually, you can use vectors for the lot, in conjunction with partial_sort.

Using -O3 optimisation this now runs in under 10 seconds for the length=1800 case, at least on my desktop PC.

I've put a trial-and-error expression for MAX_CANDIDATES in. You might still require user intervention to input the size of the collection carried forward at each iteration when L > 1300.

You can make it very slightly faster if you don't need to check the Collatz length, since intermediate values that you jump over could then stray outside the range of ULL. However, you'd then have to check the Collatz length with Python.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
 
#include <iostream>
#include <limits>
#include <vector>
#include <algorithm>
using namespace std;

using INT = unsigned long long;
INT BIG = numeric_limits<INT>::max();
INT HALF = BIG / 2;
INT QUARTER = HALF / 2;   INT THREEQUARTERS = 3 * QUARTER;
INT EIGHTH = QUARTER / 2;   INT THREEEIGHTHS = 3 * EIGHTH;
INT SIXTEENTH = EIGHTH / 2;
INT ALLOWED = 1'000'000'000'000'000'000;

//======================================================================

int Collatz( INT x )
{
   int N = 1;
   for ( ; x != 1; N++ ) x = ( x % 2 ? 3 * x + 1 : x / 2 );
   return N;
}

//======================================================================

bool sequenceStart( int L, INT &result )
{
   int STEPS = 3;

   int MAX_CANDIDATES = 1000;       // (OK up to at least L=1300)
   if ( L > 1300 )
   {
//    cout << "Maximum number of candidates to keep at each step? ";
//    cin >> MAX_CANDIDATES;
      double f = ( L - 1300.0 ) / 500.0;
      MAX_CANDIDATES = 1000 + 150000 * f * f;    // trial and error
   }

   vector<INT> V = { 1 }, oldV;
   int nsorted = 1;
   int i = 2;
   while ( i <= L )
   {
      // Work from the smallest MAX_CANDIDATES elements in (a copy of) the current set
      oldV = vector<INT>( V.begin(), V.begin() + nsorted );
      V.clear();

      // Elements of the collection at the next iteration
      for ( auto x : oldV )
      {
         if ( STEPS == 1 || i == L )                      // one step
         {
            if ( x % 6 == 4  &&  x > 4                       ) V.push_back( ( x - 1 ) / 3          );
            if (                          x <= HALF          ) V.push_back( 2 * x                  );
         }
         else if ( STEPS == 2 || i == L - 1 )             // two steps
         {
            if ( x % 6 == 4   && x > 4                       ) V.push_back( x - ( x - 1 ) / 3 - 1  );
            if ( x % 3 == 2   && x > 2 && x <= HALF          ) V.push_back( x - ( x - 2 ) / 3 - 1  );
            if (                          x <= QUARTER       ) V.push_back( 4 * x                  );
         }
         else if ( STEPS == 3 || i == L - 2 )             // three steps
         {
            if ( x % 18 == 16 && x > 7                       ) V.push_back( ( x - 7 ) / 9 * 2 + 1  );
            if ( x % 6  == 4  && x > 4 && x <= THREEQUARTERS ) V.push_back( ( x - 1 ) / 3 * 4      );
            if ( x % 3  == 2  && x > 2 && x <= HALF          ) V.push_back( ( x - 2 ) / 3 * 4 + 2  );
            if ( x % 3  == 1  && x > 1 && x <= QUARTER       ) V.push_back( ( x - 1 ) / 3 * 4 + 1  );
            if (                          x <= EIGHTH        ) V.push_back( 8 * x                  );
         }
         else                                             // four steps in one go
         {
            if ( x % 18 == 16                                ) V.push_back( ( x - 7 ) / 9 * 4 + 2  );
            if ( x % 18 == 4  && x > 4 && x <= THREEQUARTERS ) V.push_back( ( x - 13 ) / 9 * 4 + 5 );
            if ( x % 6  == 4  && x > 4 && x <= THREEEIGHTHS  ) V.push_back( ( x - 1 ) / 3 * 8      );
            if ( x % 9  == 8           && x <= HALF          ) V.push_back( ( x - 8 ) / 9 * 4 + 3  );
            if ( x % 3  == 2  && x > 2 && x <= THREEEIGHTHS  ) V.push_back( ( x - 2 ) / 3 * 8 + 4  );
            if ( x % 3  == 1  && x > 1 && x <= QUARTER       ) V.push_back( ( x - 1 ) / 3 * 8 + 2  );
            if ( x % 3  == 2           && x <= EIGHTH        ) V.push_back( ( x - 2 ) / 3 * 8 + 5  );
            if (                          x <= SIXTEENTH     ) V.push_back( 16 * x                 );
         }
      }
      i += STEPS;
      if ( V.empty() ) break;
      nsorted = MAX_CANDIDATES;   if ( V.size() < nsorted ) nsorted = V.size();
      partial_sort( V.begin(), V.begin() + nsorted, V.end() );
//    cout << i << '\t' << V.size() << '\t' << V[0] << '\n';   // Keep tabs on this for behaviour
   }

   bool OK = V.size() && V[0] < ALLOWED;
   result = OK ? V[0] : 0;
   return OK;
}

//======================================================================

int main()
{
   int L;
   cout << "What length of sequence do you want? ";   cin >> L;

   INT result;
   if ( sequenceStart( L, result ) )
   {
      cout << "Sequence start: " << result << "   " << double( result ) << '\n';
      cout << "Check: length of sequence = " << Collatz( result ) << '\n';
   }
   else
   {
      cout << "Not found with given MAX_CANDIDATES\n";
   }
}



What length of sequence do you want? 1200
Sequence start: 13529381324304041   1.35294e+16
Check: length of sequence = 1200



What length of sequence do you want? 1800
Sequence start: 627059094791614859   6.27059e+17
Check: length of sequence = 1800

Last edited on
Pages: 12