
Math General Math Forum  For general math related discussion and news 
 LinkBack  Thread Tools  Display Modes 
June 26th, 2019, 10:54 AM  #1 
Newbie Joined: Jun 2019 From: Brazil Posts: 1 Thanks: 0  How to find functions & inputs whose output is a specific number
I'm interested in the following problem: given a random number n (n can be gigantic), how do we find a pair function+input(s) whose output is n such that the input(s) are relatively small in size? This problems arises in data compression; consider the bits that make up a file (or a substring of bits of the file) and treat it as a number (i.e. the bits are the binary representation of this number). If we could write a pair function+input(s) whose output happens to be the substring, this whole substring can be replaced by the function+input(s). I've thought of expressing the number as sums (or differences) of relative big powers of prime numbers. Is this a good approach? And, if not, what would be a good one? And how to proceed? Motivation of the question: A simples function like raising the nth prime number to a power S can result (depending on the values of p and S) on various outputs, each of which is unique (given that any number has only one prime factorization). If we pick p = 17 and S = 89435, for example, that's computationally trivial to compute (takes logarithmic time), and will result in a somewhat gigantic number. We can then generate a file whose bits are the same of the binary representation of this number (or at least some of the bits are). (This is just a rough example). The problem is going the other way: Given a bit string (hence, a number), how to express this specific bitstring with less bits (very few, actually) through a function that results in the number. Any ideas/answers/comments are welcome! 

Tags 
find, function or algorithm, functions, inputs, number, number theory, output, prime numbers, specific 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Limit of specific functions  Elize  Math  2  December 15th, 2018 09:21 AM 
Find a specific number  shunya  Elementary Math  0  November 25th, 2015 05:08 AM 
Need to find the value of the Integrand of an indef. integral, given a func, & output  leo255  Calculus  7  September 18th, 2014 07:31 PM 
Finding Specific Integer Solutions of Vector Functions  Muggles420  Number Theory  1  August 31st, 2013 01:52 PM 
Deviation (specific number)  onako  Advanced Statistics  1  February 20th, 2011 02:55 PM 