khandoker Ismael

Greenhorn

Posts: 26

1

posted 1 month ago

Given a number . You multiply this number by 2 and you subtract 1

to the result. You then multiply the new result by 2 and subtract 1. And you keep doing this until

you have done it 48 times. When you are done, the result you obtain is: 2^50 +1.

What is the mystery number?

This code is giving me the result. But I think this not correct result. because I calculated by hand it was different. any mistake I am doing?

Can anybody help me regarding this? I had another question that how I can show an exponential term in my output?

thanks in advance.

to the result. You then multiply the new result by 2 and subtract 1. And you keep doing this until

you have done it 48 times. When you are done, the result you obtain is: 2^50 +1.

What is the mystery number?

This code is giving me the result. But I think this not correct result. because I calculated by hand it was different. any mistake I am doing?

Can anybody help me regarding this? I had another question that how I can show an exponential term in my output?

thanks in advance.

posted 1 month ago

There's several problems there.

The biggest problem is, the calculation you're doing is the wrong calculation and it won't give you the answer to your question.

It's also possible that your by-hand calculation is the wrong calculation too.

The other problem is, you're using double values which may or may not give you the correct answer if you use the correct calculation. It's probable that round-off errors will lead you to the wrong answer. I'd suggest that you use BigInteger values instead -- the values you'll use throughout your calculation are all integers anyway, so using BigInteger makes the round-off problem go away.

And if you get the right answer, you don't need to show an "exponential" value because the right answer doesn't require that.

The biggest problem is, the calculation you're doing is the wrong calculation and it won't give you the answer to your question.

It's also possible that your by-hand calculation is the wrong calculation too.

The other problem is, you're using double values which may or may not give you the correct answer if you use the correct calculation. It's probable that round-off errors will lead you to the wrong answer. I'd suggest that you use BigInteger values instead -- the values you'll use throughout your calculation are all integers anyway, so using BigInteger makes the round-off problem go away.

And if you get the right answer, you don't need to show an "exponential" value because the right answer doesn't require that.

Piet Souris

Rancher

Posts: 1943

66

posted 1 month ago

apart from Pauls relevant remarks: have you tried to solve it mathematically first?

For instance, if a is the number to be found, then after step 1 we have 2a - 1. Step 2 gives us 2(2a - 1) - 1 = 4a - 3. Step 3 gives us 2(4a - 3) - 1 = 8a - 7. Step 4 gives us 2(8a - 7) - 1 = 16 a - 15. Can you find a pattern in this development? Can you prove this pattern (for instance with mathematical induction)? What do we get after step 48?

For instance, if a is the number to be found, then after step 1 we have 2a - 1. Step 2 gives us 2(2a - 1) - 1 = 4a - 3. Step 3 gives us 2(4a - 3) - 1 = 8a - 7. Step 4 gives us 2(8a - 7) - 1 = 16 a - 15. Can you find a pattern in this development? Can you prove this pattern (for instance with mathematical induction)? What do we get after step 48?

khandoker Ismael

Greenhorn

Posts: 26

1

posted 1 month ago

Thank you Paul and Piet for your help. Now I again did the calculation for this problem by hand.

I got the pattern and applied geometric series formula a*r^n-1 . And by doing this I got the 48th term

which is a*2^48-2^48+1. From this

I determined a: (2^50+2^48)/2^48 =5

a=5. Is this correct way. So now if this is correct how I will write in java ? just this equation for determining value of a I need to write in program?

thanks for your time.

I got the pattern and applied geometric series formula a*r^n-1 . And by doing this I got the 48th term

which is a*2^48-2^48+1. From this

I determined a: (2^50+2^48)/2^48 =5

a=5. Is this correct way. So now if this is correct how I will write in java ? just this equation for determining value of a I need to write in program?

thanks for your time.

posted 1 month ago

I am sorry, but if "You multiply this number by 2 and you subtract 1 to the result. You then multiply the new result by 2 and subtract 1. And you keep doing this until you have done it 48 times." you will never get to 2^50+1....you need to multiply and substract 50 times.

Maybe you have to solve the following equation? a * (your pattern) = 2^50+1?

The pattern you discovered is almost correct. Piet gave you a great hint on how to find it out, just pay attention to the small details.

khandoker Ismael wrote:Thank you Paul and Piet for your help. Now I again did the calculation for this problem by hand.

I got the pattern and applied geometric series formula a*r^n-1 . And by doing this I got the 48th term

which is a*2^48-2^48+1. From this

I determined a: (2^50+2^48)/2^48 =5

a=5. Is this correct way. So now if this is correct how I will write in java ? just this equation for determining value of a I need to write in program?

thanks for your time.

I am sorry, but if "You multiply this number by 2 and you subtract 1 to the result. You then multiply the new result by 2 and subtract 1. And you keep doing this until you have done it 48 times." you will never get to 2^50+1....you need to multiply and substract 50 times.

Maybe you have to solve the following equation? a * (your pattern) = 2^50+1?

The pattern you discovered is almost correct. Piet gave you a great hint on how to find it out, just pay attention to the small details.

posted 1 month ago

Ah sorry, now I realize that you need to find out n in your case. So basically your pattern starts with n (from number). You don't need an "a" anywhere. Solve the pattern based on n, then balance it with 2^50+1 and you will easily find out n.

Sergiu Dobozi wrote:

I am sorry, but if "You multiply this number by 2 and you subtract 1 to the result. You then multiply the new result by 2 and subtract 1. And you keep doing this until you have done it 48 times." you will never get to 2^50+1....you need to multiply and substract 50 times.

Maybe you have to solve the following equation? a * (your pattern) = 2^50+1?

The pattern you discovered is almost correct. Piet gave you a great hint on how to find it out, just pay attention to the small details.

Ah sorry, now I realize that you need to find out n in your case. So basically your pattern starts with n (from number). You don't need an "a" anywhere. Solve the pattern based on n, then balance it with 2^50+1 and you will easily find out n.

Stephan van Hulst

Saloon Keeper

Posts: 7719

142

posted 1 month ago

Yes, after analysis on paper, there is not much more left to the problem that simply having a function that returns 5.

However, it's probably a better exercise to solve the problem when n and the nth term are variables instead of constants:

However, it's probably a better exercise to solve the problem when n and the nth term are variables instead of constants:

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

Campbell Ritchie

Sheriff

Posts: 55350

157

posted 1 month ago

It is actually, as you say, easy to find the original number starting from 2⁵⁰ + 1, by reversing the steps in the original formula. Don't try going forwards until you get the required result. Least of all if you think the answer about the starting point is 5.

I don't think a big integer is required because 2⁵⁰ + 1 is well within the range of a

OP: I suggest you start by finding out how to print 2⁵⁰ + 1 to screen. Don't use a loop; use one of the less commonly used operators.

Addition: Remind yourself of the whole gamut of operators in the Java™ Tutorials.

I don't think a big integer is required because 2⁵⁰ + 1 is well within the range of a

`long`.OP: I suggest you start by finding out how to print 2⁵⁰ + 1 to screen. Don't use a loop; use one of the less commonly used operators.

Addition: Remind yourself of the whole gamut of operators in the Java™ Tutorials.

Piet Souris

Rancher

Posts: 1943

66

Stephan van Hulst

Saloon Keeper

Posts: 7719

142

posted 1 month ago

No. The problem is defined to have an integer solution.

[edit]

However, in that case the return type should be

[edit]

However, in that case the return type should be

`Optional<BigInteger>`.
Campbell Ritchie

Sheriff

Posts: 55350

157

posted 1 month ago

My first time posting!

The original problem was defined to have an integer solution, but the generic problem that Piet suggested which takes arbitrary n and y (probably) does not have integer solutions for all values of n and y.

Stephan van Hulst wrote:No. The problem is defined to have an integer solution.

[edit]

However, in that case the return type should beOptional<BigInteger>.

My first time posting!

The original problem was defined to have an integer solution, but the generic problem that Piet suggested which takes arbitrary n and y (probably) does not have integer solutions for all values of n and y.

posted 1 month ago

Sorry. That Stephan originally suggested. Piet suggested a slight modification to the generic problem.

Jeremy Lautman wrote:Stephan van Hulst wrote:No. The problem is defined to have an integer solution.

[edit]

However, in that case the return type should beOptional<BigInteger>.

My first time posting!

The original problem was defined to have an integer solution, but the generic problem that Piet suggested which takes arbitrary n and y (probably) does not have integer solutions for all values of n and y.

Sorry. That Stephan originally suggested. Piet suggested a slight modification to the generic problem.

Stephan van Hulst

Saloon Keeper

Posts: 7719

142

posted 1 month ago

I used

Welcome to CodeRanch Jeremy!

`BigInteger`, because you could solve the equation for`y >> 2^50+1`, and`Optional`because there may not be an integer solution. Yes, we could use`BigDecimal`instead, but I like to keep the problem in the domain of the natural numbers.Welcome to CodeRanch Jeremy!

Campbell Ritchie

Sheriff

Posts: 55350

157

posted 1 month ago

This problem resembles the kinds of problems I used to see on math olympiads in high school. They give problems which are impractical to brute force by hand in the time available, but rely on identifying patterns.

To me, it looks like a twist on the powers of 2 series. 5 = 2^2 + 1, and the next term after applying the rule is 2^3 + 1. As such, I doubt it has its own name.

Campbell Ritchie wrote:

The problem in its current form does have a simple solution with an integer answer.

By the way: is there a name for such a series? It looks like something which should have a name.

This problem resembles the kinds of problems I used to see on math olympiads in high school. They give problems which are impractical to brute force by hand in the time available, but rely on identifying patterns.

To me, it looks like a twist on the powers of 2 series. 5 = 2^2 + 1, and the next term after applying the rule is 2^3 + 1. As such, I doubt it has its own name.

Campbell Ritchie

Sheriff

Posts: 55350

157

Ryan McGuire

Ranch Hand

Posts: 1138

8

posted 1 month ago

I could have sworn I've heard of that before... the "Ritchie Conjecture" maybe?

Campbell Ritchie wrote:. . . and after another 46 iterations you get 2⁵⁰ + 1. So it is simple to go up and it should be just as simple to come back.

There must be a name for it; every mathematician in history has tried to apply their name to something.

I could have sworn I've heard of that before... the "Ritchie Conjecture" maybe?

khandoker Ismael

Greenhorn

Posts: 26

1

posted 1 month ago

Thank you everyone for your help and nice discussion about this problem. I tried to use BigInteger in my case now and I am getting error in my following method.

Can anybody tell me am I doing right or what is error actual. Sorry I am a beginner that's why asking these.

Thanks in advance.

Can anybody tell me am I doing right or what is error actual. Sorry I am a beginner that's why asking these.

Thanks in advance.

Piet Souris

Rancher

Posts: 1943

66

posted 1 month ago

There are a couple of problems.

Math.pow takes two parameters of type double. So, Math.pow(2, n) will not work, since n is a BigInteger.

A BigInteger cannot be created by adding two doubles and dividing the sum by another double (Math.pow returns a double).

So, you need to do some reading in the API of Math and BigInteger!

Meanwhile:

1) lets define 2^N as BigInteger. First, we create a BigInteger(2). According to the API a simple way to do so is: BigInteger two = new BigInteger("2").

2) Now, look in the API if there is a handy method that will give us directly a BigInteger with the value of 2^N.

3) Being able to create any BigInteger of the form 2^N, now look in the API how to sum two BigIntegers.

4) Lastly, we must divide that sum by another BigInteger (your formula is correct). You will see a method called 'divideAndRemainder(BigInteger val)'. That method returns an array of two BigIntegers, with the second BigInteger being the remainder of the division. If that one is not BigInteger ZERO, then the result is not an integer.

Here you can find the api of java, search for BigInteger: API

Math.pow takes two parameters of type double. So, Math.pow(2, n) will not work, since n is a BigInteger.

A BigInteger cannot be created by adding two doubles and dividing the sum by another double (Math.pow returns a double).

So, you need to do some reading in the API of Math and BigInteger!

Meanwhile:

1) lets define 2^N as BigInteger. First, we create a BigInteger(2). According to the API a simple way to do so is: BigInteger two = new BigInteger("2").

2) Now, look in the API if there is a handy method that will give us directly a BigInteger with the value of 2^N.

3) Being able to create any BigInteger of the form 2^N, now look in the API how to sum two BigIntegers.

4) Lastly, we must divide that sum by another BigInteger (your formula is correct). You will see a method called 'divideAndRemainder(BigInteger val)'. That method returns an array of two BigIntegers, with the second BigInteger being the remainder of the division. If that one is not BigInteger ZERO, then the result is not an integer.

Here you can find the api of java, search for BigInteger: API

posted 1 month ago

Just as in biology where it's bad taste to name a species after yourself, it's bad taste in mathematics to name a sequence (or theorem, or rule, or conjecture, or whatever) after yourself. Fermat's Last Theorem wasn't given that name by Fermat, for example.

Campbell Ritchie wrote:There must be a name for it; every mathematician in history has tried to apply their name to something.

Just as in biology where it's bad taste to name a species after yourself, it's bad taste in mathematics to name a sequence (or theorem, or rule, or conjecture, or whatever) after yourself. Fermat's Last Theorem wasn't given that name by Fermat, for example.

khandoker Ismael

Greenhorn

Posts: 26

1

posted 1 month ago

Thank you very much Piet and others.

I think I got this BigInteger and it's giving me result 5 for n=48 which is correct according to my calculation.

Any suggestion will be appreciated.

thanks again all!!!

I think I got this BigInteger and it's giving me result 5 for n=48 which is correct according to my calculation.

Any suggestion will be appreciated.

thanks again all!!!

Campbell Ritchie

Sheriff

Posts: 55350

157

posted 1 month ago

Most of my changes to your code are minor. The ones with the most impact are reducing intermediate variables. My rule of thumb is that if you can eliminate an intermediate variable and still be clear, then do. "Still be clear" is a judgement call, though.

All things are lawful, but not all things are profitable.

Piet Souris

Rancher

Posts: 1943

66

posted 1 month ago

Knutes suggestion has the disadvantage that during development and test phase there is not much to inspect, since the whole calcultation is returned in one go. But when finished debugging, it makes the code indeed more easy to follow.

The problem that I have is: we all have read this thread, and we know what you are doing in the 'computeEquation' method. But when you look at that method in, say, three months time, would you still have a notion of what it is that you are calculating?

So I would add the comment: this method solves the equation in a: 2^n * (a-1) + 1 = 2^50 + 1.

and, if you like, the descrption from where this equation is coming.

And lastly: you can simplify the calculation with:

That makes it immediately clear what will happen when n > 50: the exponent becomes negative. What happens then? Try it out!

But all in all: great job, have a cow!

The problem that I have is: we all have read this thread, and we know what you are doing in the 'computeEquation' method. But when you look at that method in, say, three months time, would you still have a notion of what it is that you are calculating?

So I would add the comment: this method solves the equation in a: 2^n * (a-1) + 1 = 2^50 + 1.

and, if you like, the descrption from where this equation is coming.

And lastly: you can simplify the calculation with:

That makes it immediately clear what will happen when n > 50: the exponent becomes negative. What happens then? Try it out!

But all in all: great job, have a cow!