My Math Forum Need help creating formula for:Fn-1 + Fn-2 + ... + Fn-k

 Number Theory Number Theory Math Forum

 May 26th, 2010, 07:04 PM #1 Newbie   Joined: May 2010 Posts: 6 Thanks: 0 Need help creating formula for:Fn-1 + Fn-2 + ... + Fn-k I am a novice computer programmer, and I am looking to write a simple data compression program. It seems that one could use a recurrence relation sequence or Closed-form expression thereof - to compress any file down to a few bytes. See files on a computer could be looked at as one really big(astronomical number). A small formula, only a few bytes wide, could ideally represent any abitrary sized file(e.g. 1, 2, 50 gigs+, etc), and when one needed to decompress - the zip program would merely caclulate the formula, and the end result would be a really big binary number. The binary would be your file. Fibonacci numbers do not include every number - which, of course, is a very good thing. So I was thinking that I could use a formula similar to "Binet's formula". . So I need a similar Closed-form expression that would calculate: Fn-1 + Fn-2 + ... + Fn-k k being any arbitrary number > 2. [color=#FF0000]My requests[/color]: [color=#FF0000]=================================================[/color] (1) Would anyone be so kind as to write me a closed-form expression for the recurrence relation sequence: Fn-1 + Fn-2 + ... + Fn-k --------------------------------------------------------- (2) If no one is willing to write me a formula, then could someone at least talk me through writing it myself. Perhaps you could talk me through the motives and puposes behind the different parts of Binet's formula - that would help alot(e.g. Why use the sqrt of 5 in "phi" as opposed to another sqrt anyways). I am not well versed in mathematics, but if you explain things in graphical and simple terms I will eventually figure out what your writing. [color=#FF0000]=================================================[/color] i am all to willing to do this myself except I do not yet have the necessary math expertise to do so. I also, unfortunately, have had a very dibilitating mental disorder for a number of years now and it has put my entire life on ice, I am currently taking medication, and when I get better I will VERY gladly fufill all my mathematical endeavors. If creating such a formula is to much an incredible task then let me know. It seems possibly reasonably doable because the formula would be veyr muc based on Binet's already composed fromula. Thank you to whomever helps. Math is awesome, and good day!!!
May 27th, 2010, 05:45 AM   #2
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Need help creating formula for:Fn-1 + Fn-2 + ... + Fn-k

Quote:
 Originally Posted by JohnBartle I am a novice computer programmer, and I am looking to write a simple data compression program. It seems that one could use a recurrence relation sequence or Closed-form expression thereof - to compress any file down to a few bytes. See files on a computer could be looked at as one really big(astronomical number). A small formula, only a few bytes wide, could ideally represent any abitrary sized file(e.g. 1, 2, 50 gigs+, etc), and when one needed to decompress - the zip program would merely caclulate the formula, and the end result would be a really big binary number. The binary would be your file.
Just so you know, this approach won't work. Any file with reasonable Kolmogorov complexity (relative to its length) won't be able to be compressed in this way. In particular, the asymptotic fraction of files which can be compressed at all with this approach is 0, and the fraction of 'large' (say, > 1 kB) files that can be compressed to "a few bytes" (say, < 100 B) goes to 0 very quickly. Example:

By the Pigeonhole Principle, at most
Code:
0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000237%
of 1000-bit files can be compressed by this (or any) method to 100 bits or less. With a fixed choice of compression algorithms, if you choose a trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion 1000-bit files at random, the chance that any of them can be compressed to 100 bits or smaller is 0.000024%.

Quote:
 Originally Posted by JohnBartle Fibonacci numbers do not include every number - which, of course, is a very good thing. So I was thinking that I could use a formula similar to "Binet's formula". . So I need a similar Closed-form expression that would calculate: Fn-1 + Fn-2 + ... + Fn-k k being any arbitrary number > 2.
I feel it's worth pointing out that not every number can be expressed as $F_{n-1}+F_{n-2}+\cdots+F_{n-k}$ for n > k (probably this restriction can be dropped). It *is* possible to write every number as a sum of Fibonacci numbers: in particular, every number has a unique Zeckendorf representation (a sum of nonconsecutive Fibonacci numbers).

Quote:
 Originally Posted by JohnBartle Would anyone be so kind as to write me a closed-form expression for the recurrence relation sequence: Fn-1 + Fn-2 + ... + Fn-k
If n - k is large enough, this should be the nearest integer to $\frac{\varphi}{\sqrt5}(\varphi^n-\varphi^{n-k})$. n - k > 1 should be enough; this may actually work down to 0. But be sure you're calculating with enough digits of precision!

 May 27th, 2010, 10:32 PM #3 Newbie   Joined: May 2010 Posts: 6 Thanks: 0 Re: Need help creating formula for:Fn-1 + Fn-2 + ... + Fn-k Thank you CRGreathouse - your answer was fantastic. My mind is really really foggy right now, as usual, but as soon as I am thinking clearly enough to ask and discuss super compression I will be revisiting this thread. I understand that super compression is considered a pipe dream, but I also understand that anytime anyone ever wanted anything in this world and they sought out all the necessary information and resources to achieve - they eventually miraculously do achieve despite everyone saying their dream or idea was impossible. This phenomena has occurred countless times. What I am saying is that there is always a way............................................... ............... It dawned on me ,as I was reading your post, a number of really good reasons why my formula or "most" any formula or algorithm would not work - some of which I already new. The truth is that I didn't genuinely think that my formula could cover every possible number. I did however overlook the obvious that the range between one number and the next greater gets bigger and bigger towards infinity. I intended to use this formula as a learning experience . For me,there are just to many ins and outs to numbers just to rule out super compression, and even though I see compelling reasons to discount it, I am compelled even more by the infinite possabilities to make a way where there was no way. Very good day to you, and thanks again!
May 28th, 2010, 05:16 AM   #4
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Need help creating formula for:Fn-1 + Fn-2 + ... + Fn-k

Quote:
 Originally Posted by JohnBartle I understand that super compression is considered a pipe dream
No, practical (say, 1000 qubit) quantum computing is a pipe dream. Compression of the sort you're looking for is flat-out impossible.

What you need to do is understand the limitations and find ways of working around them. For example, .jpg images achieve extremely high compression by throwing away information that isn't easily visible to the human eye. The Joint Photographic Experts Group understood this result and found a way around it: they don't keep all the original information, just the 'visually significant' information. If you can find a similar way around, you may be able to create a great compression algorithm. But if you simply try to fight the bound, you will fail. (No skin off my back if you try, though.)

Consider it this way. There are 2^100 = 1267650600228229401496703205376 100-bit files. There are 2^200 = 16069380442589902755419620923411626025222029937827 92835301376 200-bit files. If you compress all 200-bit files to 100 bits, then there is (by the Pigeonhole Principle -- but it's obvious if you think about it) some 100-bit file that is the compressed version of at least 2^200 / 2^100 = 1267650600228229401496703205376 different 200-bit files. How will you tell which one is the right one to decompress to?

May 28th, 2010, 03:17 PM   #5
Newbie

Joined: May 2010

Posts: 6
Thanks: 0

Re: Need help creating formula for:Fn-1 + Fn-2 + ... + Fn-k

Quote:
 Originally Posted by CRGreathouse No, practical (say, 1000 qubit) quantum computing is a pipe dream. Compression of the sort you're looking for is flat-out impossible. What you need to do is understand the limitations and find ways of working around them.
I agree, redesigning inner components of a computer (cpu, memory, etc) such as with quantum computing would very much seem more possible. When I've learned all I can learn about math, if I still can not find a way then I will call it quits. I, indeed, intend to investigate other physical forms of compression when I am feeling better.

Quote:
 Originally Posted by CRGreathouse Consider it this way. There are 2^100 =1267650600228229401496703205376 100-bit files. There are 2^200 = 16069380442589902755419620923411626025222029937827 92835301376 200-bit files. If you compress all 200-bit files to 100 bits, then there is (by the Pigeonhole Principle -- but it's obvious if you think about it) some 100-bit file that is the compressed version of at least 2^200 / 2^100 = 1267650600228229401496703205376 different 200-bit files. How will you tell which one is the right one to decompress to?
I think I undertand... You seem to be saying that if one represents a certain set of larger numbers by smaller then they will eventually run out of the smaller - before - they run out of the bigger which would still need to be represented.

I also think I understand your comment:
Quote:
 Originally Posted by CRGreathouse By the Pigeonhole Principle, at most Code: 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000237% of 1000-bit files can be compressed by this (or any) method to 100 bits or less. With a fixed choice of compression algorithms, if you choose a trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion 1000-bit files at random, the chance that any of them can be compressed to 100 bits or smaller is 0.000024%
Above, you seem to be saying that one can use ------------ANY-------------- fixed combination of ANY algorithms that will fit within 100 bits or smaller(which would represent one's compressed file) and ALL the outputs from those algorithms would only account for an almost infinitesimally small fraction of the total quantity of numbers that can be extracted from 1000 bits. So there may be some 1000 bit files that would, infact, compress down to 100 bits or less but there are far, far, far....... more that will not.

---------------------------------------------

My problem is that when I look at things like irrational numbers, which may be infinitely complex, I perceive that there is some identity that has not been found yet, and may hold the key to super compression with today's current computer technology. Of course, the more I think about it, I see the seeming impossibility and futility of it. Really, if nothing else, I will consider my endeavors as a really fun learning experience.

Very good day to you then, CRGreathouse. Thank you for your help, friend, I've learned alot from your post.

[color=#FF0000]EDIT:
================================================== ========[/color]
I said earlier that all things were possible, but after thinking about it - what I should have said was that all things are probably possible - if - one has a healthy mind an ability to express that healthy mind, and an infinite amount of resources to work with. However, I now realise the binary representation of numbers on todays current computers is finite.

Just thought I'd throw that in.

May 29th, 2010, 04:29 AM   #6
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Need help creating formula for:Fn-1 + Fn-2 + ... + Fn-k

Quote:
 Originally Posted by JohnBartle Above, you seem to be saying that one can use ------------ANY-------------- fixed combination of ANY algorithms that will fit within 100 bits or smaller(which would represent one's compressed file) and ALL the outputs from those algorithms would only account for an almost infinitesimally small fraction of the total quantity of numbers that can be extracted from 1000 bits. So there may be some 1000 bit files that would, infact, compress down to 100 bits or less but there are far, far, far....... more that will not.
Right! Actually, this is how real-world compression works: the vast majority of inputs are 'compressed' to something larger (maybe 1-10 bytes larger), while a vanishingly small percentage can be compressed by a 'reasonable' amount. But fortunately many of the files we care about are in this small fraction. For example, text files are very compressible: they don't contain a random diustribution of possible characters (no upper ASCII, no BEL character; mostly letters, numbers, and punctuation) and repeat sequences a lot (like "the ").

Quote:
 Originally Posted by JohnBartle My problem is that when I look at things like irrational numbers, which may be infinitely complex, I perceive that there is some identity that has not been found yet, and may hold the key to super compression with today's current computer technology. Of course, the more I think about it, I see the seeming impossibility and futility of it. Really, if nothing else, I will consider my endeavors as a really fun learning experience.
In the Kolmogorov sense, an irrational number like sqrt(2) has very little information: you can calculate arbitrarily many digits with a short algorithm.

But please, continue your investigation -- I think you will find it enlightening. I'm glad that you're keeping on open mind.

May 29th, 2010, 08:44 PM   #7
Newbie

Joined: May 2010

Posts: 6
Thanks: 0

Re: Need help creating formula for:Fn-1 + Fn-2 + ... + Fn-k

I apologize for making another post for my following comments, and I really would have preferred to just edit my previous post up above, but my edit time has expired. So, I don't mean to bump this thread and flag anyone's attention.

Quote:
 Originally Posted by JohnBartle [color=#FF0000]EDIT: ================================================== ========[/color] I said earlier that all things were possible, but after thinking about it - what I should have said was that all things are probably possible - if - one has a healthy mind an ability to express that healthy mind, and an infinite amount of resources to work with. However, I now realise the binary representation of numbers on todays current computers is finite. Just thought I'd throw that in.
Ok, up above, I make a comment about another earlier comment. Above, I say, " However, I now realise the binary representation of numbers on todays current computers is finite."

In this following comment, I attempt to correct my earlier comment:
Quote:
 What I am saying is that there is always a way............................................... ...............
But you know what, I recant my correction... I recant because my original comment may - or may not - have been completely wrong to begin with. See, there are algorithms which can produce infinitely complex numbers (which may or may not be quite in the Kolmogorov sense). So an infinite amount of data can be extracted from such an algorithm - which means that in, at least, an indirect way - ALL things are possible - even when working with "certain" limited resources -- or maybe -- even "ALL" limited or finite resources.

I apologize again for bumping this thread, I did not want to leave such a mistake unfixed. Also, since I'm posting anyways, I would like to reiterate that, when I'm feeling better, I would still like to present a few theoretical ideas, and ask some hypothetical, and bizzare questions (which may or may not be stupid) of things that have caught my eye about super compression with todays current computer technology.

So, I will probably be back. Good day to everyone.

May 30th, 2010, 01:08 PM   #8
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Need help creating formula for:Fn-1 + Fn-2 + ... + Fn-k

Quote:
 Originally Posted by JohnBartle However, I now realise the binary representation of numbers on todays current computers is finite.
The number of distinct n-bit strings is finite, without regard to whether you represent them on a computer, a chalkboard, or on your fingers. The limitation is in the representation, not in our current version of computing.

Also (this is deep!), there is a finite limit on the amount of information that can be represented in the entire universe, thanks to the holographic principle. I don't recall the exact amount but it's below a googol bits.

Quote:
 Originally Posted by JohnBartle See, there are algorithms which can produce infinitely complex numbers (which may or may not be quite in the Kolmogorov sense). So an infinite amount of data can be extracted from such an algorithm - which means that in, at least, an indirect way - ALL things are possible - even when working with "certain" limited resources -- or maybe -- even "ALL" limited or finite resources.
Insofar as an algorithm is a finite sequence of instructions in some language, no algorithm can generate a sequence with infinite Kolmogorov complexity. So in what sense (if not Kolmogorov's) can an algorithm produce a sequence of infinite complexity? What definition are you using? Just trying to clear things up.

June 1st, 2010, 10:09 PM   #9
Newbie

Joined: May 2010

Posts: 6
Thanks: 0

Re: Need help creating formula for:Fn-1 + Fn-2 + ... + Fn-k

First, to CRGreathouse, I am sorry for any of my ramblings, and lack of haste to respond. I have 0 background in mathematics or really anything at all for that matter (except for a little in C++ programming), and as I've said, I am not thinking coherently. So, I openly admit to and acknowledge my foolishness and ignorance, but I am trying. My response was slow because I was trying to think of a proper and good way to respond, but I don't think my illness will allow this.

Quote:
 Originally Posted by CRGreathouse The number of distinct n-bit strings is finite, without regard to whether you represent them on a computer, a chalkboard, or on your fingers. The limitation is in the representation, not in our current version of computing.
The number of distinct n-bit strings is finite, but I meant that what can be produced is infinite, and, therefore, contains an infinite amount of data - not necessarily really complex, but infinite.

And yes, of course, the limitation is in the representation, - and I meant that our current computer technology is limited - to - our binary representation.

Quote:
 Originally Posted by CRGreathouse Also (this is deep!), there is a finite limit on the amount of information that can be represented in the entire universe, thanks to the holographic principle. I don't recall the exact amount but it's below a googol bits.
I have complete confidence that neither this nor any other principle nor law is absolutely complete, sound or accurate – simply because they are based on subjective interpretation, and because innate inarguable knowledge demontrates that the law that produces the measurable, and observable is not made out the measurable and observable. It is ABSOLUTELY transcendent.I’m sure that they may be well grounded in logic based – very - heavily on empirical and perhaps at least some non-empirical evidence, but human documented physical law is not perfect. I will admit, though, that I was already curious and concerned that not all things are naturally possible to humanity… This – principle -- looks like a party crasher!

Well anyway, I am merely rambling, feel free to ignore.

Quote:
 Originally Posted by CRGreathouse Insofar as an algorithm is a finite sequence of instructions in some language, no algorithm can generate a sequence with infinite Kolmogorov complexity. So in what sense (if not Kolmogorov's) can an algorithm produce a sequence of infinite complexity? What definition are you using? Just trying to clear things up.
In my comment, “See, there are algorithms which can produce infinitely complex numbers (which may or may not be quite in the Kolmogorov sense).” – I may have misunderstood the meaning of Kolmogorov, among other possibilities. I must have assumed that a number – must – first have at least a defined level of high complexity to be Kolmogorov, but I understand now that Kolmogorov complexity is a measure of the lowest computational resources possible needed to specify a thing.

I guess I figured that since any arbitrary algorithm cannot be, according to your statement:“In the Kolmogorov sense, an irrational number like sqrt(2) has very little information",completely complex that certain or maybe all finite algorithms did not qualify as Kolmogorov complex. I did denote, however, that I was not sure.

Now, by "infinitely complex" I meant that certain algorithms can produce an infinite number in which, at least, some newly asymptotically calculated arbitrary parts would break any previous pattern, and so there would be an infinite amount of newness. I was given this impression because of statements like what one might find on Wikipedia, such as this statement listed under "Pi":

Quote:
 Originally Posted by Wikipedia:Pi "Consequently, its decimal representation never ends or repeats. It is also a transcendental number, which implies, among other things, that no finite sequence of algebraic operations on integers (powers, roots, sums, etc.) can be equal to its value"
I have not yet learned what to call this type of complexity.

Good day to you CRGreathouse, I have considered it a pleasure to read your writings

June 2nd, 2010, 07:38 AM   #10
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Need help creating formula for:Fn-1 + Fn-2 + ... + Fn-k

Quote:
 Originally Posted by JohnBartle First, to CRGreathouse, I am sorry for any of my ramblings, and lack of haste to respond. I have 0 background in mathematics or really anything at all for that matter (except for a little in C++ programming), and as I've said, I am not thinking coherently. So, I openly admit to and acknowledge my foolishness and ignorance, but I am trying. My response was slow because I was trying to think of a proper and good way to respond, but I don't think my illness will allow this.
They're not ramblings. (I argue with semicoherent ramblers; you're not amongst them.) You're right, you do lack mathematical background -- but you actually seem to be able to learn, a trait which sets you apart from these cranks.

Quote:
Originally Posted by JohnBartle
Quote:
 Originally Posted by CRGreathouse Also (this is deep!), there is a finite limit on the amount of information that can be represented in the entire universe, thanks to the holographic principle. I don't recall the exact amount but it's below a googol bits.
I have complete confidence that neither this nor any other principle nor law is absolutely complete, sound or accurate – simply because they are based on subjective interpretation, and because innate inarguable knowledge demontrates that the law that produces the measurable, and observable is not made out the measurable and observable.
A far weaker bound comes from the number of particles in the universe, call it 10^82 as a reasonable upper bound; with quantum interactions, they can't store more than 2^(10^82) bits between them. This does assume that they're all in their base state, but I'm sure more calculations on what energy states are possible using all the energy in the universe wouldn't increase this by more than another tetrational level (and probably not more than square the value).

If that's too much, consider that data requires (a positive amount of) mass-energy to store; since the universe's mass-energy is finite, its information capacity is finite also. If there was infinite mass-energy, then all matter would be attracted with infinite force and hence infinite rapidity (the relativistic version of speed/velocity). This shows that the amount of information in the universe is finite, even if very large.

Quote:
 Originally Posted by JohnBartle In my comment, “See, there are algorithms which can produce infinitely complex numbers (which may or may not be quite in the Kolmogorov sense).” – I may have misunderstood the meaning of Kolmogorov, among other possibilities. I must have assumed that a number – must – first have at least a defined level of high complexity to be Kolmogorov, but I understand now that Kolmogorov complexity is a measure of the lowest computational resources possible needed to specify a thing.
Right. Or at least, close: it's the smallest space needed to specify the program. The program itself may take large amounts of computational resources (time & memory).

Quote:
 Originally Posted by JohnBartle I guess I figured that since any arbitrary algorithm cannot be, according to your statement, “In the Kolmogorov sense, an irrational number like sqrt(2) has very little information", completely complex that certain or maybe all finite algorithms did not qualify as Kolmogorov complex. I did denote, however, that I was not sure.
I don't know what you mean here. Algorithms don't have complexity, numbers do; and it's not a binary measure (complex or not) but an amount of information that needs to be specified, for a given computational model.

Quote:
 Originally Posted by JohnBartle Now, by "infinitely complex" I meant that certain algorithms can produce an infinite number in which, at least, some newly asymptotically calculated arbitrary parts would break any previous pattern, and so there would be an infinite amount of newness.
If I understand you properly, I disagree. An algorithm (that is, a finite sequence of commands) can produce the digits of pi, so pi has low Kolmogorov complexity. But perhaps you mean something weaker by "break any previous pattern". If you mean that it won't repeat, then the claim true since there are algorithms that generate the digits of irrational numbers like pi.

Quote:
Originally Posted by JohnBartle
Quote:
 Originally Posted by Wikipedia:Pi "Consequently, its decimal representation never ends or repeats. It is also a transcendental number, which implies, among other things, that no finite sequence of algebraic operations on integers (powers, roots, sums, etc.) can be equal to its value"
I have not yet learned what to call this type of complexity.
A decimal number which never repeats is called irrational; one that cannot be expressed as the root of a polynomial with integer coefficients is called transcendental.

 Tags creating, fn2, fnk, forfn1, formula

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post swm06 Calculus 1 May 7th, 2013 05:14 PM lowena Computer Science 25 January 2nd, 2013 02:19 PM tedward570 Algebra 3 October 2nd, 2012 03:33 PM Camper Computer Science 0 September 5th, 2011 02:24 PM bobchiba Algebra 5 November 7th, 2008 01:23 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top