24
$\begingroup$

As we approach the end of the year, I thought about the appearance of primes in calendar dates as a recreational problem. Consider the number formed by concatenating the digits of a date in the form YYYYMMDD. For example 31-Dec-2019 will be written as $20191231$.

I was investigating if the number YYYYMMDD is prime. I checked for the next hundred thousand years and found that each year has between a minimum of $1$ for the year $5771237$ and a maximum of $37$ primes for the year $450060$. I could not yet find a single year which did not have a prime.

Conjecture: There is at least one prime every year.

Update: The year $27789755$ is the smallest year which has no prime.

What is the smallest counter example?

Also $37$ primes occurring in the year $450060$ because it implies that the interval $(4500600001, 4500601231)$ contains at least $37$ primes. Upon checking, it turns out this interval contains $77$ primes which is quite a dense for a short interval between two large numbers.

$\endgroup$
9
  • 5
    $\begingroup$ If you checked $YYYY$ for $0000$ through $9999$ you have shown that every year (if you truncate to the last four digits to fit $YYYYMMDD$) will have a prime. The proofs in the answers involve years that have more than four digits and have more digits $Y$ than you have specified. I don't say this as a criticism, but as a point that exactly how you ask the question can change the answer. $\endgroup$ – Ross Millikan Dec 27 '19 at 5:46
  • 3
    $\begingroup$ Heuristically we expect failures to occur starting roughly around years with value $e^{365} / 10^5 \approx 10^{154}$. $\endgroup$ – Travis Willse Dec 27 '19 at 6:05
  • 3
    $\begingroup$ @TravisWillse Got it! The year $27789755$ is the smallest year which has no prime. $\endgroup$ – NiloS Dec 27 '19 at 8:52
  • 3
    $\begingroup$ The next year with no primes is actually $13446204$. It happens that $134462040931$ is prime, but there is no 31st of September, of course. I note also that the year $450060$ has only $35$ primes, although $4500600431$ and $4500600631$ are both prime. Did you test the days of the month precisely? $\endgroup$ – nickgard Dec 27 '19 at 14:09
  • 2
    $\begingroup$ I should be more careful writing right before bed: Heuristically we expect failure to occur $\color{red}{\textrm{with characteristic probability} \frac{1}{e}}$ around years with value $e^{365} / 10^\color{red}{4} \approx 10^{\color{red}{155}}$. $\endgroup$ – Travis Willse Dec 27 '19 at 14:42
18
$\begingroup$

It is false, as you can construct sequences of composite numbers of arbitrary length $n$, e.g., $$(n+1)! + 2, \ldots, (n + 1)! + (n + 1) :$$ Pick such a sequence of length at least $19999$, so that it contains a subsequence of consecutive numbers ending in $0000, \ldots, 9999$. Then, the first number in that subsequence is $10\,000 \cdot y$ for some integer $y$, and all the numbers given by date strings from the year $y$ are composite.

$\endgroup$
18
$\begingroup$

Your conjecture is false.

Let $S=\left\{s_1,s_2,\ldots,s_{366}\right\}$ be the set of all numbers of the form MMDD, including $229$. We can restate your problem in the following marginally weaker form (it's weaker since not all years are leap years):

For every $k$, at least one of the numbers $$10000k+s$$ for $s\in S$ is a prime number.

However, this can easily be proven false. If we take $p_1,p_2,\ldots,p_{366}$ to be $366$ distinct prime numbers, different from $2$ and $5$, by the Chinese Remainder Theorem, there exists a $Y$ such that $$Y\equiv-s_1\cdot10000^{-1}\pmod{p_1}$$ $$Y\equiv-s_2\cdot10000^{-1}\pmod{p_2}$$ $$\vdots$$ $$Y\equiv-s_{366}\cdot10000^{-1}\pmod{p_{366}}$$ For this year $Y$, every single number $10000Y+s_i$ that we can generate will be divisible by the corresponding $p_i$ (while at the same time being much bigger than it), meaning that this year will have no primes.


Here's an alternate proof, much more technical, but much more faster. If every year had a prime, then $\pi(n)\in O(n)$, which is false by the Prime Number Theorem.

$\endgroup$
6
  • 7
    $\begingroup$ This is nice. An alternative might be to check the year $Y=1231!$ for then $MMDD$ will alwyas be a non-trivial factor of $Y$. $\endgroup$ – Jyrki Lahtonen Dec 27 '19 at 5:31
  • $\begingroup$ This looks similar to Erdos's method of covering systems for generating prime-free sequences. $\endgroup$ – Conifold Dec 27 '19 at 6:15
  • 1
    $\begingroup$ @NilotpalKantiSinha Jyrki’s method is pretty much what Travis Willse did. I suggest you give the accepted answer to him. $\endgroup$ – URL Dec 27 '19 at 6:56
  • 2
    $\begingroup$ If we're going to use $1231!$, we can also just multiply the largest prime powers contained there is, thus $2^{10}×3^6×5^4×7^3×11^2×13^2×$(squares of more primes up to $31$)$×37×$(remaining primes up to $1231$). $\endgroup$ – Oscar Lanzi Dec 28 '19 at 1:03
  • 2
    $\begingroup$ @OscarLanzi For that matter by the same reasoning we can just take the $\textrm{lcm}$ of the smallest prime factors of $101, \ldots, 131, 201, \ldots ,1231$. A quick script finds this number to have just $168$ digits, short enough to write down, which isn't bad for a cheap computation---10195786957875821444345027559223862895695570587202703712 \\ \qquad 45663038946624297463506225005754546690502456396108946978 \\ \qquad\qquad 43996095129242049481585843767583543973383881510424445610$$---but which is still far short of the apparently optimal $8$-digit solutions. $\endgroup$ – Travis Willse Dec 28 '19 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.