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

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?

• I initially parsed the sentence as "divisible by (k or a prime)" and was confused for a while. Jan 19, 2021 at 16:50
• Also, it doesn't look so meaningful to try solving this by hand, and it looks straightforward to solve it by programming, so I don't see much puzzling value. (Compare it to the ant walk problem where hand optimization is feasible to some extent and programming is not that straightforward IMHO.) Jan 19, 2021 at 17:01
• This is a good question for the math SE but not really for puzzling. I also strongly suspect there are only finitely many such integers. Given such a number all its blocks of first $k$ digits are also of this type. This means if you know all such $n$ digits numbers you can find the $n+1$ digit ones by trying to extend the $n$ digits ones by one digit. Jan 19, 2021 at 17:44
• @Bubbler: It's straightforward to solve by programming if there is in fact a largest number with that property. Jan 19, 2021 at 18:18
• Just primes: oeis.org/A024770. Jan 19, 2021 at 22:31

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.