How many 𝑛-digit integers have the property that the block of its first 𝑘 digits is a prime or divisible by 𝑘 for all 1 ≤ 𝑘 ≤ 𝑛?

Question

Are there infinitely many integers with the property that the block of its first 𝑘 digits (for all 𝑘, 1 ≤ 𝑘 ≤ 𝑛, where 𝑛 is the number of its digits) is either a prime number or is divisible by 𝑘?

An example of such a number with nine digits is 149,251,283.

If not, what is the largest number with this property?

Answer 1

As I commented already, I have a heuristic argument that

there is some largest number that satisfies the condition

because

for a length-k number, both the probability of being a multiple of k and being prime converges to zero as k increases.

Based on this belief, I quickly coded a program in Factor:

: good-number? ( k n -- ? )
  [ swap mod 0 = ] [ nip prime? ] 2bi or ;

: next-numbers ( k seq -- k+1 seq' )
  [ 1 + ] [ [ 10 * 10 <iota> [ + ] with map ] map concat ] bi*
  [ drop ] [ [ good-number? ] with filter ] 2bi ;

1 9 [1,b] [ next-numbers [ f ] when-empty ] follow

It took a few minutes to run in the GUI interpreter.

It internally uses Miller-Rabin probabilistic primality test, but two runs gave equal results, so I think the output is correct.

The number of n-digit numbers for each n was as follows:

 n          1     2     3     4     5      6      7      8      9     10
 count      9    66   320  1063  3141   7708  14885  25994  41508  57500

 n         11    12    13    14    15     16     17     18     19     20
 count  74514 87867 92237 97764 87821  74203  60737  47573  34498  20443

 n         21    22    23    24    25     26     27     28     29     30
 count  13593  7599  4775  2557  1524    821    468    212     94     35

 n         31    32    33    34    35
 count     18    10     7     2     0

and the largest number was:

5011561981801201672032001313475247, a 34-digit number. The other 34-digit number was 1860544080133200006094325972409613.