Question

In: Computer Science

The Golomb's sequence is G(n) = 1 + G(n - G(G(n - 1))) For what n...

The Golomb's sequence is G(n) = 1 + G(n - G(G(n - 1)))

For what n value (approximately) does your computer stop producing output? Why is this?

The following is my code, but I don't know what would be the max value for n, since my computer stuck at 80

#include <iostream>

using namespace std;

int golombSequence(int);

int golombSequence(int max){

if(max == 1){

return 1;

}

else{

return 1 + golombSequence(max - golombSequence(golombSequence(max-1)));

}

int main(int argc, const char * argv[]) {

// int n = 90;

// for(int i = 1; i<=n; i++){

// cout<<i<<": "<<golombSequence(i)<<endl;

// }

// return 0;

}

Expert Solution

C++ Program:

In my computer, the program stuck at 69. The sole reason for the stacking of this program is the processing speed of the computer. It might be that you are having a better configured desktop/laptop than mine which is the reason why your program went upto 80.
The function Golomb sequence in the program has many recursions due to which the processing power required by the code to execute is far more than any other normal program which is why the program is stuck after the number of time running the program.
As we all know the recursion programs can have recursive loop as can be seen in the above program and if each of the loop is required with more resources and not fulfilling the requirement of the resources after executing the program could probably result in crashing the system.
It totally depends on the system that how much can it can bear the memory-intensive program without crashing the system completely and how much time will it take for the program to completely hung up the system or to occupy all the available resources.

Output:

Hence, this is the reason why the program is hunging up your system and the maximum will depend on the systems capacity and the input of the program.

venereology answered 8 months ago

Let sn be a Cauchy sequence such that ∀n > 1, n ∈ N, ∃m >...

Let sn be a Cauchy sequence such that ∀n > 1, n ∈ N, ∃m > 1, m ∈ N such that |sn − m| = 1/3 (this says that every term of the sequence is an integer plus or minus 1/3 ). Show that the sequence sn is eventually constant, i.e. after a point all terms of the sequence are the same

3. The Hofstadter Conway sequence is defined by a(1)=a(2)=1 and (for n>2 by) a(n)=a(a(n-1))+a(n-a(n-1)). Write a...

3. The Hofstadter Conway sequence is defined by a(1)=a(2)=1 and (for n>2 by) a(n)=a(a(n-1))+a(n-a(n-1)). Write a function to quickly compute this sequence. >>> [hc(i) for i in range(1,20)] [1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11]

Given the sequence {an}∞ n=1 where an = 3ne−6n A) Justify whether the sequence is increasing...

Given the sequence {an}∞ n=1 where an = 3ne−6n A) Justify whether the sequence is increasing or decreasing. B) Is the sequence bounded? If yes, what are the bounds? C) Determine whether the sequence converges or diverges. State any reason (i.e result, theorems) for your conclusion.

Fibonacci Sequence: F(0) = 1, F(1) = 2, F(n) = F(n − 1) + F(n −...

Fibonacci Sequence: F(0) = 1, F(1) = 2, F(n) = F(n − 1) + F(n − 2) for n ≥ 2 (a) Use strong induction to show that F(n) ≤ 2^n for all n ≥ 0. (b) The answer for (a) shows that F(n) is O(2^n). If we could also show that F(n) is Ω(2^n), that would mean that F(n) is Θ(2^n), and our order of growth would be F(n). This doesn’t turn out to be the case because F(n)...

A sequence {an} is given by: an = n2 - 1, n € N. Show that it is not an arithmetic progression (A.P)?

2. The Fibonacci sequence is defined as f(n) = f(n - 1) + f(n - 2)...

2. The Fibonacci sequence is defined as f(n) = f(n - 1) + f(n - 2) with f(0) = 0 and f(1) = 1. Find f(54) by a program or maually. Note that this number must be positive and f(53) = 53.......73 (starting with 53 and ending with 73). I must admit that my three machines including a desktop are unable to find f(54) and they quit during computation. The answer is f(54) = 86267571272 */ The Java code: public...

1.)Prove that f(n) = O(g(n)), given: F(n) = 2n + 10; g(n) = n 2.)Show that...

1.)Prove that f(n) = O(g(n)), given: F(n) = 2n + 10; g(n) = n 2.)Show that 5n2 – 15n + 100 is Θ(n2 ) 3.)Is 5n2 O(n)?

def seq3np1(n): """ Print the 3n+1 sequence from n, terminating when it reaches 1. args: n...

def seq3np1(n): """ Print the 3n+1 sequence from n, terminating when it reaches 1. args: n (int) starting value for 3n+1 sequence return: None """ while(n != 1): print(n) if(n % 2) == 0: # n is even n = n // 2 else: # n is odd n = n * 3 + 1 print(n) # the last print is 1 def main(): seq3np1(3) main() Using the provided code, alter the function as follows: First, delete the print statements...

For any sequence, S[1…n], of length n, a basement is defined as a contiguous subsequence of...

For any sequence, S[1…n], of length n, a basement is defined as a contiguous subsequence of S, which we denote by S[ i, i + 1, ..., j – 1, j ], with 1 £ i < i + 1 < j – 1 < j £ n, satisfying the following conditions: S[ i ] > S[ i + 1] S[ j – 1] < S[ j ] 1 £ i < i + 1 < j – 1 <...

Let a sequence {xn} from n=1 to infinity satisfy x_(n+2)=sqrt(x_(n+1) *xn) for n=1,2 ...... 1. Prove...

Let a sequence {xn} from n=1 to infinity satisfy x_(n+2)=sqrt(x_(n+1) *xn) for n=1,2 ...... 1. Prove that a<=xn<=b for all n>=1 2. Show |x_(n+1) - xn| <= sqrt(b)/(sqrt(a)+sqrt(b)) * |xn - x_(n-1)| for n=2,3,..... 3. Prove {xn} is a cauchy sequence and hence is convergent Please show full working for 1,2 and 3.