wraithx on Wed, 25 Jan 2023 04:02:41 +0100

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Looking for a smaller solution...


While I was working on a problem, someone offered a Pari/GP solution. While it works great, the solution is larger than I'd like. I was wondering if there was an alternate way to compute the solution that results in a smaller answer?

Here is a simplified version of the problem I'm working on:
Does anyone know of a way to find, or construct, a number B = k*x + y with x and y given, that is only divisible by primes from a finite set of primes P?

For example, if x=97929 and y=83261 and P = [1171, 1429, 1811, 2339], how would we find or construct B? Or, perhaps show that one doesn't exist?

I know we could do a brute force search, looping over k values and checking the factors of B, but I'm hoping someone might know of a way to construct, or constructively find, B. Is this possible?

In the full problem I'm working on, my numbers x and y have a few hundred digits, and my set P has over 1000 primes. Also, x has only small prime factors p^e, with p a prime < 1000 and where e is usually 1, but can be higher, like 2^13, or 3^8, 7^5, etc. Also, all p are less than the smallest prime in P, ie no prime is in both sets.

The code that was offered is:
which "outputs a vector giving the exponents that each of the primes in P need to be raised to in the product." ie B = product(P[i]^e[i]) where e[i] is the output of the above function.

For the full problem, this does give a solution, but each exponent e[i] in the solution has over 90 digits. Also, Pari/GP only finds exponents for 142 of the primes from P (the rest of the exponents for the other primes in the set are 0). I understand this is due to the fact that my x value has 141 factors (p_i^e_i).

Does anyone know of a way to reduce the size of the "exponents" in the solution? Perhaps by using more primes from the set P? Is there a way to get Pari/GP to use more than 142 primes from P to generate its solution to this problem? I don't need to find the smallest B value to my problem, but I would like to find a "small" B value that is computable. Perhaps a B value with only a few hundred, or a few thousand, digits. Thank you in advance for any help!

-David C.