Win a copy of Cross-Platform Desktop Applications: Using Node, Electron, and NW.js this week in the JavaScript forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Calculating mystery number  RSS feed

 
khandoker Ismael
Greenhorn
Posts: 26
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

 
Paul Clapham
Sheriff
Posts: 22374
42
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Piet Souris
Rancher
Posts: 1943
66
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
khandoker Ismael
Greenhorn
Posts: 26
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Sergiu Dobozi
Ranch Hand
Posts: 107
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Sergiu Dobozi
Ranch Hand
Posts: 107
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:
 
Campbell Ritchie
Sheriff
Posts: 55350
157
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:

Better make the return type BigDecimal then.
 
Stephan van Hulst
Saloon Keeper
Posts: 7719
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
No. The problem is defined to have an integer solution.

[edit]

However, in that case the return type should be Optional<BigInteger>.
 
Campbell Ritchie
Sheriff
Posts: 55350
157
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There is no need for Optional either. It has an integer solution, and all terms and intermediate values will fit into a long.
 
Jeremy Lautman
Greenhorn
Posts: 4
AngularJS Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:No. The problem is defined to have an integer solution.

[edit]

However, in that case the return type should be Optional<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.
 
Jeremy Lautman
Greenhorn
Posts: 4
AngularJS Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 be Optional<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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I used 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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jeremy Lautman wrote:. . . My first time posting! . . . .
Welcome to the Ranch

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 shou‍ld have a name.
 
Jeremy Lautman
Greenhorn
Posts: 4
AngularJS Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 shou‍ld 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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
. . . and after another 46 iterations you get 2⁵⁰ + 1. So it is simple to go up and it sh‍ould 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.
 
Ryan McGuire
Ranch Hand
Posts: 1138
8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:. . . and after another 46 iterations you get 2⁵⁰ + 1. So it is simple to go up and it sh‍ould 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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.




 
Piet Souris
Rancher
Posts: 1943
66
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Paul Clapham
Sheriff
Posts: 22374
42
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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!!!


 
Campbell Ritchie
Sheriff
Posts: 55350
157
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ryan McGuire wrote:. . . . the "Ritchie Conjecture" maybe?
hahahahahahahahahahahahahahahaha!
 
Knute Snortum
Sheriff
Posts: 3942
92
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Piet Souris
Rancher
Posts: 1943
66
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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!
 
khandoker Ismael
Greenhorn
Posts: 26
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you for your valuable suggestions.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!