All Questions
68 questions
2
votes
0
answers
110
views
+50
How to apply Pohlig Hellman using a very limited set of auxiliary inputs in that case?
So I was reading about Talotti, Paier, and Miculan - ECC’s Achilles’ Heel: Unveiling Weak Keys in Standardized Curves. The underlying idea is to lift the discrete logarithm problem to $\mathrm{prime}−...
- 87
1
vote
0
answers
89
views
Test for odd prime triples in a $2p-1$ progression
Let $a(n)$ be A057326 (i.e., first member of a prime triple in a $2p-1$ progression).
Let $b(n) = B$ after $n-1$ iterations where we start with $A=n, B=1$ and for $i$ from $1$ to $n-1$ simultaneously ...
- 4,938
2
votes
1
answer
221
views
A question on signed Stirling numbers of the first kind
Let $(x)_0=1$ and $(x)_n=x(x-1)\cdots(x-n+1)$ for $n=1,2,3,\ldots$. The signed Stirling numbers of the first kind, $s(n,k)$ with $n\ge k\ge0$, are defined by
$$(x)_n=\sum_{k=0}^ns(n,k)x^k.$$
Question. ...
- 15.6k
0
votes
0
answers
169
views
On a property of prime numbers
Let $p_i$ be the $i^{\rm th}$ prime number (i.e. $p_1=2,\ p_2=3,\ p_3=5,\cdots$)
What is the function of number of combinations of $c_1,\cdots,c_n$ in terms of $n$ such that,
$$\sum_{i=1}^{n}c_ip_i\ =\...
8
votes
0
answers
150
views
Can P-recursive functions assume only prime values?
A function $f\colon \{0,1,\dots\}\to \mathbb{R}$ is P-recursive if
it satisfies a recurrence $$
P_d(n)f(n+d)+P_{d-1}(n)f(n+d-1)+\cdots+P_0(n)f(n)=0,\ n\geq 0, $$
where each $P_i(n)\in \mathbb{R}[n]$ ...
- 50.8k
6
votes
1
answer
393
views
Test for pair of odd primes $(p, 2p^2-1)$
Let $a(n)$ be A106483 (i.e., primes $p$ such that $2p^2-1$ is also prime).
Let $b(n)$ be an integer sequence such that $b(n) = B$ after the whole transformation where we start with $A = n$, $B = 1$, $...
- 4,938
5
votes
2
answers
691
views
Representing natural numbers as sums of distinct prime powers
I am investigating whether every natural number $n > 18$ can be represented as a sum $p_1^{m_1} + \dots + p_k^{m_k}$, where $p_1, \dots, p_k$ are distinct primes, and $m_1, \dots, m_k$ are distinct ...
- 1,228
2
votes
0
answers
199
views
Not a twin prime pair test using $\gcd$ only
Let $m$ be an odd positive integer such that $m=2k+1$, $k\in\mathbb{N}$.
Let $v$ be a vector of $n$ positive integers. Let $v(i)$ be the $i$-th element of the vector. Then we start with $v(i)=m(i+1)-2$...
- 4,938
1
vote
1
answer
594
views
Some necessary condition for $\gcd(m,n) $ be a proper divisor of $\gcd(mk_2 +nk_1,mn) $ [closed]
Let $m,n,k_1,k_2 $ be natural numbers such that $(k_1,m)=(k_2,n)=1 $.
Statement 1: $\gcd(m,n) $ is a proper divisor of $\gcd(mk_2 +nk_1,mn) $, for every $k_1,k_2$ having the above property.
Statement ...
- 923
11
votes
9
answers
1k
views
What are examples of problems we know how to solve for primes (or prime powers), but not for composites?
I am interested in seeing examples of research problems which fall into one of the two following categories:
A problem which is solved in the case of primes (or prime powers), but which remains open ...
4
votes
1
answer
206
views
Prime numbers and number of partitions of $n$ into distinct parts with boundary size $2$
Let $a(n)$ be A227559, i.e., number of partitions of $n$ into distinct parts with boundary size $2$. Be careful here: offset is $3$.
I conjecture that $a(4n+2)=2n+1$ for $n>0$ if and only if $2n+1$ ...
- 4,938
0
votes
1
answer
100
views
$a(16n+k)=b(16n+k)-c(16n)$ for $n\geqslant0$, $0 < k < 16$ where $c(n)=b(n)-a(n)$
Let $a(n)$ be A339970 = A329697$($A019565$(2n))$: the sequence begins with
$$0, 1, 1, 2, 2, 3, 3, 4, 2, 3, 3, 4, 4, 5, 5, 6, 2, 3, 3, 4, 4$$
Also let's consider
$$\ell(n)=\left\lfloor\log_{2}(n)\right\...
- 4,938
69
votes
2
answers
4k
views
Function that produces primes
For any $n\geq 2$ consider the recursion
\begin{align*}
a(0,n)&=n;\\
a(m,n)&=a(m-1,n)+\operatorname{gcd}(a(m-1,n),n-m),\qquad m\geq 1.
\end{align*}
I conjecture that $a(n-1,n)$ is always ...
- 4,938
2
votes
1
answer
169
views
A new convolution, on function of $\mathbb F_p^n$ to $\mathbb F_p$ still zero?
Let $p$ integer prime, $f$ a function of $A=\mathbb F_p^n$ to $\mathbb F_p$, with $n\geq p+1$.
Is it true that : for all $x\in A, \sum\limits_{\sigma \in S_n} s(\sigma) \times f(x_\sigma) =0$?
$s$ ...
- 4,074
10
votes
1
answer
694
views
Prime numbers from permutation
Let $P(n)$ of a sequence $s(1),s(2),s(3),...$ be obtained by leaving $s(1),...,s(n)$ fixed and reverse-cyclically permuting every $n$ consecutive terms thereafter; apply $P(2)$ to $1,2,3,...$ to get $...
- 4,938
2
votes
1
answer
292
views
Difference between $n$-th and $(n-1)$-th composite numbers
Let $f(n)$ = 1 if $n$ belongs to A014689, $\operatorname{prime}(n)-n$, the number of nonprimes less than $\operatorname{prime}(n)$. Here $\operatorname{prime}(n)$ is the $n$-th prime number, $\...
- 4,938
2
votes
0
answers
215
views
Two conjectures about generalised A329369
Let $m \geqslant 2$ be a fixed integer.
Let
$$\operatorname{wt}(n,m)=\operatorname{wt}\left(\left\lfloor\frac{n}{m}\right\rfloor,m\right)+n\bmod m, \operatorname{wt}(0,m)=0$$
Then we have an integer ...
- 4,938
2
votes
1
answer
273
views
Primes in modular arithmetic progression
Fix a prime $p$.
I want to get $k<p$ primes $p_1<\dots<p_k$ such that at every $i\in\{1,\dots,k\}$ we have
$$p_i\equiv (2i+1+c)\bmod p$$ where $c$ is fixed and $2k+1+c<p$ holds.
For a ...
- 13.9k
2
votes
3
answers
365
views
Is this number theoretic quantity bounded above?
I am considering a combinatorial argument which involves the following quantity. We use the prime counting function $\pi(n)$ and to save on exponents we set $h=\pi(n/2)$. The quantity as a function ...
- 13k
5
votes
4
answers
819
views
Can one show combinatorially how $\operatorname{lcm}(1, \dotsc, n)$ grows?
Let us write $M(n)$ for $\operatorname{lcm}(1,\dotsc,n)$ for $n$ a positive integer. Asymptotically $M(n)$ tends toward $e^n$. This result uses analytic number theory. (Lcm is least common multiple, ...
- 13k
0
votes
0
answers
143
views
Given $\,m=\prod_k {p_k}^{\alpha_k}\,$ and the function $\,g(m)=\sum_k \alpha_k(p_k-1)^2$, find all solutions of the equation $\,g(2n)=n$
Let's consider the unique decomposition of a natural number $\,m\,$ into its prime factors:
$$\prod_k {p_k}^{\alpha_k}$$
Then, let's define the following arithmetic function (completely additive) $\,g:...
- 1,008
2
votes
0
answers
156
views
Questions about a certain sequence of naturals generated by primorials
I'm working on the following sequence of naturals (which is NOT listed in OEIS)
$$3,5,11,17,23,29,59,89,119,149,179,209,419,629,839,1049,1259,1469,1679,...$$
whose elements are generated this way
$$3=(...
- 1,008
-8
votes
1
answer
520
views
Is Green-Tao's theorem a consequence of Van der Waerden theorem?
Wanting to learn a bit about Ramsey's theory, I read the corresponding article on Wikipedia and stumbled upon this:
"Le théorème de van der Waerden[2] : pour tous entiers c et n, il existe un entier[...
- 6,974
4
votes
0
answers
191
views
Overview of Combinatorial Technique of "Selberg’s Symmetry Formula"
In the paper entitled "A Computational History of Prime Numbers and Riemann Zeros" (on page 4, click here) it is written about "Selberg’s symmetry formula" that-
Until 1950 it was widely believed (...
2
votes
0
answers
192
views
A conjecture on crossing numbers related to primes
For a permutation $\sigma\in S_n$, its crossing number $\text{cr}(\sigma)$ is the number of pairs $\{i,j\}$ with $i,j\in\{1,\ldots,n\}$ such that
$$i<j\le\sigma(i)<\sigma(j)\ \ \text{or}\ \ \...
- 15.6k
0
votes
0
answers
128
views
Number of primes skipped by binomial coefficients?
Take $$B(l,n)=\binom{n+l}{n}$$ and $\mathcal P(t)=\{p\mbox{ prime}:p|t\}$.
What is the cardinality of $\mathcal P(B(l,n))$?
What is minimum cardinality of $L\subseteq\{1,\dots,n\}$ such that $$\...
- 13.9k
8
votes
1
answer
575
views
Unstable Integers
There is a question that has been bothering my mind for quite a while now. I will present it and my current thoughts and progress on it.
Let the prime factorization of an integer $n$ be
$$n = p_1^{...
- 311
1
vote
0
answers
126
views
How many solutions to $p_i|a_{i,1} p_1 + \dotsc + a_{i,n} p_n$?
Consider a system of $n$ divisibility conditions on $n$ prime variables:
$$p_i|a_{i,1} p_1 + \dotsc + a_{i,n} p_n,\;\;\;\;\;1\leq i\leq n,$$
where $a_{i,j}$ are bounded integers. How many solutions ...
- 545
-3
votes
1
answer
269
views
Negative Dirichlet Pigeonhole Principle [closed]
From Dirichlet Pigeonhole Principle if $p$ is a prime and if $a,b\in\mathbb Z$ are in $(0,p/2)$ then there is a $t\in(0,p)\cap\mathbb Z$ such that $\|(x,y)\|_\infty<\lceil\sqrt p\rceil$ holds where ...
- 13.9k
3
votes
0
answers
131
views
Chen primes and permutations
In 1973 the Chinese mathematician J.-R. Chen proved that there are infinitely many primes $p$ such that $p+2$ is a product of at most two primes. Nowadays such primes $p$ are called Chen primes.
For $...
- 15.6k
19
votes
1
answer
3k
views
A mysterious connection between primes and squares
Motivated by two previous questions of mine (cf. Primes arising from permutations and Primes arising from permutations (II)), here I ask a curious question which connects primes with squares.
...
- 15.6k
3
votes
0
answers
293
views
Primes arising from permutations (II)
In Question 315259 (cf. Primes arising from permutations) I asked a question on primes arising from permutations which looks quite challenging.
Here I pose a new question in this direction which does ...
- 15.6k
7
votes
1
answer
531
views
Primes arising from permutations
Recently, Paul Bradley proved in arXiv:1809.01012 that for any positive integer $n$ there is a permutation $\pi_n$ of $\{1,\ldots,n\}$ such that $k+\pi_n(k)$ is prime for every $k=1,\ldots,n$ (cf. ...
- 15.6k
2
votes
1
answer
201
views
The largest number $y$ such that $(x!)^{x+y}|(x^2)!$
Since the multiplication of $n$ consecutive integers is divided by $n!$, then $(n!)^n|(n^2)!$ with $n$ is a positive integer.
Are there any formula of the function $y=f(x)$ that shows the largest ...
- 501
8
votes
2
answers
1k
views
Prime plus square equals prime
Furstenberg–Sárközy's theorem states that if a set of positive integers has positive upper density, then there exists (infinitely many) pair of elements of the set, whose difference is a perfect ...
- 191
5
votes
0
answers
355
views
What is the sum of the binomial coefficients ${n\choose p}$ over prime numbers?
What is known about the asymptotics, lower and upper bound of the sum of the binomial coefficients
$$
S_n = {n\choose 2} + {n\choose 3} + {n\choose 5} + \cdots + {n\choose p}
$$
where the sum runs ...
- 5,470
6
votes
1
answer
640
views
Upperbounding a sum of Legendre-Symbols
Let $p$ be a prime with $p\equiv 3 \mod 4$, for any $\mathcal{I} \subset \lbrace 0,...,p-1 \rbrace $ and any $\mathcal{J} \subset \lbrace 0,...,p-1 \rbrace $ with $\vert\mathcal{I}\vert \leq \sqrt{p} $...
- 93
2
votes
0
answers
116
views
Does each odd prime $p$ have a primitive root $g < p$ which is the sum of two central binomial coefficients?
The central binomial coefficients are those integers
$$\binom{2n}n=\frac{(2n)!}{(n!)^2}\ \ \ (n=0,1,2,\ldots).$$
QUESTION: Does each odd prime $p$ have a primitive root $g<p$ which is the sum of ...
- 15.6k
0
votes
1
answer
306
views
Have you seen this prime distribution before?
The basic question is : has this system been considered before, and how do I find it? References to the literature would be most welcome, but I am asking for reasonable search terms. I will try the ...
- 13k
3
votes
0
answers
265
views
Prove A Skipping Prime Conjecture For Rio?
I am writing a paper to accompany a Short Communication I plan to give in Rio this August. The paper regards work on jumping primes, a project on which Jose Brox has been working with me. I was going ...
- 13k
3
votes
3
answers
388
views
Largest power of $p$ which divides $F_p=\binom{p^{n+1}}{p^n}-\binom{p^{n}}{p^{n-1}}$
I would like to know your comments in order to obtain the largest power of the prime numberr $p$ which divides
$$
F_p= \binom{p^{n+1}}{p^n}-\binom{p^{n}}{p^{n-1}}.
$$
I proved the largest power that ...
- 181
1
vote
0
answers
121
views
Characterization of $t$-gap prime pairs
Everyone who dealt with the Pascal triangle knows the basic fact that $p$ is a prime iff it divides each of the entries $\binom{p}s$, for $0\leq s\leq p$, except for $s=0$ and $s=p$.
Based on ...
- 43.2k
5
votes
1
answer
259
views
Central binomial coefficients deprived of $2$'s: not radicals?
In the paper, P Erdos, R Graham, I Ruzsa, E Straus, On the prime factors of $\binom{2n}n$, Math. Comp., 29:83–92, 1975, it was conjectured that the central binomials are never square-free for $n>4$....
- 43.2k
4
votes
1
answer
464
views
Odd Chebyshev, part 2
Let
$$ \forall_{n=1\ 2\ \ldots}\quad I(n)\ :=\
\frac {(6\cdot n-3)!!}{(2\cdot n-1)!!\cdot(4\cdot n-3)!!} $$
Let $\ M(n)\ $ be the smallest natural number such that
$$ M(n)\cdot I(n)\ \...
- 7,500
2
votes
2
answers
393
views
Playing leapfrog with primes
In connection with how primes jump (How do these primes jump?),
I consider the following game.
Let $R$ be a finite set of positive integers. For this question, I content myself with $R$ being the $k$ ...
- 13k
3
votes
2
answers
491
views
Unknown bias in a distribution related to prime numbers
If $n$ is composite then $\phi(n) < n-1$, hence there is at least one divisor $d$ of $n-1$ which does not divide $\phi(n)$. We call $d$ as the totient divisor of $n$. Trvially, if $n$ is prime then ...
- 5,470
1
vote
3
answers
286
views
Reference book for primality testing [closed]
im searching for good reference to understand the primality testing idea
especially the Elliptic curves and primality for stirling numbers first and second ones , so can any one suggest to me good ...
- 199
0
votes
1
answer
170
views
Minimal number of different values in the sequence $(\mu(d_i)\varphi(d_i))_{i=\overline{{1,\tau(m)}}}$
Let $m=p_1\ldots p_k$ be the prime factorization of some positive integer $m$ and $k\geq 2$.
Let $d_1,\ldots,d_{\tau(m)}$ be all divisors of $m$, where $\tau(m)$ counts the number of divisors of $m$....
- 41
3
votes
0
answers
320
views
On sets of coprime numbers
We know that from prime number theorem that the number of primes below $n$ and above $\frac n2$ (denoted by $\pi_{n,\frac n2}$ is approximately $$\pi_{n,\frac n2}\approx\frac{n}{2\ln n}.$$
Denote by $...
user76479
1
vote
2
answers
375
views
binomial/factorial identity mod p
In trying to determine the spectrum of a well-known ergodic transformation, I came up with the following useful (for me) result.
Let $p$ be a prime and $a$ a positive integer. Then for $M$ a positive ...
- 4,679