Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
46
questions
5
votes
3
answers
2k
views
Goldbach conjecture and other problems in additive combinatorics
The field is also known as additive number theory. I am interested in sums $z=x + y$ where $x \in S, y\in T$, and both $S, T$ are infinite sets of positive integers. For instance:
$S = T$ is the set ...
- 3,088
54
votes
2
answers
8k
views
Walsh Fourier transform of the Möbius function
This question is related to this previous question where I asked about ordinary Fourier coefficients.
Special case: is Möbius nearly orthogonal to Morse
August Ferdinand Möbius (November 17, 1790 – ...
11
votes
0
answers
765
views
Borderline Collatz-like problems
The usual Collatz map is $C:n \mapsto n/2$ if $n$ even, $(3n+1)/2$ if $n$ odd. Let $f^{\circ (r+1)}:=f \circ f^{\circ r}$.
We suspect that for every fixed $n>0$, the sequence $C^{\circ r}(n)$ ...
25
votes
3
answers
2k
views
Unexpected behavior involving √2 and parity
This post makes a focus on a very specific part of that long post. Consider the following map:
$$f: n \mapsto \left\{
\begin{array}{ll}
\left \lfloor{n/\sqrt{2}} \right \rfloor & \...
19
votes
2
answers
2k
views
Is formula valid for relating $\pi$ with ALL of its OEIS A002485(n)/A002486(n) convergents?
Could anyone try to prove that the below conjectured formula is valid for relating $\pi$ with ALL of its convergents - those, which are described in OEIS via A002485(n)/A002486(n)?
$$(-1)^n\cdot(\pi - ...
- 335
18
votes
2
answers
6k
views
Efficient computation of integer representation as a sum of three squares
Recently I've been studying the problem of integer representation as sum of three squares. Most of the articles that I've found study the function $r_m(n)$ which counts the number of representations ...
- 1,573
11
votes
1
answer
2k
views
Integer values of a rational function
Suppose we are given a rational function with numerator and denominator being polynomials with integer coefficients. Is there an efficient algorithm for finding all integers arguments at which the ...
- 30.6k
4
votes
0
answers
429
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$ ...
44
votes
5
answers
23k
views
Does pi contain 1000 consecutive zeroes (in base 10)?
The motivation for this question comes from the novel Contact by Carl Sagan. Actually, I haven't read the book myself. However, I heard that one of the characters (possibly one of those aliens at ...
- 31.5k
24
votes
2
answers
2k
views
Do these rational sequences always reach an integer?
This post comes from the suggestion of Joel Moreira in a comment on An alternative to continued fraction and applications (itself inspired by the Numberphile video 2.920050977316 and Fridman, ...
19
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 ...
- 40.8k
12
votes
1
answer
846
views
Analytic lower bounds on the first sign change of pi(x) - li(x)?
There have been many results on the first sign change of $\pi(x)-{\mathrm{li}}(x)$: among others, Lehman, te Riele, Bays & Hudson, Demichael, Chao & Plymen, and most recently Saouter & ...
- 8,984
12
votes
1
answer
539
views
Seeking references for finding primes infinitely often
I've been pondering this weakened version of the finding primes problem for a while:
Is there an algorithm which given $k$ outputs a prime $p > 2^k$ in time $F(\log_2(p))$?
This differs from ...
- 2,254
11
votes
3
answers
2k
views
Mertens' function in time $O(\sqrt x)$
This MathOverflow question seems to indicate that the state of the art in computing
$$
M(x)=\sum_{n\le x}\mu(n)
$$
takes time $\Theta(n^{2/3}(\log\log n)^{1/3}),$ which matches my understanding. ...
- 8,984
8
votes
3
answers
2k
views
Numerical evaluation of the Petersson product of elliptic modular forms
It is known how to compute the Fourier expansion of elliptic modular forms using modular symbols, and it is known how to get numerical evaluations of $L$-functions of various type ; it's possible to ...
5
votes
1
answer
601
views
Eulerian ordering of the integers modulo n
Let $n>1$ be an integer. Consider the set $C_n := \{0,1, \dots , n-1\}$.
An Eulerian ordering of $C_n$ is an ordering $r_1, \dots, r_n$ of its elements such that:
$$\forall i \le n \ \forall j&...
5
votes
2
answers
329
views
Reliability of ILP approach to number-theoretic optimization
This question is inspired by the recent answer, where @RobPratt proposed to use integer linear programming (ILP) for solving a number-theoretic optimization problem. I will consider a very similar ...
- 30.6k
4
votes
4
answers
640
views
What or where is the series expansion of the function $\ln\bigl(\frac{\tan x}{x}-1\bigr)$ or $\ln(\tan x-x)$ around $x=0$?
It is known that
\begin{equation*}
\tan x=\sum_{k=1}^{\infty}\frac{2^{2k}\bigl(2^{2k}-1\bigr)}{(2k)!}|B_{2k}|x^{2k-1}, \quad |x|<\frac{\pi}{2}
\end{equation*}
and
\begin{equation*}
\ln\tan x=\ln x+\...
- 838
68
votes
7
answers
5k
views
Open project: Let's compute the Fourier expansion of a non-solvable algebraic Maass form.
OK so let's see if I can use MO to explicitly compute an example of something, by getting other people to join in. Sort of "one level up"---often people answer questions here but I'm going to see if I ...
- 40.8k
48
votes
4
answers
3k
views
Twin primes conjecture and extrapolation method
Let $(p_1, p_2)$ be a twin prime pair, where we include $(2, 3)$. If $p_1 \equiv 1$ mod $4$ then we let $t_{(p_1, p_2)} := p_1 ^ 2 / p_2 ^ 2$ otherwise, we let $t_{(p_1, p_2)} := p_2 ^ 2 / p_1 ^ 2$.
...
- 1,305
26
votes
3
answers
2k
views
Sum of squares and divisibility
Consider an integer of the form $$N = 1 + \sum_{i=1}^r d_i^2$$ where $d_i \in \mathbb{N}_{\ge 3}$ and $d_i^2$ divides $N$.
Question: Must $r$ be greater than or equal to $9$?
Checking (with SageMath): ...
26
votes
3
answers
16k
views
How good is Kamenetsky's formula for the number of digits in n-factorial?
In Number of digits in n!, now closed, there was a mention of Dmitry Kamenetsky's formula, $[\bigl(\log(2\pi n)/2+n(\log n-\log e)\bigr)/\log 10]+1$, for the number of decimal digits in $n$-factorial. ...
- 39k
19
votes
1
answer
1k
views
Possible contemporary improvement to bounded gaps between primes?
In his summary of his book Bounded gaps between primes: the epic breakthroughs of the early 21st century, Kevin Broughan writes
Which brings me to my final remark: where to next in the bounded gaps ...
- 33.9k
13
votes
2
answers
783
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,680
13
votes
4
answers
23k
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,539
12
votes
1
answer
1k
views
How many LLL reduced bases are there?
For a given $n$-dimensional lattice embedded inside $\mathbb R^n$ along with a given inner product, how many distinct LLL-reduced bases are there?
In this question, a lattice is the set of all $\...
- 351
11
votes
4
answers
932
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,693
11
votes
2
answers
402
views
Extension of Dickson's theorem on integers of the form $a^2+b^2+2c^2$
Theorems V in this paper of L.E. Dickson states that the following two sets are equal. $$E=\{a^2+b^2+2c^2 \ | \ a,b,c \in \mathbb{Z}\} \ \text{ and } \ F=\mathbb{N} \setminus \{4^k(16n+14) \ | \ k,n \...
11
votes
1
answer
2k
views
Best way to find a closest vector in a lattice
Let $v_1,\dotsc,v_n$ be linearly independent vectors in $\mathbb{R}^n$, and let $\Lambda=\bigoplus_{i=1}^n \mathbb{Z}v_i$. The question is, given a vector $w$ in $\mathbb R^n$, find the element $v$ ...
- 351
11
votes
0
answers
826
views
Points of bounded height in a number field
Let $K$ be a number field of absolute degree $d$, let $B$ be a positive real number, and write $S(K, B) = \{x \in K : H(x) \leq B\}$. Here $H$ is the absolute multiplicative height of an algebraic ...
- 1,169
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 ...
6
votes
0
answers
427
views
Are there always at least *five* divisions?
@JosephO'Rourke asked a question about a Collatz like function related to primes:
$f(n) =
\begin{cases}
n^2 & \text{if} \;n \;\text{is prime} \\
\lfloor n/2 \rfloor & \text{if} \;n \;\text{...
- 1,345
6
votes
1
answer
603
views
On a fast high precision numerical analysis C library
This is probably a $y=f(x)$ question, but I searched several times on the MathOverflow without success so I decided to explicitly ask for the help of other members: please feel free to ask me to ...
- 5,632
6
votes
2
answers
453
views
Divisibility labeling on a boolean lattice and positive Euler totient
Let $B_n$ be the rank $n$ boolean lattice (i.e. the subset lattice of $\{1,2, \dots , n \}$). Let $\hat{0}$ and $\hat{1}$ be the minimum and the maximum of $B_n$. Let $f: B_n \to \mathbb{N}$ be a ...
5
votes
0
answers
711
views
Primitive element for a number field, and ramification
Let $K=\mathbb Q(\theta)$ be a number field with integral primitive element $\theta$, and let $f(x)$ be the minimal polynomial of $\theta$. Let $p$ be a rational prime. It's well known that if $p$ ...
- 1,001
5
votes
1
answer
233
views
On a result of Euler on pseudoprimes
In several sources (for instance on page 58 of the first ed. of Crandall & Pomerance book on prime numbers or at the end of this paper by J. H. Jaroma), I have seen a result that goes like this:
...
- 87
4
votes
1
answer
682
views
Calculating the constant in the Bateman-Horn-Stemmler conjecture
Bateman & Horn [1], building on Bateman & Stemmler [2], give a conjectured formula for the density of numbers that produce simultaneous primes in a number of fixed polynomials.
The constant ...
- 8,984
4
votes
1
answer
13k
views
What is the longest known sequence of consecutive zeros in Pi? [closed]
Inspired by this question, I would like to know what is the longest known sequence of consecutive zeros in Pi (in base 10).
So far the longest I have found is the sequence of 8 zero's occurring in ...
- 975
4
votes
0
answers
176
views
Computing the density of a set of multiples
Erdős and his coauthors often wrote about problems relating to the densities of sets of multiples. I have a computational question about the same topic. I have a finite* set $A=a_1<\cdots<a_r$ ...
- 8,984
4
votes
1
answer
1k
views
Computing coefficients for the slash operator of a modular form
Suppose $f$ is a classical modular form of weight $r$ for a (congruence) group $\Gamma$. Let $\gamma$ be any matrix in $\operatorname{SL}_2(\mathbb{Z})$. Then the slash operator $|_\gamma$ is usually ...
- 295
3
votes
1
answer
437
views
Finite group of units in quaternion orders
Let $F$ be a totally real number field, $R$ is a quaternion algebra over $F$ ramified in all infinite places of $F$. Let $\mathcal{O}\subset R$ be an order. By assumption on $R$ its group of units $\...
- 7,027
3
votes
1
answer
497
views
abc-conjecture and positive definite kernels, again?
One formulation of the abc-conjecture is:
$$\forall a,b \in \mathbb{N}: \frac{a+b}{\gcd(a,b)}< \operatorname{rad}\left ( \frac{ab(a+b)}{\gcd(a,b)^3}\right )^2 $$
Let us define:
$$K(a,b) := \frac{2(...
- 2,462
3
votes
1
answer
286
views
Does this condition characterise intervals, among subsets of the real line?
For a real number, $c\in \left]0,1\right[$, consider the following property $\mathbf(\mathbf P_c\mathbf)$ of subsets $A$ of $\mathbb R$:
$\mathbf(\mathbf P_c\mathbf)$ For every bounded set $B\subset \...
- 56.6k
3
votes
0
answers
133
views
Recover cyclotomic integer with bounded coefficients from its known associate
Recall that two cyclotomic integers are called associated if their ratio is a unit in the corresponding ring of cyclotomic integers.
We will view cyclotomic integers as polynomials (of degree $<\...
- 30.6k
0
votes
1
answer
159
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,088
-1
votes
1
answer
303
views
Finite or polynomial number integral points clarification on Coppersmith's theorems (possibility of ellipse counter example?)
Coppersmith states if $f(x,y)$ is an irreducible bivariate with total degree $\delta$ then if he can list all roots $(X,Y)$ of the polynomial in $\mathsf{poly}(\log D,\delta)$ time if the roots ...
- 13.7k