Erdős Problem #404

Erdős Problem 404: finite congruences and an infinite factorial sum

Statement and outcome

We prove an exact finite residue test, the equivalence between unbounded $f(a,p)$ and an infinite sequence starting at $a$, and the exact family $f(a,p)=v_p(a!)$ when $a\equiv-1\pmod p$. No pair with unbounded $f(a,p)$ is established here, and the general problem remains unresolved. Source: https://www.erdosproblems.com/404. These are elementary structural deductions, not a claimed resolution of the known difficult pair $(2,2)$.

A finite test for each valuation threshold

Thus failure of $1$ is a complete certificate that $f(a,p)<h$, not merely failure of a search with an arbitrary cutoff. Conversely a successful residue supplies a finite witnessing sum. Testing $h=1,2,\ldots$ determines $f(a,p)$ exactly if it is finite; the first failing test is $h=f(a,p)+1$. Nontermination alone would not prove infinity.

Unbounded finite cancellation is equivalent to infinite cancellation

Deleting the last bit of an admissible string leaves an admissible string at the previous level. Indeed every condition required there has $M_h\le N$, and $N!$ vanishes modulo $p^h$. Since each string has at most two extensions, there is an infinite branch: at each step choose a child having descendants at arbitrarily large levels, which exists by finite branching. This proves the compactness step explicitly.

The branch has infinitely many one-bits. Otherwise its eventually fixed positive integer sum would, by $3$, be divisible by every power of $p$, impossible. Enumerate its one-bit indices as $a=a_1<a_2<\cdots$. For each fixed $h$, all sufficiently long such prefixes contain every selected index below $M_h$, while each further selected factorial vanishes modulo $p^h$. Condition $3$ therefore makes all sufficiently long partial sums divisible by $p^h$. This is precisely the limit in $2$.

In particular the existence question about an infinite sequence is equivalent to asking whether some pair $(a,p)$ has $f(a,p)=\infty$. Choosing unrelated finite witnesses without the preceding compactness argument would not justify this equivalence.

An exact infinite family of finite values

Remaining gap

1) FORMAL RESTATEMENT

Fix an integer $a\ge 1$ and a prime $p$.

For a finite strictly increasing sequence of integers \[ a=a_1<a_2<\cdots<a_n, \] define the factorial sum \[ S:=a_1!+a_2!+\cdots+a_n!. \]

For each such pair $(a,p)$, define \[ f(a,p):=\sup\{k\ge 0:\ \exists\ n\ge 1,\ \exists\ a=a_1<\cdots<a_n\text{ with }p^k\mid S\}. \] (So $f(a,p)=0$ means no such sum is divisible by $p$; if arbitrarily large $k$ occur we interpret $f(a,p)=\infty$.)

The problem asks:

(A) For which $(a,p)$ is $f(a,p)$ finite (i.e. there is an upper bound on achievable $k$)? How does $f(a,p)$ behave?

(B) Does there exist a prime $p$ and an infinite sequence $a_1<a_2<\cdots$ such that if $m_k$ is the exact $p$-adic valuation \[ m_k:=v_p\left(\sum_{i\le k} a_i!\right), \] then $m_k\to\infty$ as $k\to\infty$?

Edge cases. If $a=p-1$ then $a!$ is not divisible by $p$ but all $m!$ for $m\ge p$ are divisible by $p$.

2) QUICK LITERATURE/CONTEXT CHECK

I only restate what is recorded in the problem statement.

The statement records: - Lin showed $f(2,2)\le 254$.

3) ATTACK PLAN

Proof-track (partial): - Establish elementary constraints on $p$-adic valuations of factorials and simple sums of factorials. - Identify pairs $(a,p)$ where $f(a,p)=0$ by a modulo $p$ obstruction. - Compute small examples for sanity.

Disproof-track: - Try to build explicit constructions forcing $v_p$ to grow (computational evidence only).

Chosen path: prove a few exact lemmas (including an explicit family with $f(a,p)=0$) and give brute-force lower bounds for small $(a,p)$.

4) WORK

PHASE 1 — FAST REALITY CHECK (computed)

For small $M$ I brute-forced over subsets of $\{a,a+1,\dots,M\}$ (always including $a$) to maximise $v_p\left(\sum i!\right)$. These computations give lower bounds on $f(a,p)$.

Examples (all exact within the stated search cutoff):

- For $(a,p)=(1,2)$, the maximum $v_2$ found up to $M=20$ is $0$ (subset $\{1\}$), suggesting $f(1,2)=0$. - For $(a,p)=(2,2)$, up to $M=18$ I found a subset $\{2,3,5,6,7,11,12,15,16,18\}$ with \[ v_2\left(\sum_{i\in S} i!\right)=17, \] so $f(2,2)\ge 17$. - For $(a,p)=(2,3)$, up to $M=20$ the best $v_3$ was $0$ (subset $\{2\}$), suggesting $f(2,3)=0$.

Lemma 1 (elementary lower bound for factorial valuations). For every prime $p$ and integer $m\ge 1$, \[ v_p(m!)\ge \lfloor\frac{m}{p}\rfloor. \] In particular, if $m\ge kp$ then $p^k\mid m!$.

Proof. Among the factors $1,2,\dots,m$ there are exactly $\lfloor m/p\rfloor$ multiples of $p$, and each contributes at least one factor of $p$ to the product $m!$. Therefore the total exponent of $p$ in $m!$ is at least $\lfloor m/p\rfloor$. The final statement follows because $\lfloor m/p\rfloor\ge k$ when $m\ge kp$. $\square$

Lemma 2 (a two-term valuation identity). For every integer $a\ge 1$, \[ a!+(a+1)! = a!(a+2). \] Consequently, for every prime $p$, \[ v_p\left(a!+(a+1)!\right)=v_p(a!)+v_p(a+2). \]

Proof. Factor out $a!$: \[ a!+(a+1)! = a! + (a+1)a! = a!(1+a+1)=a!(a+2). \] Taking $p$-adic valuations and using $v_p(xy)=v_p(x)+v_p(y)$ gives the valuation formula. $\square$

Lemma 3 (an explicit infinite family with $f(a,p)=0$). For every prime $p$, \[ f(p-1,p)=0. \] Equivalently, if $a=p-1$ then no sum $a_1!+\cdots+a_n!$ with $a_1=a$ is divisible by $p$.

Proof. Fix prime $p$ and set $a=p-1$. Any admissible sequence has $a_1=p-1$ and all other terms (if any) satisfy $a_i\ge p$. Therefore each $a_i!$ for $i\ge 2$ is divisible by $p$. Hence modulo $p$ we have \[ a_1!+a_2!+\cdots+a_n! \equiv (p-1)! \pmod p. \] But $(p-1)!$ is a product of integers all strictly less than $p$, so $p\nmid (p-1)!$. Thus the sum is nonzero mod $p$, so it is not divisible by $p$. Therefore no power $p^k$ with $k\ge 1$ divides the sum, i.e. $f(p-1,p)=0$. $\square$

Corollary 4. The case $(a,p)=(2,3)$ satisfies $f(2,3)=0$ (since $2=3-1$), consistent with the computation.

5) VERIFICATION

- Lemma 1: for $p=2$, $v_2(5!)=3\ge\lfloor 5/2\rfloor=2$; the inequality is weak but always correct. - Lemma 2: tested numerically for small $a$; the factorisation is exact. - Lemma 3: for $p=2$, $a=1$ gives sums always odd, so $f(1,2)=0$; for $p=3$, $a=2$ gives sums always $\equiv 2\pmod 3$, so $f(2,3)=0$.

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result obtained here. - Exact family with $f(p-1,p)=0$ for all primes $p$ (Lemma 3). - General tools: $v_p(m!)\ge\lfloor m/p\rfloor$ (Lemma 1) and the exact identity $v_p(a!+(a+1)!)=v_p(a!)+v_p(a+2)$ (Lemma 2). - Computational lower bounds: for example $f(2,2)\ge 17$ (from an explicit subset up to $18$).

(ii) Exact first gap. Determine for any fixed pair $(a,p)$ with $a\not\equiv -1\pmod p$ whether $f(a,p)$ is finite or infinite; in particular, exhibit any $(a,p)$ for which one can prove $f(a,p)=\infty$ (unbounded $p$-adic valuation) or prove a nontrivial finite upper bound.

(iii) Top 3 next moves (concrete targets). 1. Develop a systematic $p$-adic “greedy” algorithm to choose additional factorial terms to cancel the low-order $p$-adic digits of the partial sum and thereby increase $v_p$. 2. For specific small pairs (e.g. $(a,p)=(2,2)$), attempt to prove unboundedness by constructing an explicit infinite sequence $a_1<a_2<\cdots$ with $v_p$ of partial sums strictly increasing. 3. Conversely, seek rigid obstructions (e.g. working modulo $p^{k+1}$ once $a!$ has exact valuation $k$ and later factorials are all multiples of $p^{k+1}$) that would force $f(a,p)$ finite in certain regimes.

(iv) What a minimal counterexample would likely look like. A counterexample to the existence of any $(a,p)$ with $f(a,p)=\infty$ would be a proof that for every $a,p$ there exists a maximal $k$ such that $p^k\mid\sum a_i!$. Such a proof would likely show that once $v_p$ reaches a certain level, the residues contributed by the finitely many factorials with valuation exactly that level cannot be arranged to cancel modulo the next power.