How to find the Nth number in a fractal sequence?

user_5956878 0
Viewed 514

The assignment is to write a C++ program which takes the input number n and outputs the nth number in the sequence:

1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6 ...

This is what I've come up with so far:

#include <iostream>
using namespace std;

int main()
{
    long long n,k=1,result;
    cin >> n;
    if(n==1){
        result=1;
    }else{
        for(int i=1,j=1;;i=j,j=j+k){
            if(n>i&&n<=j){
                result=n-i;
                break;
            }else{
                k++;
            }
        }
    }
    cout << result << endl;
}

This is also what I've written before:

#include <iostream>
using namespace std;

int main()
{
    long long n,count=0,result;
    cin >> n;
    for(int i=1;;i++){
        for(int j=1;j<=i;j++){
            count=count+1;
            if(count==n){
                result=j;
                break;
            }
        }
        if(count>=n){
            break;
        }
    }
    cout << result << endl;
}

Both of these work properly for smaller numbers, but the problem is I have to follow the constraint:

1 <= n <= 10^12

So when bigger numbers are inputted, the programs both take too long to output the solution and exceed the time limit, which is 2 seconds. I've been working on this for 5 hours now and I don't know how to improve these programs so they are faster. I also thought about a certain formula that could help determine the nth number in such a sequence, but I can't seem to find anything about it on the internet or in my math books. Could somebody point me to the solution? I would be very grateful.

sequence sequences c++
3 Answers

We can group numbers in your sequence:

(1) (1, 2) (1, 2, 3) ...

The overall amount of numbers is

1 + 2 + 3 + ...

The latter is an arithmetic progression, its sum equals to x*(x+1)/2.

We'll find the number of full groups k that go before n+1-th number in the sequence. k equals to the maximal integer such that k*(k+1)/2 <= n. To find it we'll solve the quadratic equation:

x*(x+1)/2 = n 
x^2 + x - 2*n = 0

Let's assume that positive root of this equation is x'. We round it down to the nearest integer k. If x' == k (x' is a whole number) it is the answer. Otherwise, the answer is n - k*(k+1)/2.

Exemplary c++ implementation:

double d = 1 + 8.0 * n;
double x = (-1 + sqrt(d)) / 2;

long long k = floor(x);
long long m = k*(k+1) / 2;
if (m == n) {
    return k;
} else {
    return n - m;
}

The solution has O(1) time complexity.

user_47592000

The first job is to write out the sequence like this:

1
2   3
4   5   6
7   8   9   10

And note that we want to map this to

1
1   2
1   2   3
1   2   3   4

The row position of a number is given by rearranging the formula for an arithmetic progression, solving the resultant quadratic, discarding the negative root, and removing any fractional part of the answer. A number t appears in the row r given by the whole number part

r = R(1/2 + (1/4 + 2 * (t - 1))1/2)

Where R() is a function that rounds a number downwards to the whole number.

But you are after the column c. That is obtained subtracting the value of the first term in that row from t:

c = t - 1/2 * r * (r - 1)

Reference: https://en.wikipedia.org/wiki/Arithmetic_progression

user_23808300

A solution using loop. It will out the number at nth.

x = 0 ;
i = 1 ;
do {
    x += i ;
    if( x == n ) {
        cout<< i ;
        break ;
    }
    else if( x > n ) {
        cout<< (n - (x-i)) ;
        break ;
    }
    i ++ ;
}while( 1) ;
user_81975600
Related