Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
477 questions
4
votes
1
answer
723
views
Efficient computation of $\sum_{i=1}^{\sqrt{n}} i^2\cdot\left\lfloor{\frac n{i^2}}\right\rfloor$
I need to compute efficiently the sum
$$
\sum_{i=1}^{\sqrt{n}} i^2\cdot\left\lfloor{\frac n{i^2}}\right\rfloor.
$$
We can do this in $O({\sqrt{n}})$ but I need a faster algorithm: for example, it ...
- 43
6
votes
0
answers
93
views
Computing all eta quotients of given weight and level
I have written a rather naive program for finding all holomorphic eta quotients of
given weight and level (and varying character). When the level has few divisors it is
very fast, but incredibly slow ...
- 13.1k
1
vote
0
answers
77
views
Digit summation of squared numbers
In olympiad teaching period, we have a session that students must try to design a good problem for others. Many times we arrive to good questions but sometimes there are some challenges. In one of our ...
- 4,784
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$ ...
26
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 & \...
11
votes
0
answers
813
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)$ ...
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
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
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
2
votes
1
answer
89
views
Partitioning integers into two parts and exploring relationships with positional numeral systems
I asked this question in Mathematics StackExchange (link) about a month ago, but I have received no answer. It is about the following problem:
Problem:
Are there sets $A,B$ of integers such that $A\...
3
votes
0
answers
189
views
Largest observed value of $S(t)$
Let $S(t)$ be the deviation of the number of zeros of the Riemann zeta function up to height $t$ from the expectation.
What is the largest observed value of $S(t)$ today?
Here is a quote from a ...
- 499
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 ...
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
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
99
views
A problem in modular roots
We have three mutually coprime integers $r,t,M$ where $M\asymp K^{\frac12-2\epsilon}$ and $r,t\asymp K^{\frac14+\epsilon}$ holds with some fixed $\epsilon>0$ and $K>0$ is a large parameter. ...
- 13.9k
4
votes
0
answers
189
views
How to find a CM point with the image in the elliptic curve under modular parametrization given
everyone! Let $E:y^2+y=x^3-61$ be the minimal model of the elliptic curve 243b. How can I find the CM point $\tau$ in $X_0(243)$ such that $\tau$ maps to the point $(3\sqrt[3]{3},4)$ under the modular ...
- 390
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
7
votes
0
answers
274
views
Are there infinitely many zeroes of $\sum_{r = 1}^{n-1} \mu(r)\gcd(n,r) $?
Let $\mu(n)$ be the Möbius function and $S(x)$ be the number of positive integers $n \le x$ such that
$$
\sum_{r = 1}^{n-1} \mu(r)\gcd(n,r) = 0
$$
My experimental data for $n \le 6 \times 10^5 $...
- 5,470
0
votes
1
answer
250
views
If the coefficient of the polynomial positive
I want to know what is following sum coefficient looks like. We sum over all integers $p$, $q$ also we put the condition that $q$ is even. Also, it should depend on the parity of $k$
$$\bar{S}(k)=\...
- 685
5
votes
0
answers
179
views
Finding a presentation matrix with low dimension
Let $R=\mathbb Z[t^{\pm}]$ and $M$ a finitely generated $R$-module. With $A$ a presentation matrix, i.e we have the following exact sequence (usually I'm working with the case where $A$ is an square ...
1
vote
1
answer
189
views
Explicit bivariate quadratic polynomials where Coppersmith is better than standard solver?
http://www.numbertheory.org/pdfs/general_quadratic_solution.pdf gives a general method to solve quadratic bivariate diophantine equation while Coppersmith introduced a method to solve bivariate ...
- 13.9k
2
votes
0
answers
137
views
Compare my software's representation of exponential numbers and 0?
Suppose I have a real number
$$
x=\sum_{i=1}^n a_i e^{\lambda_i}
$$
where $a_i,\lambda_i$s are complex algebraic numbers.
Is there an algorithm to determine whether it is greater than 0 or less than ...
- 1,503
5
votes
2
answers
932
views
How can I find explicit examples of maximal orders of quaternion algebras that are not isomorphic?
I know that there exist algorithms that will construct maximal orders of a quaternion algebra over, say, $\mathbb{Q}$. However, the implemented algorithms that I know of require that you input an ...
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
0
votes
0
answers
83
views
Generating the digits in a base system by repeated multiplication of a number
The first 15 terms of the sequence {a_i} = 2^i are 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768. All of the digits in base-10, i.e. {0, ...
2
votes
0
answers
78
views
Accelerating convergence of a product by multiplying by zeta values: history?
Let $R(s_1,\dotsc,s_n) = \prod_p r(p^{-s_1},\dotsc,p^{-s_n})$, where
$r$ is a rational function on $n$ variables. Say we want to compute the value of $R(s_1,\dotsc,s_n)$ for some choice of $s_1,\dotsc,...
- 545
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
2
votes
1
answer
235
views
How to get asymptotic expansion of the sum of modified Bessel function $\sum_{n=1}^\infty K_0(s\, n)$ as $s\to 0^+$?
I guess for the modified Bessel funcion $K_0(z)$,
$$\sum_{n=1}^\infty K_0(s\, n)
\sim
\frac{-2\log 2 - \log \pi + \gamma}{2} + \frac{\log s}{2} + \frac{\pi}{2\, s}, \quad s\to 0^+,$$
if taking
$$\...
- 21
1
vote
0
answers
123
views
Testing polynomials irreducible over the integers
Let $f\in\operatorname{int}(\mathbb Z)$, the ring of integer-valued rational polynomials. Define $\operatorname{P}^+(f)$ as the number of primes $>0$ that $f$ assumes at distinct integral arguments....
- 862
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
0
votes
0
answers
58
views
Quadrics over the univariate function field with discriminant of minimal degree
Consider a non-degenerate quadric $Q(x,y,z) \subset \mathrm{P}^2$ over the univariate function field $\mathbb{F}_p(t)$, where $\mathbb{F}_p$ is a prime finite field, $p > 2$. For simplicity assume ...
- 1,833
1
vote
1
answer
144
views
Factoring with partial information on gaps
If $N=PQ$ is a semi-prime with $P=N^{\frac12 +\delta}$ and $Q=N^{\frac12-\delta}$ then if we know $\delta\in(0,\frac12)$ to a reasonable precision we can factor $N$ quickly. What precision (number of ...
- 13.9k
3
votes
1
answer
293
views
Number of lattice points on spheres with center not at the origin
Let $k\ge1$. It is known that the number of lattice points on the $k$-sphere $S^k(0)$ (center at the origin, radius $R$), namely the size of $\mathbb{Z}^{k+1}\cap S^k(0)$, is bounded by $R^{k-1+\...
- 187
5
votes
0
answers
195
views
Is there some computational evidence of the $pq$ analog of Serre's conjecture?
The $pq$ analog of Serre's conjecture (see "Mod pq Galois representations and Serre's Conjecture"- Khare, Kiming) states that if $\bar{\rho}_1:G_{\mathbb{Q}}\rightarrow \text{GL}_2(\mathbb{F}_p)$ is a ...
user130124
-1
votes
1
answer
725
views
summation of Euler totient function
Let $\phi(n)$ be the Euler totient function and let $2\leq k\in\mathbb{N}$. For $m\in\mathbb{N}$, are there any known results, upper bounds (tighter than just removing the coprimality) or ...
3
votes
1
answer
108
views
Is coprimality in $NC$?
Following reference https://pdfs.semanticscholar.org/e86e/8d7a267a29b9ad4ca112828109adfec55e8b.pdf claims integer coprimality is in $NC$ and it also has one citation. Is this claim valid?
- 13.9k
2
votes
0
answers
127
views
Coppersmith's method to quadrivariate degree $2$ polynomials that behave as bivariate?
We have a polynomial $f(x_1,x_2,x_3,x_4)\in\mathbb Z[x_1,x_2,x_3,x_4]$ where the only monomials are either from set $$\{x_1,x_1x_2,x_2,x_3,x_3x_4,x_4\}$$ and we seek solutions $(x_1,x_2,x_3,x_4)\in\...
- 13.9k
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 ...
11
votes
2
answers
410
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 \...
2
votes
1
answer
199
views
Decide if a system of arithmetic sequences is an $m$-cover of $\mathbb{N}$
Let $A = \{ a_i + b_i \mathbb{N} \}_{i=1}^{k}$, where $a_1, \ldots, a_k \in \mathbb{N} \cup \{0\}$ and $b_1, \ldots, b_k \in \mathbb{N}$ be a system of arithmetic sequences.
For a positive integer $m$...
- 655
4
votes
1
answer
288
views
Is total degree version and $x,y$ degree version of Coppersmith's theorem correct?
The notes here https://web.eecs.umich.edu/~cpeikert/lic13/lec04.pdf have the note 'Small decryption exponent $d$: so far the best known attack recovers $d$ if it is less than $N^{.292}$. This uses a ...
- 13.9k
1
vote
0
answers
26
views
Uncertainty in semiprime factors
What is maximum $p\in(0,\frac12)$ such that if we know $2p\in(0,1)$ fraction of bits of $PQ$ with $P,Q$ primes it is possible to identify $p$ fraction of bits in each of $P,Q$ with certainty in ...
- 13.9k
18
votes
4
answers
1k
views
In which cyclic cubic number fields does there exist this type of unit?
Let $K$ be a cyclic cubic number field with conductor $f$ and ring of integers $\mathcal{O}_K$.
Define $K$ to be blue if and only if $$\operatorname{Norm}_{K/\mathbb{Q}}(w) = \operatorname{Norm}_{K/...
1
vote
1
answer
465
views
Taking pairwise coprime integers from prescribed sets
Given $m$ and $n$ in $\mathbb Z_{>0}$ what is the computational complexity of picking $n$ pairwise coprime integers each of $m$ bits when they exist?
Given $m$ and $n$ in $\mathbb Z_{>0}$ what ...
- 13.9k
1
vote
1
answer
182
views
How many iterations the best biprime factoring method has to factor a number [closed]
I'm researching method of biprime number factoring. I have a biprime number 1012322327 * 1115382761 (19 decimal digits= 1129126872111204847). I'd like to know how many iterations (or trials) the best ...
- 113
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 $...
12
votes
1
answer
308
views
Factoring polynomials over the abelian closure of the rationals
What algorithms are known to perform the following task?
Input: a univariate polynomial over the rationals $f \in \mathbb{Q}[t]$.
Output: the factorization of $f$ into irreducible factors over the ...
- 32.5k
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
17
votes
2
answers
1k
views
Analogues of the Riemann zeta function that are more computationally tractable?
Many years ago, I was surprised to learn that Andrew Odlyzko does not consider the existing computational evidence for the Riemann hypothesis to be overwhelming. As I understand it, one reason is as ...
- 82.7k
0
votes
1
answer
159
views
Parity and number of squares taken by polynomials in a range?
I have a polynomial $f(x)=a^2x^2+bx+c\in\mathbb Z[x]$ with $f(x)$ not a constant times a square and $abc\neq0$ and I want to know how many $x$ between $-a$ and $a$ the polynomial is a perfect square. ...
- 13.9k