|
Problem in question:
You may solve this problem with or without programming, but it has been optimised for solution with a programming method.
The Fibonacci sequence of numbers is defined as:
F[0]=0<br />
F[1]=1<br />
and for all x>1,<br />
F[x]=F[x-1]+F[x-2]
PLEASE do not post the answer.
What is the smallest value of x>0 such that F[x]=0 mod 2^32
PLEASE do not post the answer.
I never thought I'd revert to posting here to get help with this question from a Puzzel Challange Site[^]. The history behind it, I've been stuck on this for a year. Not a solid year but off and on. I've written a LongMath Class[^] to help me solve it but I still haven't found the the answer. I've read through the posts on the challange site and they're talk'n about, "If you understand the Fibonacci sequence you won't need a program to figure it out.
I'm looking for help in solving the problem on my own. The site is older and not alot of visitors to the forums. I've applied my LonMath Class to a sandbox app to help solve it but I'm not sure if I'm performing F[x]=0 mod 2^32 correctly. Fibonacci Pilot[^]
I'm listening but I only speak GEEK.
|
|
|
|
|
I'm intrigued, but I'm not about to log on to that site, is that the full text of the puzzle?
I ask because it seems to me that 0 mod 2^32 equals 0; so, as stated, the puzzle has no solution.
|
|
|
|
|
Nono, in real life as well as in maths, numbers have no upper bound and no limit as
to the number of bits; so there might well be non-zero Fibonnacci numbers
that take a divisor of 2^32. In fact, I can assure you there are infinitely many
solutions to this one, and the smallest of them can be calculated with a simple calculator !
The puzzle site is very challenging, and yes, most often the problem descriptions are
short, and sometimes very ... puzzling.
Luc Pattyn
|
|
|
|
|
Yes, but as stated, we're not dividing (or MODing) the xth Fibonnacci number by 2^32, but comparing it with 0 mod 2^32 which ought to be 0; isn't 0 mod anything (except 0) always 0? So the mod 2^32 is unnecessary.
That simplifies the puzzle to F[x]=0, but that's only true when x=0, and the puzzle is to find a solution where x>0, that's why I see no solution.
Certainly, if the puzzle stated F[x] mod 2^32 = 0, then I would understand it.
|
|
|
|
|
mathematician use a lot of different notations for modulo arithmetic.
All of the following are equivalent:
a ≡ b (mod M)
a = b (mod M)
a ≡ b mod M
a = b mod M
and they all actually mean:
a % M = b % M
so the modulo operator is often mentioned only once,
and sometimes not at all (but just implied by text or context)
Therefore the problem at hand is really asking for the first Fibonacci number
that is a multiple of 2^32.
Of course, a more programmer-friendly notation would have been:
find x such that F(x) mod 2^32 = 0
instead of: F(x) = 0 mod 2^32
Luc Pattyn
|
|
|
|
|
Aside:
Well, if a = b mod M means a % M = b % M how would I express a = b % M ?
|
|
|
|
|
Program statements must be accurate and unambiguous; thats what compilers need,
and programmers must provide.
Mathematical equations must also be accurate and unambiguous. However math publications
try to come up with the clearest and/or shortest notation, often at the expence of
some ambiguity (which then should be resolved by adding a textual description of the
local conventions, if necessary).
It is important to recognize which is which. On most of the CP message boards, there
is no doubt, it is code in one of the many standard programming languages.
On the Maths and Algos board, some of it is math equations, and must be treated as such.
Luc Pattyn
|
|
|
|
|
Luc Pattyn wrote: find x such that F(x) mod 2^32 = 0
Your correct that the author mentions that the above equation is another way to look at it. Thank you for the help in this puzzle. I've been reviewing the series for a pattern of numbers that follow a power of 2, but I'm not much of a mathematician.
I'm listening but I only speak GEEK.
|
|
|
|
|
That would be why I asked if you could post the full actual text of the puzzle.
|
|
|
|
|
Hi,
there are several bulletin boards on the caesum site, there is one per level,
and one per problem (only accessible once you solved it!).
The fibber problem can be cracked easily by programming; there are tsraightforward
ways, and even better ones.
It can also be solved by hand using a simple calculator (hint: scan the Fibonacci
sequence looking for a pattern in the powers of 2).
Luc Pattyn
|
|
|
|
|
I've been running the squence and squaring each number looking for an noticable pattern but I'm not seeing anything. Most of the puzzles I've run into have an underlying reson for the puzzle. Would you know where else this information would be used? Why would I be looking at a pattern of squared numbers?
I'm listening but I only speak GEEK.
|
|
|
|
|
Squaring ?? 
Just look at the Fib numbers in binary...
Luc Pattyn
|
|
|
|
|
sorry just miss typed, was meaning, (power of 2) not squared.
I'm listening but I only speak GEEK.
|
|
|
|
|
|
will you help me about 3d modelling application devlopment,i have requirment to devlop 3d modelling applicationj just like any presentation software.
Hi manish Here.
|
|
|
|
|
You can have look at openGL section on this site.
|
|
|
|
|
Well, i know it's not a part of this site and i don't want to advertise (i really don't have to gain anything) but i'm using TrueVision3D, a DX wrapper (free for demo, 160$ for a single license, no royalties). It's quite fast and extremelly easy to use in vb6, c++, c# and .NET. It's current version is 6.2 but with a license you can get the beta 6.5 which is amazing. Anyway, it has all you'll ever need for creating a 3D modelling software.
PS: To avoid sounding biased, there are also many other engines out there like Torque, Ogre, .. etc but as far as i know they're oriented towards C++. Don't know for sure though. Also you could go for OGL or DX if you can spare the time learning.
|
|
|
|
|
I think Torque can now release code that runs on the XBox 360. That's pretty cool.
the last thing I want to see is some pasty-faced geek with skin so pale that it's almost translucent trying to bump parts with a partner - John Simmons / outlaw programmer
Deja View - the feeling that you've seen this post before.
|
|
|
|
|
ms raj wrote: will you help me about 3d modelling application devlopment,
a bit late to reply, but you can always try: http://www.openscenegraph.org/[^]
_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
|
|
|
|
|
Click here.[^]
"Marge, don't discourage the boy! Weasling out of things is important to learn. It's what separates us from the animals! Except the weasel." - Homer Simpson
Web - Blog - RSS - Math - LinkedIn - BM
|
|
|
|
|
amount is too small
Luc Pattyn
|
|
|
|
|
Indeed. I wonder if it wasn't, would the person who cashed it have been able to do so?  Imagine the fun mathematicians could have. 
"Marge, don't discourage the boy! Weasling out of things is important to learn. It's what separates us from the animals! Except the weasel." - Homer Simpson
Web - Blog - RSS - Math - LinkedIn - BM
|
|
|
|
|
People that handle economic issues is just too limited to imagine the possibilities. Just take the case of negative amounts. If you could issue a check with a negative amount, it would elliminate the need of invoices. Paying your rent would just be a matter of casching a negative check. 
---
It's amazing to see how much work some people will go through just to avoid a little bit of work.
|
|
|
|
|
Guffa wrote: Paying your rent would just be a matter of casching a negative check.
And how many people would cash it? 
"Marge, don't discourage the boy! Weasling out of things is important to learn. It's what separates us from the animals! Except the weasel." - Homer Simpson
Web - Blog - RSS - Math - LinkedIn - BM
|
|
|
|
|
It is not too small. The whole thing came up because apparently Verizon doesn't know the difference between cents and dollars; some guy was inquiring about data transfer rates while he was in Canada, and multiple times they quoted his rate as "0.002 cents/KB" when they meant "$0.002/KB", and consequently his bill was 100 times larger than he expected. He has chronicled the story on his blog: http://verizonmath.blogspot.com/[^].
--
Marcus Kwok
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
