My Math Forum  

Go Back   My Math Forum > Math Forums > Math

Math General Math Forum - For general math related discussion and news

LinkBack Thread Tools Display Modes
June 26th, 2019, 10:54 AM   #1
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!
DaviFN is offline  

  My Math Forum > Math Forums > Math

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

Copyright © 2019 My Math Forum. All rights reserved.