2
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ I initially parsed the sentence as "divisible by (k or a prime)" and was confused for a while. $\endgroup$ – Bubbler Jan 19 at 16:50
  • 3
    $\begingroup$ 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.) $\endgroup$ – Bubbler Jan 19 at 17:01
  • $\begingroup$ 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. $\endgroup$ – quarague Jan 19 at 17:44
  • $\begingroup$ @Bubbler: It's straightforward to solve by programming if there is in fact a largest number with that property. $\endgroup$ – Michael Seifert Jan 19 at 18:18
  • 2
    $\begingroup$ Just primes: oeis.org/A024770. $\endgroup$ – Bernardo Recamán Santos Jan 19 at 22:31
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.