Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Programming Logic: Finding the smallest equation to a large number

Tags:

algorithm

math

I do not know a whole lot about math, so I don't know how to begin to google what I am looking for, so I rely on the intelligence of experts to help me understand what I am after...

I am trying to find the smallest string of equations for a particular large number. For example given the number

"39402006196394479212279040100143613805079739270465446667948293404245721771497210611414266254884915640806627990306816"

The smallest equation is 64^64 (that I know of) . It contains only 5 bytes.

Basically the program would reverse the math, instead of taking an expression and finding an answer, it takes an answer and finds the most simplistic expression. Simplistic is this case means smallest string, not really simple math.

Has this already been created? If so where can I find it? I am looking to take extremely HUGE numbers (10^10000000) and break them down to hopefully expressions that will be like 100 characters in length. Is this even possible? are modern CPUs/GPUs not capable of doing such big calculations?


Edit:

Ok. So finding the smallest equation takes WAY too much time, judging on answers. Is there anyway to bruteforce this and get the smallest found thus far?

For example given a number super super large. Sometimes taking the sqaureroot of number will result in an expression smaller than the number itself.

As far as what expressions it would start off it, well it would naturally try expressions that would the expression the smallest. I am sure there is tons of math things I dont know, but one of the ways to make a number a lot smaller is powers.

like image 340
ParoX Avatar asked Aug 04 '10 20:08

ParoX


3 Answers

Just to throw another keyword in your Google hopper, see Kolmogorov Complexity. The Kolmogorov complexity of a string is the size of the smallest Turing machine that outputs the string, given an empty input. This is one way to formalize what you seem to be after. However, calculating the Kolmogorov complexity of a given string is known to be an undecidable problem :)

Hope this helps,

TJ

like image 177
tjgreen Avatar answered Nov 01 '22 10:11

tjgreen


There's a good program to do that here: http://mrob.com/pub/ries/index.html

like image 7
Charles Avatar answered Nov 01 '22 09:11

Charles


I asked the question "what's the point of doing this", as I don't know if you're looking at this question from a mathemetics point of view, or a large number factoring point of view.

As other answers have considered the factoring point of view, I'll look at the maths angle. In particular, the problem you are describing is a compressibility problem. This is where you have a number, and want to describe it in the smallest algorithm. Highly random numbers have very poor compressibility, as to describe them you either have to write out all of the digits, or describe a deterministic algorithm which is only slightly smaller than the number itself.

There is currently no general mathemetical theorem which can determine if a representation of a number is the smallest possible for that number (although a lower bound can be discovered by understanding shannon's information theory). (I said general theorem, as special cases do exist).

As you said you don't know a whole lot of math, this is perhaps not a useful answer for you...

like image 4
David_001 Avatar answered Nov 01 '22 09:11

David_001