Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with nt.number-theory
Search options answers only
not deleted
user 7076
Prime numbers, diophantine equations, diophantine approximations, analytic or algebraic number theory, arithmetic geometry, Galois theory, transcendental number theory, continued fractions
30
votes
Proof for new deterministic primality test
The claim does not hold. A counterexample is given by $n=14$, $p=134123250258009499$ and correspondingly
$$N = 2197475332227227631617 = 193 \cdot 12289 \cdot 926510094425921.$$
It can be easily verifi …
- 29.5k
29
votes
Harmonic sums and elementary number theory
Graham (1963) proved that any integer $n>77$ can be represented as
$$ n = a_1 + \dots + a_m,$$
where $a_i$ are distinct positive integers with
$$\frac{1}{a_1} + \dots + \frac{1}{a_m} = 1.$$
Hence, a …
- 29.5k
24
votes
When do binomial coefficients sum to a power of 2?
I doubt this problem has an easy solution. It is clear how it was approached for small fixed $N$. Below I show how it can be addressed for the case of fixed odd $n>1$.
When $n>1$ is odd, $S(N,n)$ as a …
- 29.5k
24
votes
Accepted
Simple recurrence that fails to be integer for the first time at the 44th term
Copying my explanation from https://mathoverflow.net/a/217894/25028
The recurrence formula can be rewritten as
$$a_2=2,\qquad a_{n+1}=\frac{a_n\cdot (a_n+n-1)}n,\quad n\geq 2,$$
which somewhat justif …
- 29.5k
23
votes
$3^n - 2^m = \pm 41$ is not possible. How to prove it?
The congruence $3^n - 2^m \equiv 41\pmod{60}$ has no solutions.
The congruence $3^n - 2^m \equiv -41\pmod{72}$ has no solutions.
- 29.5k
23
votes
Accepted
Are there infinitely many positive integer solutions to $(3+3k+l)^2=m\,(k\,l-k^3-1)$?
It does have infinitely many positive solutions. Here is just one such series.
Consider the following recurrence sequence:
$$u_0=1,\ u_1=2,\ u_{n+1} = 23 u_n - u_{n-1} - 4\qquad (n\geq 1).$$
Let $t,k$ …
- 29.5k
20
votes
Accepted
Dividing squares by sums
First, notice that such $a$, $b$, $c$ must be pairwise coprime (e.g., if prime $p\mid \gcd(a,b)$, then $(a+b)\mid c^2$ implies $p\mid c$, a contradiction to $\gcd(a,b,c)=1$).
As divisors of pairwise c …
- 29.5k
19
votes
Accepted
Are there infinitely many natural numbers not covered by one of these 7 polynomials?
Notice that
$$30\cdot f_1(n_1,m_1) = (30\cdot m_1+23)\cdot (30\cdot n_1+7) - 11\\
30\cdot f_2(n_2,m_2) = (30\cdot m_2+17)\cdot (30\cdot n_2+13) - 11\\
30\cdot f_3(n_3,m_3) = (30\cdot m_3+23)\cdot (30\ …
- 29.5k
17
votes
Accepted
what is the status of this problem? an equivalent formulation?
In a recent paper A set of 12 numbers is not determined by its set of 4-sums (in Russian), Isomurodov and Kokhas identify an error in the argument of Ewell (1968) and present two distinct sets of 12 i …
- 29.5k
17
votes
Accepted
2-adic valuation of a certain binomial sum
First we notice that
\begin{split}
a_n & = n \int_0^1 x^n (1+x)^{n-1}{\rm d}x \\
& = n \int_0^1 (1-x)^n (2-x)^{n-1}{\rm d}x \\
& = n\sum_{k=0}^{n-1} \binom{n-1}{k}2^k (-1)^{n-1-k} \int_0^1 (1-x)^n x^ …
- 29.5k
17
votes
When do binomial coefficients sum to a power of 2?
This is a follow-up to John's answer.
Here is the questionable "theorem" from the 2nd (2013) edition of Erickson's book (thanks @spin for the pointer), which in the 1st (1996) edition was numbered as …
- 29.5k
16
votes
Accepted
In search of a combinatorial reasoning for a vanishing sum
For fixed $s,j>0$, $\sum_{\mathcal{A}_{j,s}}\binom{s}{n_1,\dots,n_j}$ enumerates the compositions of $j$ into $s$ positive parts by ordering the corresponding partitions. That is, we have
$$\sum_{\mat …
- 29.5k
16
votes
Accepted
The GCD-matrix: generalizing a result of Smith?
For Pell numbers, the answer appears to be
$$\det\left[\gcd(P_i,P_j)\right]_{i,j=1}^n = \prod_{k=1}^n \sum_{d|k} \mu(\frac{k}{d})\cdot P_d,$$
i.e. the product of first $n$ terms of the Moebius transfo …
- 29.5k
14
votes
Examples of integer sequences coincidences
Just another instance of the (second) Strong Law of Small Numbers:
We have A157656(n) = A059100(n-1) for all known terms (i.e., $n\leq 6$), but it's also known that A157656(29) > A059100(28). So, the …
14
votes
Accepted
$2$-adic valuations: a tale of two $q$-series
First notice that
$$\frac{1+q^n}{1-q^n} = 1 + 2\frac{q^n}{1-q^n}.$$
Computing modulo $8$, we have
$$\left(\frac{1+q^n}{1-q^n}\right)^2 \equiv 1 + 4\frac{q^n}{1-q^{2n}}\pmod8.$$
Correspondingly,
$$\pro …
- 29.5k
14
votes
Accepted
Squares in the set $\{\sum_{j=1}^m j^2: m\in\mathbb{N}\}$
We have $\sum_{j=1}^m j^2 = \frac{m(m+1)(2m+1)}6$. Hence, the question reduces to finding integral points on the elliptic curve:
$$y^2 = \frac{x(x+1)(2x+1)}6.$$
Turning it to Weierstrass equation with …
- 29.5k
14
votes
Accepted
When is $\mathrm{gcd}(k,p^k-1)=1$ true?
It is easier to describe non-good (bad) numbers with respect to a given prime $p$. For each such number $k$, there exists a prime $q$ such that $q\mid k$ and $q\mid (p^k - 1)$. It follows that $k$ is …
- 29.5k
13
votes
Accepted
Integers $b$ such that $n \nmid (b^n-1)$ for $n>1$
$b=2$ is the only almost 2-like number. Indeed, if $n\mid (b^n-1)$ and $p$ is a prime divisor of $(b^n-1)/n$, then $np\mid (b^{np}-1)$. That is, existence of one $n>1$ dividing $b^n-1$ implies existen …
- 29.5k
13
votes
Accepted
When is the number of areas obtained by cutting a circle with $n$ chords a power of $2$?
Denoting $k:=2^{\lfloor m/2\rfloor}$, we get two cases to consider:
$k^2 = f(n)$ and $2k^2 = f(n)$, or making the coefficients integer:
$$(12k)^2 = 144f(n)\qquad\text{and}\qquad (12k)^2 = 72f(n).$$
Th …
- 29.5k
12
votes
Is $441$ the only square of the form $\frac{397\cdot 10^n-1}{9}$?
If $\frac{397\cdot 10^n - 1}9$ is a square then so is $397\cdot 10^n - 1$. Let $y^2=397\cdot 10^n - 1$. Denoting $x:=10^{\lfloor n/3\rfloor}$, we get that
$$y^2 = 397\cdot 10^r\cdot x^3 - 1$$
or
$$(39 …
- 29.5k
10
votes
Primality test for numbers of the form $\frac{a^p-1}{a-1}$?
The test fails already for $p=3$ and $a=7$, claiming that $57=3\cdot 19$ is prime.
ADDED. And new test fails for $a=10$ and $p=5$.
ADDED#2. And the test in EDIT 2 fails for $a=52$ and $p=3$.
- 29.5k
10
votes
Accepted
Ordinary partitions vs partitions into odd parts
The g.f. for the right-hand is
$$e^{2x}\cdot e^{2x^2} \cdots = e^{2\frac{x}{1-x}}.$$
For the left-hand side, additionally introducing variable $y$ to account for partition length, we get
$$\sum_{n\ge …
- 29.5k
9
votes
Does $a_0=6$, $a_{n+1} = (a_n-1)\cdot a_n\cdot (a_n+1)$ define a square-free sequence?
The question is equivalent to asking whether $b(n):=\frac{a(n)}{a(n-1)}$ are squarefree. The sequence $b(n)$ is listed in OEIS A231831 and satisfies the recurrence $b(n+1) = b(n)^3 + b(n)^2 - 1$ with …
- 29.5k
9
votes
$23005\cdot (2^n-1)\cdot 2^n +1=p^2$
Multiplying the equation by $2^n$ and denoting $X:=2^n$ and $Y:=p2^{\lfloor n/2\rfloor}$, we obtain two elliptic curves (depending on the parity of $n$):
$$(23005(X-1)X+1)X=Y^2,$$
$$(23005(X-1)X+1)X=2 …
- 29.5k
9
votes
A Collatz-like function that bifurcates on primes
Let us use a rough estimate for the probability of a large integer $n$ being prime as $\frac{1}{\ln n}$ (as suggested by PNT). Then the expectation of $\ln f(n)$ can be estimated as
$$\frac{1}{\ln n}\ …
- 29.5k
8
votes
Accepted
Is the number of solutions of $\phi(x)=n!$ bounded? If yes, what is its bound?
UPD. Bound simplified.
Here is a constructive bound for the number of solutions to $\phi(x)=m$.
Let $\varphi(a) = m$. If $p^k\mid a$ for some $k\geq 1$, then $p^{k-1}(p-1)\mid m$, and thus $k\leq 1+\f …
- 29.5k
8
votes
Partitioning $2p$, subject to a divisibility condition.
It is possible. Take $p=61$ and $t_1=2$, $t_{120}=1$. Then $l=113$ and $1^{t_1}\cdot t_1!\cdot 120^{t_{120}}\cdot t_{120}!=240$ divides $(2p-l)!=9!=362880$.
Another example: $p=673$, $t_1=t_{672}=2$. …
- 29.5k
8
votes
Accepted
Modular arithmetic and elementary symmetric functions
It follows that $e_k(n) = \begin{bmatrix} n+1\\ n-k+1\end{bmatrix}$, i.e., unsigned Stirling numbers of first kind.
Now, let
$$f_n(x) := \sum_{k\geq 0} e_k(n) x^k = (1+x)(1+2x)\cdots (1+nx).$$
Then
$ …
- 29.5k
8
votes
Primality test for numbers of the form $4k+3$
In other words, $z^n \equiv \bar{z}\pmod{n}$ or $z^{n+1} \equiv z\bar{z}\pmod{n}$. That splits into two conditions:
$$\begin{cases}
\Im z^{n+1}\equiv 0\pmod{n}, \\
(c^2+1)^{n}\equiv c^2+1\pmod{n}.
\en …
- 29.5k
8
votes
Elementary divisibility problem
Zsigmondy theorem states that for any $p>1$, $a^p+b^p$ has a primitive prime factor, except when $\{a,b\}=\{1,2\}$. Such prime does not divide $a+b$. Hence, $a^p+b^p$ cannot divide $(a+b)^p$ unless it …
- 29.5k
8
votes
Accepted
Conjecture on palindromic numbers
The conjecture is true.
Let $b=a(n)=2^n+1$.
First, notice that the number in question is
$$N=(b^c-1)\frac{b^{m_1}+1}2\cdots \frac{b^{m_n}+1}2 = \frac{b^c-1}{b-1}(b^{m_1}+1)\cdots (b^{m_n}+1).$$
Sec …
- 29.5k
8
votes
Centered-hexagonal triangular squares
The question is equivalent to the system of quadratic Diophantine equations:
$$8 n^2 = m'^2 - 1$$
$$4n^2 = 3p'^2 + 1$$
where $m'=2m+1$ and $p'=2p+1$. How to solve such systems is described in my paper …
- 29.5k
8
votes
Testing whether an integer is the sum of two squares
The question is equivalent to testing whether -1 is a square modulo n. This corresponds to the quadratic residuosity problem which is supposedly computationally hard:
http://en.wikipedia.org/wiki/Qua …
- 29.5k
8
votes
Accepted
A moment sequence and Motzkin numbers. Modular coincidence?
Let's start with $b_n$. Since Catalan number $C_k$ is odd iff $k=2^m-1$, from Lucas theorem it follows that
$$b_n=\sum_{k=0}^n \binom{n}{2k}C_k \equiv\sum_{m\geq 0}\binom{n}{2(2^m-1)}\equiv 1+\nu_2(\l …
- 29.5k
8
votes
Accepted
Is Somos-8 $\mod 2$ periodic?
I confirm the observation of @მამუკაჯიბლაძე that $\nu_2(s_{103})=-1$. That is, $s_n\bmod 2$ is not well-defined at first place, which invalidates the question.
Moreover, for $n\geq 133$, $\nu_2(s_n)$ …
- 29.5k
8
votes
Reversing the CRT: Is $5$ tough?
The system of congruences in question is equivalent to $2^{pq}\equiv 2x\pmod{pq}$, i.e., the question is whether there exists an odd semiprime solution $n$ to $2^n\equiv c\pmod{n}$ (where $c=2x$).
Yo …
- 29.5k
8
votes
Accepted
Set partitions and permanents
Let me outline an approach for computing permanents in these conjectures. For the sake of concreteness, I will prove Conjecture 1 for an odd $n$. The matrix here is the sum of the following two 0-1 ma …
- 29.5k
8
votes
Accepted
A simple looking problem in partitions that became increasingly complex
I've got the following counts (which agrees with Brendan's):
1: 1
2: 3
3: 10
4: 55
5: 196
6: 2730
7: 10032
8: 108999
9: 973258
10: 20780331
11: 79309308
12: 2614200602
13: 100733 …
- 29.5k
8
votes
Is $-\det\big[\big(\frac{i^2+j^2}p\big)\big]_{1\le i,j\le (p-1)/2}$ always a square for each...
This is not an answer, but a reduction to supposedly simpler problem. (edited with more details)
Using quadratic Gauss sums, we can express Legendre symbol $\left(\frac{i^2+j^2}p\right)$
as
\begin{sp …
- 29.5k
8
votes
Accepted
Is there a similar formula like Ramanunjan's Eisenstein series identity for $\sum_{k=1}^{n-1...
Numerical experiments suggest that
$$A_2(n) := \sum_{k=1}^{n-1} k^2\sigma(k)\sigma(n-k) = \frac{n^2}{8}\sigma_3(n) - \frac{4n^3-n^2}{24}\sigma(n).$$
PS. In fact, it directly follows from the quoted To …
- 29.5k
7
votes
Reference request: Diophantine equations
E.g.
Number Theory: Volume I: Tools and Diophantine Equations, Graduate Texts in Mathematics 239, https://doi.org/10.1007/978-0-387-49923-9; and
Number Theory: Volume II: Analytic and Modern Tools, G …
- 29.5k
7
votes
Accepted
An identity for product of central binomials
We have
$$\prod_{j=1}^n \binom{2j}{j} = \frac{2!4!\cdots (2n)!}{(1!2!\cdots n!)^2}$$
and
$$\prod_{j=1}^n 2\binom{n+j}{2j} = 2^n\frac{(n+1)!(n+2)!\cdots (2n)!}{(2!4!\cdots (2n)!)\cdot (0!1!\cdots (n-1) …
- 29.5k
7
votes
Accepted
Minimal $n$ such that $(a-1)^m | a^n - 1$ for a given $a,m > 1$
Lifting The Exponent Lemma is helpful here.
First notice that $(a-1)^m\mid a^n-1$ is equivalent to $\nu_p(a^n-1)\geq m\nu_p(a-1)$ for every prime $p\mid a-1$.
If $a$ is even, then by LTE for any pri …
- 29.5k
7
votes
Chebyshev polynomials of the first kind and primality testing
I do not share excitement about this test and believe it admits false positives (i.e., pseudoprimes). Here are some supporting arguments.
Assuming that $n\equiv 2\text{ or }3\pmod{5}$, we will have $r …
- 29.5k
7
votes
Accepted
Reduced resultants and Bezout's identity
First off, it can be seen that the reduced resultant must divide $c$. Indeed, if $u_1(x)f(x)+v_1(x)g(x)=c$ and $u_2(x)f(x)+v_2(x)g(x)=d$, then from the Bezout identity for integers $c,d$, we can const …
- 29.5k
7
votes
Accepted
Conjectured primality test for specific class of $N=4kp^n+1$
The "if and only if" statement fails for
$$[p,n,k,a] \in \{ [3, 4, 1, 100], [3, 4, 1, 225], [3, 6, 13, 2901] \}$$ and many others. In these cases, $N$ is not prime, but the congruence $S_{n-2}\equiv …
- 29.5k
7
votes
For which $n$ is $\sum_{k=1}^n 1 / \varphi(k)$ an integer?
Here is some computational evidence that $n\in\{1,2,4\}$ are the only $n$ that deliver an integer sum.
For an odd prime $p$, let $a_p < b_p$ denote two smallest even positive integers such that $a_pp+ …
- 29.5k
7
votes
Accepted
Modulo $3$ calculations for a binomial-sum sequence
The answer is Yes.
The generating function for $t_n$ is
$$\sum_{n\geq 0} t_n x^n = \frac14\big(\frac{1+x}{\sqrt{1-6x+x^2}}-1\big).$$
Correspondingly,
$$\sum_{n\geq 0} t_n x^n \equiv \frac{1+x}{\sqrt{1 …
- 29.5k
7
votes
Accepted
Small covering of divisors
UPDATED
We can simply take
$$B = \{1\} \cup \{ d\in D_n\ :\ d > n^{1/2} \}.$$
Then for any $d\in D_n$:
if $d\leq n^{1/2}$, we take $(a,b)=(d,1)$;
if $d>n^{1/2}$, we take $(a,b)=(1,d)$.
Then
$$\sum_{ …
- 29.5k
7
votes
Attempt at applying linear programming to the partial sums of the Möbius inverse of the Harm...
Here is a proof of Conjecture 2.
First, we have
\begin{split}
\sum_{k=1}^n M(n,k) &= \sum_{k=1}^n \sum_{m=k}^n \sum_{d|\gcd(m,k)} d\cdot\mu(d) \\
&= \sum_{m=1}^n \sum_{k=1}^m \sum_{d|\gcd(m,k)} d\cdo …
- 29.5k