Problems & Puzzles: Puzzles

Puzzle 1160 A Puzzle related to 2024 Emmanuel Vantieghem sent the following nice puzzle. It is easy to show that for every prime p there exists a number k such that k*p contains 2024 as a substring.Moreover, that k is <= 9992. But, if p is not prime, it is possible that a k bigger than 9992 is needed. An example is p = 119904, where k must be 16881. So, my next question is : "Is 16881 an upper bound for k ?"

---

From Jan 30 to Feb 02 contributions came from Giorgos Kalogeropoulos,Michael Branicky,

Paul Cleary, JM Rebert, Oscar Volpatti

 

***

Giorgos wrote:

The answer is no.

For p = 11625250 -> k = 17411

***

 Michael Branicky wrote

16881 is not an upper bound for k:

p =    1162525 requires k = 17411,

p =   11415525 requires k = 17731,

p =  108695795 requires k = 18621,

p = 1041666675 requires k = 19431.

However, k is bounded by 20240 for all p

Proof. For any p >= 1, pick t such that 10^t > p >= 10^{t-1}.

Then k = ceil(2024*10^t/p) has 2025*10^t > k*p >= 2024*10^t.

Therefore, k*p has 2024 as its first 4 digits.

The largest this k can be is ceil(2024*10^t/10^{t-1}) = 20240.

Given the bound's form, it is not unexpected that our records above

are proportionately closer and closer to powers of 10.

As a side note, prime p = 11538497 achieves the prime bound k  9992.

***

Paul Cleary wrote:

I Have found 2 more extensions to the upper bound, the first one occurred at p = 1162525 with a k of 17411, the next increase was at p =11415525 with a k of 17731.  I found no more increases of k with a p upto 60000000.

 

I am tending towards 17731 as the upper bound mainly because if we re-set the counter, the maximum k is 6746 for all p between 30000000 and 50000000 and likewise the maximum k is 4048 for all p between 50000000 and 6000000

...

Working on a hunch, I extended the range and working in steps of 25 was able to get a larger k value of 18462 and a p value of 108873375 where the resultant is 2010020249250. No further upper bound was found using the increments of 25 upto 240000000.  So there could be a larger k upper bound with a p value less than 240 million.

...

I managed to find a k value of 18462 with a p value of 108873375.

***

JM Rebert wrote:

I found:

9992 * 11538497 = 115292662024

 

16881 *   119904 =   2024099424

17411 *  1162525 =  20240722775

17731 * 11415525 = 202408673775

 

***

Oscar wrote:

there are composites p for which a number k bigger than 16881 is needed:
p k
1162525  17411
11415525  17731
113636375  17812
108695795  18621
1041666675  19431


It can be proven that no composite p requires a number k bigger than 20240.

***