5
$\begingroup$

  • i) Find, if it exists, a prime P such that the number of 1's used to write all the primes from 2 to P is precisely P.

  • ii) Are there infinitely many such P? If not, find them all.

These questions arose during discussions at the 2023 Soacha, Colombia Math Circle.

Here is a related question.

Improve this question
$\endgroup$
6
  • $\begingroup$ Does this have any practical applications? $\endgroup$
    – web adventurer
    Aug 28 at 5:14
  • 1
    $\begingroup$ The 'number of 1's used to write' a number is just the number of occurences of the digit 1? $\endgroup$
    – quarague
    Aug 28 at 9:13
  • 1
    $\begingroup$ The number of 1's required is the following sequence in the oeis. By 10^14 still far behind! $\endgroup$
    – Freddy Barrera
    Aug 28 at 15:34
  • 1
    $\begingroup$ Please clarify what exactly you mean by the number of 1s required to write a number n. $\endgroup$
    – Rosie F
    Aug 29 at 9:36
  • $\begingroup$ @RosieF In writing the numbers from 1 to 100, the total number of 1's used is 21. Verify! $\endgroup$
    – Bernardo Recamán Santos
    Aug 29 at 12:57

2 Answers 2

Reset to default
3
+200
$\begingroup$

The prime-counting function, denoted by $\pi(x)$, counts the number of prime numbers less than or equal to $x$. It is closely approximated by $\frac{x}{\ln{x}}$. If we take $x=10^n$, we know that all primes in this range have at most $n$ digits. We can therefore estimate the total number of digits to be $d\approx n\times\frac{10^n}{\ln{10^n}}$. Then we take some prime $p\approx 10^n$ and find an approximate value for $\frac{d}{p}$:

$\frac{d}{p}\approx\frac{n}{\ln{10^n}}\approx0.4343$

As this value is constant, the implication is:

The total number of digits used to write all primes from $2$ to $p$ is less than $\frac{p}{2}$ for sufficiently large primes. The number of 1's used to write these primes is approximately one tenth of that.
There does not exist a prime $p$ for which this number is precisely $p$.

Data from the first 50 million primes, up to 982,451,653.

enter image description here

enter image description here

Improve this answer
$\endgroup$
5
  • $\begingroup$ This answer draws conclusion based on behavior at infinite - for big numbers - and missing terms as "probably" in it. For a formal proof, I think one has to prove how big has to be $p$ to consider the digit count approximation to have an error such that that error prevent the digit counting function to diverge too much from its value at infinite and reach values equal to $p$. Thus I am not sure that would prove there does not exist primes with such property but a finite amount...(cont) $\endgroup$
    – 10010100102ohno
    Sep 6 at 8:54
  • $\begingroup$ ...Also one has to prove that primes and their digits are acting like random numbers. digits are not. (ie. having primes with a lot of 1s at large number is likely as having a prime in any other allowed form). The fair conclusion should be "Probably, there does not exist a prime with such property, and hardly an infinite amount." $\endgroup$
    – 10010100102ohno
    Sep 6 at 8:54
  • $\begingroup$ @10010100102ohno A formal proof is not required here. Also, the prime counting function is well studied. An upper bound for the digit count comes directly from $\pi(x)$. The total digit count remains below $0.5x$, so the distribution of digits is irrelevant. $\endgroup$
    – Daniel Mathias
    Sep 6 at 21:40
  • $\begingroup$ Got it, I misunderstood your answer because the word "approximation". It's clear to me that if we speak of upper bounds your answer works great! (however $x/ln(x)$ is a lower bound for counting primes, so the sequent operation it's not an upper bound to their digits). I found this site that suggests a simple upper bound that does not change the answer conclusions: $(x/ln x)(1 + 1.2762/ln x)$ when $x>598$ @Daniel Mathias $\endgroup$
    – 10010100102ohno
    Sep 7 at 8:48
  • $\begingroup$ @10010100102ohno (pedantic) An upper bound ... directly from $\pi(x)$, using the actual value, not the approximation. $\endgroup$
    – Daniel Mathias
    Sep 7 at 22:36
4
$\begingroup$

A partial answer with some observations about numerical behavior.

You can find the code to compute the numbers in this answer here.

  • First we want to define the ratio $R_N$ as the number of ones in primes until number $N$ and the number $N$. If $R_N=1$ and $N$ is prime than we found our solutions (some or all).
  • You can see from this OEIS sequence (thanks to @Freddy Barrera) that $R_{10^n}$ is decreasing for n>1. However the delta from $R_{10^(n+1)}$ and $R_{10^n}$ is also decreasing and at some point it can start increasing (or reach a plateau).

enter image description here

  • Plot of $R_N$:

! Plot of $R_N$ when N is prime, x axis is the i-th prime, up to the 10k ! enter image description here Minimas seem to occur at values just before power of 10, while maximas are around 2*power of 10

  • Conjecture 1: Base 10 is peculiar and maybe the point on which $R_N >= 1$ (if exists) is at very high value of N. It's time consuming computing primes greater than 10^14 (the value from OEIS) to see patterns. And maybe the bouncing behavior is less marked in other bases.

  • Conjecture 2: Lower numerical bases maybe give us a clearer $R_N$ pattern.

Let's work in base $2$, that is full of ones!

First we check if we have any solution:

Yes, 3 5 11 19 23 47 61 are, computed up to 10^7 .

Then we want to see if $R_N$ has some patterns:

Plot of $R_N$ when N is prime, x axis is the i-th prime, up to the 10k enter image description here Little bouncing, uh? Seems also to tend to a value... Let's see if 100k give us more clues: enter image description here Still a little bouncing. So, for the moment our best guess is that ${R_N}$ is approaching some value near 0.8

Let's compute $R_{10^n}$ in base $2$:

N ones R_N
10^1 8 0.8
10^2 87 0.87
10^3 889 0.889
10^4 8437 0.8437
10^5 82074 0.82074
10^6 809377 0.809377
10^7 7902408 0.7902408
10^8 78337542 0.78337542
10^9 778137796 0.778137796

Let's see if base $4$ has some similar behavior

Plot of $R_N$ when N is prime, x axis is the i-th prime, up to the 10k enter image description here Yes, it is bouncing and tending to some values...

${R_{10^n}}$ base 4:

10^1 3 0.3
10^2 31 0.31
10^3 252 0.252
10^4 2644 0.2644
10^5 25265 0.25265
10^6 217444 0.217444
10^7 2279625 0.2279625
10^8 22415398 0.22415398

Solutions in other bases:

Not found up to 10^7 and base from 3 to 62

My best guess (aka speculation without mathematical proof!):

Even in base $2$ that should be the base with the most number of ones (at least in any given random number) - both because the length of the numbers and the fact that numbers themselves are composed by only $0$s and $1$s - We observe a mostly decreasing trend in the long run, even if little bouncing, leaving me think that no more solution will be discovered after the first 7. In base $10$ this behavior could be even stronger due to the rarity of ones wrt base-2, so $R_N < 1$ for all N and no solution exists at all.

I leave for reference $R_{10^n}$ computed in bases from 3 to 62 pastebin

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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