Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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}−...
user2284570's user avatar
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 ...
Notamathematician's user avatar
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. ...
Zhi-Wei Sun's user avatar
  • 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\ =\...
yash vinayvanshi's user avatar
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]$ ...
Richard Stanley's user avatar
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$, $...
Notamathematician's user avatar
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 ...
Marcos Cramer's user avatar
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$...
Notamathematician's user avatar
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 ...
Sky's user avatar
  • 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$ ...
Notamathematician's user avatar
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\...
Notamathematician's user avatar
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 ...
Notamathematician's user avatar
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$ ...
Dattier's user avatar
  • 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 $...
Notamathematician's user avatar
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, $\...
Notamathematician's user avatar
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 ...
Notamathematician's user avatar
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 ...
Turbo's user avatar
  • 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 ...
Gerhard Paseman's user avatar
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, ...
Gerhard Paseman's user avatar
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:...
Augusto Santi's user avatar
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=(...
Augusto Santi's user avatar
-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[...
Sylvain JULIEN's user avatar
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 (...
Consider Non-Trivial Cases's user avatar
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}\ \ \...
Zhi-Wei Sun's user avatar
  • 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 $$\...
Turbo's user avatar
  • 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^{...
MC From Scratch's user avatar
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 ...
Nell's user avatar
  • 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 ...
Turbo's user avatar
  • 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 $...
Zhi-Wei Sun's user avatar
  • 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. ...
Zhi-Wei Sun's user avatar
  • 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 ...
Zhi-Wei Sun's user avatar
  • 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. ...
Zhi-Wei Sun's user avatar
  • 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 ...
apple's user avatar
  • 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 ...
Stoyan Apostolov's user avatar
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 ...
Nilotpal Kanti Sinha's user avatar
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} $...
nahila's user avatar
  • 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 ...
Zhi-Wei Sun's user avatar
  • 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 ...
Gerhard Paseman's user avatar
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 ...
Gerhard Paseman's user avatar
3 votes
3 answers
389 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 ...
d.y's user avatar
  • 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 ...
T. Amdeberhan's user avatar
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$....
T. Amdeberhan's user avatar
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)\ \...
Włodzimierz Holsztyński's user avatar
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$ ...
Gerhard Paseman's user avatar
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 ...
Nilotpal Kanti Sinha's user avatar
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 ...
Ramez Hindi's user avatar
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$....
Robert's user avatar
  • 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 $...
user avatar
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 ...
David Handelman's user avatar