Let T be the transformation that sends an even integer x to x/2 and an odd integ

Question

Let T be the transformation that sends an even integer x to x/2 and an odd integer x to 3x 1. A famous conjecture, sometimes known as the 3x + 1 conjecture, states that for all positive integers x, when we repeatedly apply the transformation T, we will eventually reach the integer 1. Write an algorithm in pseudocode that checks whether the 3x+1 conjecture is true for a given integer input x. For your algorithm, what is the time complexity in terms of number of integers generated to test the conjecture for x = 89478485?

Explanation / Answer

ues as it is trivial once you understood above work

Int number;

//take input number from user

While(1)

{

If(number == 1)

Break;

//if number is even then divide it by 2;

If(number %2 ==0)

{

number= number/2;

}

Else

{

//if number is odd

Number = 3*number +1

}

}

//if program reaches here it indicate that number has become 1 and it testifies conjecture.

So by above algorithm number is odd

Number = 3*89478485 +1 = 268435456 .

Now number is even

Number = 268435456/2 = 134217728

Now number is even

Number = 134217728/2 = 67108864

Now number is even

Number = 67108864/2 = 33554432

Now number is even

Number = 33554432/2=16777216

Now number is even

Number = 16777216/2=8388608

Now number is even

Number = 8388608/2=4194304

Now number is even

Number = 4194304/2=2097152

Now number is even

Number = 2097152/2=1048576

Now number is even

Number = 1048576/2=524288

Now number is even

Number = 524288/2=262144

Now number is even

Number = 262144/2=131072

Now number is even

Number = 131072/2=65536

Now number is even

Number = 65536/2=32768

Now number is even

Number = 32768/2=16384

Now number is even

Number = 16384/2=8192

Now number is even

Number = 8192/2=4096

Now number is even

Number = 4096/2=2048

Now number is even

Number = 2048/2=1024

Now number is even

Number = 1024/2=512

Now number is even

Number = 512/2=256

Now number is even

Number = 256/2=128

Now number is even

Number = 128/2=64

Now number is even

Number = 64/2=32

Now number is even

Number = 32/2=16

Now number is even

Number = 16/2=8

Now number is even

Number = 8/2=4

Now number is even

Number = 4/2=2

Now number is even

Number = 2/2=1

So conjecture is true as number =1

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.