# 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. – Bubbler Jan 19 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.) – Bubbler Jan 19 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. – quarague Jan 19 at 17:44
• @Bubbler: It's straightforward to solve by programming if there is in fact a largest number with that property. – Michael Seifert Jan 19 at 18:18
• Just primes: oeis.org/A024770. – Bernardo Recamán Santos Jan 19 at 22:31

## 1 Answer

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.