2

On my spare time I was playing with prime numbers and I ended up with this prime:

Update : I wrote a small app so far it goes up to 567971319309729771210786213268422260969319129482217737847903312383286964865394128911072146362309663543273945114494702883183617651521339440145570920031781109691165102597686166105613682101202311051220252388622041905195316661081211759149538625353140728826530534941751633668018330987379383124615608109350154306331101861873143125711717826324448991141563962387814503222646171339212244414514122666961822271622033170516558160848580284227373013741242714693226093145723898217171297464894117132763023712555691594493972241981124520737210726224644435368513229226176343777366165441128286813963144106216517358022179411541839911735418028569681614330348360582931783391524186752014242126999966132848574636451203362912619510015152129256240206328233335794651471018341717451336997

by adding max 4 digits.

5794651471018341717451336997

The special thing about it is that I was able to generate it adding 1 or 2 digits to the left hand side and I am curious for how long this goes on. Perhaps someone smarter than me can find the answer. Currently all below numbers are primes:

7

97

997

6997

36997

336997

1336997

51336997

451336997

17451336997 (2 digits added)

717451336997

41717451336997 (2 digits added)

341717451336997

18341717451336997 (2 digits added)

101834171745133699 (2 digits added)

471018341717451336997 (2 digits added)

51471018341717451336997 (2 digits added)

4651471018341717451336997 (2 digits added)

94651471018341717451336997

5794651471018341717451336997 (2 digits added)

emperon
  • 131
  • @PeterForeman thanks for the comment. Do you think this yields any practical advantage in terms of prime number generation? – emperon Jun 13 '20 at 19:44
  • 1
    Unlikely given how small these primes are in comparison to those used nowadays. – Peter Foreman Jun 13 '20 at 19:46
  • You can continue that indefinitely, but where's the point? –  Jun 13 '20 at 19:58
  • @ProfessorVector I actually don't know. I personally find it interesting to be able to generate prime numbers deterministically even if it is a bit brute forcish. But maybe it's not special at all. – emperon Jun 13 '20 at 20:07
  • Can I summerize your question this way: Is it possible for every prime number except 2 and 5 to get an other prime number by prepending digits? – Paul Jun 13 '20 at 20:55
  • @Paul Let's say by prepending max 4 digits and only for above number. – emperon Jun 13 '20 at 21:03
  • I don't see any reason to think that this is possible. You have seen for yourself that the higher you go, the more digits you need to add. – TonyK Jun 13 '20 at 21:10
  • Yes it looks like. But maybe it is capped. – emperon Jun 13 '20 at 21:11

1 Answers1

2

There's nothing particularly surprising about this result.

Suppose you have an arbitrary number $ N $ coprime to $ 10 $ (only depends on the first digit of $ N $) and $ 10^k $ is the smallest power of $ 10 $ greater than $ N $. If you look at the arithmetic sequence

$$ N, N + 10^k, N + 2 \cdot 10^k, \ldots, N + i \cdot 10^k, \ldots $$

then the number of primes you expect to find up to $ i \leq M $, for example, would be approximately

$$ \sum_{i=0}^M \frac{1}{\log(N + i \cdot 10^k)} \geq \sum_{i = 1}^M \frac{1}{\log(i) + k \log (10)} \geq \frac{M}{\log M + k \log 10} $$

by the prime number theorem. You can make this precise using averages in the infinite limit using results about arithmetic progressions, so this is not even a heuristic argument; it can be made entirely formal at the expense of introducing some error terms. If you now pick $ M $ to be on the order of $ k \log 10 $, then you expect to find a prime in this sequence. If you recall that $ k $ is about $ \log_{10}(N) = \log N / \log 10 $, then you need to pick $ M \approx \log N $, and if you pick something like $ M = O((\log N)^{{1 + \varepsilon}}) $ then you will almost surely find a prime in this arithmetic progression when $ N $ gets large.

The upshot is that if you have a number like $ 94651471018341717451336997 $ ($ 26 $ digits, so its natural logarithm is about $ 60 $), you expect there to be some $ i \approx 60 $ such that the concatenation

$$ i94651471018341717451336997 $$

is prime, and indeed you find $ i = 57 $, very close to $ 60 $. You can build a similar sequence starting with any digit different from $ 0, 2 $ and $ 5 $.

If you want to add a maximum of $ 4 $ digits, then you can go up to about

$$ \exp(10^4) = 10^{10^4 / \log 10} \approx 10^{4343} $$

which I suspect is beyond the capabilities of your primality testing algorithm to handle.

Ege Erdil
  • 17,747