Reducing the time to calculate collatz sequence

Competitive Programming
1

How to reduce run time for calculating collatz sequence for larger input greater than 1000000?

2

For the benefit of anyone who doesn’t know what is a collatz sequence:

The collatz conjecture is an open (unsolved) problem in mathematics that states that for:

  • If N is Odd then change N to 3*N + 1 .
  • If N is Even then change N to N / 2 .

Until N reaches 1.

when N = 13 :
13 → 40 → 20 → 10 → 5 > 16 → 8 → 4 → 2 → 1

3

You can write a straightforward iterative program to calculate collatz sequence for any given number. Time will not be an issue since collatz sequences collapse very quickly even for very large numbers, for example for all n <= 10^17 length of longest collatz sequence is 2091 for n = 93571393692802302, i.e even for such huge values of n your loop would not exceed 2000 iterations.

ref https://en.wikipedia.org/wiki/Collatz_conjecture

4

May use long long int if using cpp

5

Calculating collatz sequence for a given number is running within time limit,
But calculating largest collatz sequence within a number is exceeding time limit.
IMG20200318121251

6

IMG20200318121251

7

We can’t guess what’s wrong,
post the code and the question link

8

mine solution

#include
#include
using namespace std;
int main()
{
int t;
scanf("%d", &t);
while(t–)
{
int a, j, p, move;
scanf("%d", &a);
p = a, move=1;
while(p!=1)
{
if(p%2 == 0)
{
p= p/2;
}
else
{
p = p*3 + 1;
move++;
}
}

    printf("%d\n", move);
}

}

9

https://projecteuler.net/problem=14

#include
#include
using namespace std;
int main()
{
int a, b, i, j, great=0, p, move, ans;
for(i=1000000; i>=1; i–)
{
p = i, move=1;
while(p!=1)
{
if(p%2 == 0)
{
p= p/2;
move++;
}
else
{
p = p*3 + 1;
move++;
}
}
if(move>great)
{
great = move;
}
}
printf("%d\n", great);
}

10

first of all is it c or c++?
secondly it is full of errors, please post a formatted version of error free code to debug

11

I wrote using namespace std after that you can use scanf and printf in place of cin cout, and it is compiling moreover code was accepted partially by hackerrank

12

Bro check your code at very 1st line Pls, #include what?

13

iostream vector
Idk but angular bracket is not visible

14
1 Like
15

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
int t;
cin >> t;
while(t–) {
ll n;
cin >> n;
ll count=0,even=0;
while(n != 1) {
if( n % 2 == 0) {
count++;
even++;
n /= 2;
} else {
count++;
n = (3*n) + 1;
}
}
count++;
cout << count - even << endl;
}
}

1 Like