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?

Bubbler · Accepted Answer

As I commented already, I have a heuristic argument that

because

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:

and the largest number was:

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

One Answer

Add your own answers!

Ask a Question