All Questions
21 questions
1
vote
2
answers
383
views
Is there any way to estimate this functions: $f(n)=\sum_{d|n}d\varphi(d)$ and $g(n)=\sum_{d|n}\frac{\varphi(d)}{d}$?
Let that $n$ be a natural number and $\varphi(n)$ be the Euler totient function. Is there any formula or estimation for computing functions $f,g$ such that:
$$
f(n)=\sum_{d\mid n}d\varphi(d)
$$
and
$$
...
- 139
10
votes
2
answers
3k
views
Can every integer be written as a sum of squares of primes?
This question is mainly inspired from a different problem I was working on.
Is there a value of $k$ such that, for each $n\in \mathbb N$, the equation
$$\sum_{i=1}^{k}x_i^2=n$$
is solvable in $x_1,\...
- 791
-2
votes
2
answers
149
views
Calculate the great common factor between $2^{2n+1}-1$ and $2^{4m+2}+1$ [closed]
How to calculate the great common factor between $2^{2n+1}-1$ and $2^{4m+2}+1$, where $n$ and $m$ are positive numbers.
We guess that: the great common factor is $1$.
- 577
15
votes
0
answers
365
views
Do primes of the form $4k+1$ ever lead the greatest prime factor race?
Analogous to Chebyshev's race between primes, I examined the race between primes in the greatest prime factors, GPF, of natural numbers. Similar to the regular prime race, in the GPF race, the ...
- 5,470
0
votes
2
answers
288
views
Counting powerful integers. Lower bounds
Remark: The upper bounds are perhaps still more interesting; I may address them in another post.
PROBLEM: Find simple (numerically efficient) lower bounds for the number of powerful integers (...
- 4,786
11
votes
2
answers
1k
views
Do consecutive integers have a big prime factor?
Let us say that three consecutive positive integers $(m-1,m,m+1)$ have a big prime factor if the largest prime factor $p$ of $N=(m-1)m(m+1)$ satisfies $e^p>N$.
I ckecked that it is true for all $m&...
9
votes
3
answers
584
views
Why is there an unexpected increase in the density of certain types of Goldbach primes?
Note: Posted in MO since it was unanswered in MSE.
I was checking how quickly we can verify Goldbach's conjecture for a given even number $n$ and it was clear that searching backward starting from the ...
- 5,470
1
vote
0
answers
84
views
How common are semiprimes with equally bitsized factors among semiprimes with equal bitsize?
I am curious about the following after having looked at the paper "Almost primes in almost all short intervals", theorem 3 says:
Almost all intervals $[x, x + \log^{3.51}{(x)}]$ with $x ≤ X$...
- 11
2
votes
0
answers
205
views
Sum of all primes below $n$ without listing all primes below $n$
Asymptotically there is around $\frac{n}{\ln n}$ primes below a given integer $n$. Thus $\frac{n}{\ln n}$ is a lower bound for the time complexity of any algorithm that at some point finds each prime ...
- 21
20
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 ...
- 35.5k
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
2
votes
0
answers
54
views
Asymptotic growth of the collection of Miller-Rabin pseudo-primes witnessed by a set
Consider a set $S$ of positive integers[*]. Define $P(S)$ as the set of numbers $N$ for which elements of $S$ are "witnesses" for the Miller-Rabin test for primality of $N$. Explicitly $P(S)=...
- 1,566
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,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
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
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
0
votes
1
answer
120
views
How many integers $x$ satisfy that $x*p(x) \leq n$, where $p(x)$ means the largest prime factor of $x$?
I guess that the number of integers $x$ which satisfy the condition $x*p(x) \leq n$ is $O(n^{2/3})$ or $O(n^{3/4} / \ln n$), but I cannot prove it. I just write a program to count the number. The ...
- 601
1
vote
1
answer
153
views
Specializing non-trivial primality tests
Primes $p$ are integers with no factors (composite allowed) in $[1,p]$. There is a polynomial time test for them.
Given an interval $[a,b]$ what is the best way to test given integer $q$ has no ...
- 13.9k
5
votes
2
answers
314
views
Congruences for the non-divisors of Euler's $\phi(n)$
If $n$ is composite, then $\phi(n) < n-1$: hence, there is at least one number $d$ which does not divide $\phi(n)$ but divides$(n-1)$. We shall call $d$ the totient divisor of $n$. The purist will ...
- 5,470
4
votes
1
answer
708
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 ...
- 9,114
12
votes
1
answer
867
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 & ...
- 9,114