Share Your Experience: Take the 2024 Developer Survey

Questions tagged [diophantine-equation]

The tag has no usage guidance.

11 questions
Filter by
Sorted by
Tagged with
63 views

Given required total area and capacity, choose an amount for each of three given modules

Suppose you have three modules $m_1,m_2$ and $m_3$, each with a capacity of $c_i$ and area $a_i$. You are also given $A$ and $C$. How can you find some of the solutions to choose an amount of each ...
66 views

Reduction from Diophantine Equation Problem to Halting Problem

I want to study the reduction from the Diophantine Equation Problem (Hilbert's tenth problem) to the Halting problem. Can you either explain it to me or give me a credible source from which I can ...
• 1
1 vote
76 views

Is there a way to find the fixed size subsequence sum in an N by M array that is the closest to a given N-dimensional vector?

Basically, I need to solve the multivariate case of the "closest subsequence sum to a given value K" problem, which is solved with dynamic programming as far as I understand. Let's say I ...
• 13
50 views

Is there a simplistic way of describing the proof to the undecidability of David Hilbert's 10th problem?

I recently have been reading a bunch about David Hilbert's famous 10th problem, and trying to understand its proof. I am currently in the process of reading through an explanation of the proof, given ...
60 views

Efficient solution for a particular form of quadratic Diophantine equation

Preface: I know there are a lot of posts already here and elsewhere about algorithms for solving quadratic Diophantine equations in general. I am posting this in the hope that my very particular case ...
1 vote
38 views

algorithm to check the existence of $b-1$ in $(n)_b$?

Given an integer number $n$ (in base 10) and a base $b$, determine whether the representation of $n$ in base $b$, $(n)_b$ has a coefficient with value of $b-1$. ...
• 173
30 views

Efficient algorithm to solve multiplication Diophantine equation

Consider an equations of the form: (a + x) * (b + y) - c = 0 Or: (a + x) * (b + y) = c Or: ...
58 views

Euclidean algorithm - runtime in specific case

I'm going to solving many times this specific equations: $$2^{x+y} \cdot c - a^{y} \cdot z = 1$$ in which $$a$$ can be equal to: $$-7,-5,-3,-1,1,3,5,7.$$ And $$x+y$$ will be equal to $$128.$$ It has ...
• 133
1 vote
40 views

How do you solve a general linear diophantine equation in polynomial time (with minimization constraint)?

Given $$a_1 X_1 + \dots + a_n X_n = b$$ where $a_i, b \in \Bbb{Z}$. How do you come up with a clearer picture of the solution set in polynomial time. Also, what I really want is to do the above,...
1 vote
Given a Diophantine equation $p(x_1,x_2,...,x_n)$, Can I find a reduction from $\text{dioph}(\mathbb{N}) \leq \text{dioph}(\mathbb{N}_e)$? $\mathbb{N}_e$ is the set of even numbers. So I have to ...
How does one find out whether $N = a^b$ for some integer $a$ and $b$?
I was trying to find out how to find whether $N$ is a perfect power or not for some $a$ and $b$ (so the algorithm should discover that it is not a perfect power if it is not expressible in the form \$a^...