Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
477 questions
5
votes
3
answers
2k
views
Square root algorithm
I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms?
4
votes
0
answers
154
views
Riemann-Siegel formula for Dirichlet characters
After unearthing and giving a proof of what is now known as the Riemann--Siegel formula for the Riemann zeta function enabling the computation of $\zeta(1/2+iT)$ in time $O(T^{1/2})$,
in 1943 Siegel ...
- 13.1k
11
votes
4
answers
944
views
How close can powers of coprime integers get?
Given coprime $a, b$, what is $$ \min_{x, y > 0} |a^x - b^y| $$
Here $x, y$ are integers. Obviously taking $x = y = 0$ gives an uninteresting answer; in general how close can these powers get? ...
- 1,703
0
votes
0
answers
118
views
what are all possible pairs (k,m) such that n=2k^2+ m^2
I am working on a problem in number theory and would like to count all possible ways to partition an integer $n\geq 1$ into pairs $(k,m)$ of positive integers such that $n=2k^2+m^2$ and $n=4k^2+m^2$. ...
- 11
3
votes
0
answers
97
views
Study of relative class number of 'non-abelian' CM field by using L-functions
I'm currently interested in finding good upper bounds for the relative class numbers of non-abelian CM-fields.
So I'm looking for some references to learn the techniques that can be useful.
So far, I ...
- 1,013
2
votes
1
answer
196
views
Software for $S$-unit equation
Is there any implementation available of an algorithm which solves in full generality the $S$-unit equation $x+y=1$ in a number field? It seems that Magma solves $ax+by=c$ but only in the algebraic ...
- 509
1
vote
0
answers
115
views
Is there an effective genus theory for indefinite quadratic forms?
For positive definite quadratic forms, there is a way to check if two forms are isomorphic by arithmetic equivalence over $GL_n(Z)$ by computing configurations of vector up to some norm and then ...
5
votes
0
answers
339
views
About a diophantine equation from group theory
Is there any set of odd primes $\{p_1, p_2,..., p_k\}$ and natural numbers $a_1,..., a_k$ such that the following equation satisfied:
$${p_1^{2a_1+1}+1 \over p_1+1}\times ....\times {p_k^{2a_k+1}+1 \...
- 1,168
13
votes
0
answers
1k
views
Why am I unable to find primes of the form $(9n)!+n!+1$?
See also Math StackExchange: Is there a prime of the form $(9n)!+n!+1$?
Recently, user Peter from Math StackExchange asked for a prime of the form $(9n)!+n!+1$ (where $n$ is some natural number).
...
- 1,326
1
vote
0
answers
96
views
Smooth number pairs satisfying a congruence
Let $\mathcal P=\{p_1,\dots,p_{2t}\}$ be $2t$ primes between $2^\ell$ and $2^{\ell+1}$ and fix an exponent bound $a\in\mathbb Z_{\geq2}$.
Fix $N\in\mathbb N$ whose prime factors $p$ satisfy $p>2^{\...
- 13.9k
11
votes
1
answer
474
views
Representing field elements in a computer
I'm wondering if there is existing terminology to describe fields $F$ with the properties below. I don't have a completely precise description of the concept I have in mind, but hopefully this will be ...
- 1,021
1
vote
0
answers
192
views
Integer solutions of Diophantine equation $y^2= 1+4n^{\underline k} $
I am looking for the integer solutions for the diophantine equation $y^2 =4n(n-1)(n-2)\cdots (n-k+1)+1$ for a given $k$ where $n>k+1>5$.
In other words,
$$y^2=1+4n^{\underline k},\tag{I}$$
where ...
0
votes
0
answers
149
views
How to determine if a unramifed prime split or not?
Let $K$ be the Number field and $L$ be finite extension where $\mathfrak{p}$ prime of K is unramified. Are there any conditions on $\mathfrak{p}$ so that I can say $\mathfrak{p}$ splits completely in ...
- 743
1
vote
1
answer
218
views
On a quadratic diophantine equation
Given a quadratic diophantine equation in $\mathbb Z[x,y,z]$ of form
$$ax^2+by^2+cx+dy+ez+f=0$$ are there standard methods to solve for it when $$\|(x^2,y^2,z)\|_\infty\leq e^{1/2}$$
$$\|(a,b,c,d,e,f)...
- 1,836
2
votes
1
answer
152
views
When can we decompose a multivariable p-adic power series into product of single variable power series?
Is there any known result of decomposing multivariable power series over $p$-adic field into product of single variable power series ?
For example, consider the following power series in $n$ variables:...
- 930
5
votes
4
answers
792
views
Proving a least prime factor
Suppose that I find a small prime factor $p$ dividing a large number $n$ and I wish to prove that it is the least prime dividing $n$. There are two obvious approaches: either factor $n/p$, or divide $...
- 9,114
12
votes
2
answers
823
views
GRH and the rank of elliptic curves
I have been using the Magma calculator recently, and while calculating ranks of elliptic curves with very big coefficients, there is a possibility to assume GRH is true, which signaficantly speeds up ...
- 3,738
2
votes
0
answers
110
views
Evidence of optimality of sieve algorithms
Sieve techniques apply to integer factoring and discrete logarithm to provide $2^{O(((\log n)(\log\log n)^2)^{1/3})}$ complexity for $n$ bit factoring and $n$ bit prime discrete logarithm.
The state ...
- 13.9k
1
vote
0
answers
139
views
Diophantine approximation and the Euclidean algorithm
My question is whether something I've noticed is well-known. It seems like it must be, but I've been unable to find any references that describe what is outlined below.
Given real $x$ and irrational $...
- 133
2
votes
0
answers
288
views
Best known primality test for the whole intervals of integers up to $10^{20}$ — like the sieve of Eratosthenes
What are the best known primality test(s) for the whole intervals of integers up to $N=10^{20}$ ? "Best" means "have minimal amortized time per tested integer".
That is, the ...
- 121
4
votes
0
answers
447
views
The irrational numbers α such that n odd and m=⌊nα⌋ odd implies ⌊mα⌋ odd
This post is the analogous of that one (about $\sqrt{2}$) but with a much stronger expectation here.
We observed, and then this comment of Lucia proved, that for $\phi$ the golden ratio, if $n$ ...
2
votes
2
answers
540
views
Algorithm for checking linear independence of algebraic numbers
Is there any if and only if condition for checking $\mathbb{Q}$-linear independence of given a set of numbers say $\alpha_i$ ? More precisely how to check linear independence of given $n$ algebraic ...
20
votes
3
answers
2k
views
Computing (on a computer) the first few (non-trivial) zeros of the zeta function of a number field.
Let $M$ be the splitting field of
x^8 + 3*x^7 + 13*x^6 + 17*x^5 + 45*x^4 + 37*x^3 + 11*x^2 + 112*x + 108
over the rationals. If I've understood some tables ...
- 41.4k
8
votes
5
answers
4k
views
Computational number theory
I am interested in learning computational number theory and doing some computer experiments.
Which sort of number theory problems can be solved by using computers? For example, is it possible to ...
18
votes
3
answers
562
views
How to construct a small coprime?
Given an integer $n$, is there a deterministic algorithm to find in poly$(\log n)$ time an integer $q$, $n < q< n^{c}$, such that $gcd(q,n!)=1$? Here $c>1$ is some fixed constant.
...
- 17.1k
13
votes
1
answer
2k
views
Erdős multiplication problem revisited
This is a well-known problem and is about counting the number of distinct numbers in the $n \times n$ multiplication table.
The very problem has been discussed in-depth and, as such, I require no ...
user56218
3
votes
1
answer
510
views
Yet another question on sums of the reciprocals of the primes
I recall reading once that the sum $$\sum_{p \,\, \small{\mbox{is a known prime}}} \frac{1}{p}$$
is less than $4$.
Does anybody here know what the ultimate source of this claim is?
Please, let me ...
- 8,842
5
votes
1
answer
2k
views
Solving a system of linear equations over the integers
I have a matrix with integral entries $A$ and integer vector $b$, and want to determine if there is exactly one vector $x$ such that $Ax=b$. $A$ is rectangular, and I know there always is a solution.
...
- 2,429
8
votes
2
answers
1k
views
How to compute Dedekind eta function efficiently?
According to wiki: https://en.wikipedia.org/wiki/Dedekind_eta_function, Dedekind eta function is defined in many equivalent forms. But none of them is an explicit description (say in algorithmic ...
- 475
2
votes
1
answer
913
views
Numbers that are the sum of 2 distinct nonzero squares in exactly 1 way [closed]
I need to emulate this sequence for a program: http://oeis.org/A025302
Stuff that I've taken into account:
After finding the prime divisors of a number. I take any divisor as p and apply the ...
- 123
6
votes
2
answers
385
views
Is the nth-power-sum graph connected?
This post was inspired by the Square-Sum Problem presented in Numberphile by Matt Parker.
He asked about Hamiltonianness for $n=2$, and we ask about connectedness for all $n \in \mathbb{N}^*$.
...
0
votes
0
answers
110
views
Common integer roots of polynomials
I have two polynomials of form
$$f_1(w,x)=M_1$$
$$f_2(y,z)=M_2$$
and I have two polynomials of form
$$g_1(w,x,y,z)=M_3$$
$$g_2(w,x,y,z)=M_4$$
where $f_1,f_2,g_1,g_2\in\mathbb Z[w,x,y,z]$ and $M_1,M_2,...
- 13.9k
0
votes
1
answer
165
views
About another potential characterization of normal numbers
Normal numbers, in a nutshell, are real numbers that have a "uniform" distribution of digits in standard numeration systems (binary, decimal, and so on.) You can find a formal definition and ...
- 3,098
2
votes
0
answers
96
views
Geometry for an odd perfect number? (Second question)
Let $e_d$ be the $d$-th standard-basis vector in the Hilbert space $H=l_2(\mathbb{R})$.
Let $h(n) = J_2(n)$ be the second Jordan totient function.
Define:
$$\phi(n) = \frac{1}{n} \sum_{d|n}\sqrt{h(d)}...
- 3,144
1
vote
0
answers
57
views
Hecke eigenvalues of Siegel Modular forms of level greater than two
I wish to compute Hecke eigenvalues of Siegel Modular forms of level greater than two using the software like SAGE OR MAGMA. Is it possible to do the same?
- 248
16
votes
4
answers
25k
views
Is there an efficient algorithm for finding a square root modulo a prime power?
Cipolla's algorithm http://en.wikipedia.org/wiki/Cipolla's_algorithm is an efficient algorithm for finding a square root modulo a prime number. Is there an efficient algorithm for finding a square ...
- 2,649
3
votes
1
answer
227
views
How can we justify the use of Example 5,4 (of Cohen, Lenstra) assuming their heuristics
In these days, I'm studying Cohen-Lenstra heuristics to understand the paper of Rene Schoof "Class Numbers of Real Cyclotomic Fields of Prime Conductor".
On page 932 of Schoof's paper, there is a ...
- 1,013
6
votes
0
answers
290
views
Effective bounds for Fermat's Last Theorem
Suppose $n>2$. By Fermat's Last Theorem, we know that $a^{n}+b^{n}=c^{n}$
has no non-trivial solutions. Can we quantify it more?
More specifically, given $a,b,c,n\in\mathbb{N}$ with $n>2$ and $...
- 583
2
votes
1
answer
145
views
Estimation of a sum involving Stirling's number of second kind and binomial coefficient
Let $S(n, j)$ be Stirling's number of second kind. Let $p\in [0,1]$ and $m \in N$.
Bound from above the following sum:
$$
\sum_{j=0}^m S(n,j) {m \choose j}\, j! \, p^j
$$
- 97
3
votes
0
answers
81
views
I have a question on the definition of 'good' primes in the paper of Cohen and Martinet
I'm reading the paper of Cohen and Martinet 'Etude heuristique des groups de classes'.
In the section 6, for an central idempotent $e$ of $\mathbb{Q}[\Gamma]$ and a prime $p$, the 'goodness' of $p$ is ...
- 1,013
2
votes
0
answers
140
views
Double Diophantine approximation
Let $0 < \alpha < 1$. For any $n$ there is a closest lower Diophantine approximation $\max p / q \leq \alpha$ with integer $0 \leq p < q \leq n$. It can be found efficiently, e.g., with Stern-...
- 5,590
4
votes
2
answers
301
views
Quadratic diophantine equations and geometry of numbers
Let (for concreteness) $a = 2$, $b = \sqrt{5}$ and $\varphi = (\sqrt{5}+1)/2$. I am interested in solutions $(w,x,y,z) \in \mathbb{Z}[\varphi]^4$ of the system
$$
w^2 - ax^2 -by^2 + abz^2 = 1
$$
$$
\...
- 2,050
6
votes
0
answers
260
views
Brief history of primality testing theory after 2002?
Its clear that there is about 15 years (2004-2019) after the publication of AKS primality testing in 2002 and its modifications in 2003-2004. AS result, is there any development happened in this ...
- 199
3
votes
1
answer
137
views
Subexponential algorithms that apply only one of factoring and discrete logarithm?
Shor (quantum polynomial), Number Field Sieve (subexponential), Pollard rho (square root) all have both factoring and discrete logarithm over $\mathbb F_p^*$ variants.
What are the subexponential ...
- 13.9k
4
votes
0
answers
248
views
All digits of $2^n$ are even if and only if $n=1,2,3,6,11$ [closed]
All digits of $2^n$ are even if and only if $n=1,2,3,6,11$.
For example,
$2^1=2,2^2=4,2^3=8,2^4=16,2^5=32,2^6=64,\ldots,2^{11}=2048,2^{12}=4096$.
Do you know a proof of this fact or some related ...
11
votes
1
answer
496
views
$p$-adic sums of $p$ terms
My question is inspired by this riddle: Let $p \geq 5$ be prime, and let
$$ 1 + \frac 1 2 + \frac 1 3 + \dots + \frac 1 {p-1} = \frac a b $$
where $a/b$ is the fraction expressed in lowest terms. ...
- 1,105
2
votes
0
answers
153
views
On the smallest solution of a linear congruence
I have the following question. First, consider the following congruence for primes $p\geq 5$:
$24x\equiv -1\;(\mbox{mod}\;p)$.
The smallest $x$, that is, $1\leq x\leq p-1$ for which the above ...
- 21
0
votes
1
answer
809
views
Conjecture that relates matrix systems with some specific functions as solution sets
what is written below is a conjecture that I posed , and I ask for a proof or a disproof of it .I have checked the conjecture from $n$=$1$ up to $n$=$10$ using Matlab, and all results were in ...
12
votes
0
answers
1k
views
Euler's totient function and Riemann hypothesis
I am looking for an upper-bound of the Euler's totient function $\varphi$ which would be equivalent to the Riemann hypothesis (RH). There is the following Nicolas' criterion about primorial numbers $...
1
vote
2
answers
119
views
For a given value of $n$ and $m$, find $\text{fib}(n)$ $\text{mod } m$ where $n$ is very huge. (Pisano Period) [closed]
Input
Integers $'n'$ (up to $10^{14}$) and $'m'$(up to $10^3$)
Output
$\text{Fib}(n)$ $\text{modulo}$ $m$
My questions
For example : Why $\text{fib}(n=2015)$ $\text{mod}$ $3$ is equivalent to $\...
- 111