Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [diophantine-equation]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
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 ...
raibd's user avatar
  • 9
0 votes
0 answers
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 ...
Mgh's user avatar
  • 1
1 vote
1 answer
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 ...
oleg's user avatar
  • 13
2 votes
1 answer
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 ...
David Jentjens's user avatar
2 votes
1 answer
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 ...
William Rosenbloom's user avatar
1 vote
1 answer
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$. ...
Math-fort's user avatar
  • 173
0 votes
0 answers
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: ...
Alexandr Dorofeev's user avatar
0 votes
1 answer
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 ...
Tom's user avatar
  • 133
1 vote
0 answers
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,...
HighAsAKiteOnMath's user avatar
1 vote
2 answers
63 views

Multivariate polynomials

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 ...
Joe Smith's user avatar
5 votes
2 answers
340 views

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^...
Charlie Parker's user avatar