1
$\begingroup$

I find one of the suggested solution to this problem a little bit questionable:

“If N is divisible by 1, 2, 3,. . . M, then N must also be divisible by M + 1, M + 2, M + 3, . . . M + k for k is a positive integer.”

One of the suggested solution is:$$M=1+\prod_{p\leq k+1} p^{1+\lfloor \log_p (k+1)\rfloor}$$

This gives $M=37$ for $k=2$ and $M=1+8\cdot 9=73$ for $k=3$.

But the one who give this formula also claimed that this formula does not guarantee for the best value of M, it just give a value of M.

In lieu to this, I believe that this formula will fail at some k as k is considerably large. My question is what must be the code to be encoded in mathematica so that I'll be able to determine the smallest k it will fail by brute force. Manual computation is time consuming., I already tried up to k = 12... any help will be much appreciated!

$\endgroup$

closed as off-topic by MarcoB, b3m2a1, garej, Daniel Lichtblau, Young Sep 22 '17 at 14:53

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question cannot be answered without additional information. Questions on problems in code must describe the specific problem and include valid code to reproduce it. Any data used for programming examples should be embedded in the question or code to generate the (fake) data must be included." – MarcoB, b3m2a1, garej, Young
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What's the actual code you're working with? Having real, copyable code in your question increases the likelihood someone will take it upon themselves to write up an answer. One other thing, what do you mean the "best value of M"? $\endgroup$ – b3m2a1 Sep 21 '17 at 5:31
  • $\begingroup$ Is the formula for M, correct? For k=2, I get M = 37. $\endgroup$ – Anjan Kumar Sep 21 '17 at 5:38
  • $\begingroup$ aw sorry mistype.. you're correct it must be 37 then $\endgroup$ – rosa Sep 21 '17 at 5:49
  • $\begingroup$ @rosa Likewise for k=3, M is 1153. $\endgroup$ – Anjan Kumar Sep 21 '17 at 5:53
  • $\begingroup$ @b3m2a1 What it means is that for k = 2, M = 37 that is the LCM(1,2,3,4 ....37) = LCM(1,2,3,4,...38) = LCM (1,2,3,4, ...,39) for M + 1 and M + 2,,, based on the suggested formula it does not include M + 3 which is 40 but LCM(1,2,3,4....40) although it is also included in the set. the formula does not give the best value M .. but only gives M as suggested value. $\endgroup$ – rosa Sep 21 '17 at 5:53
1
$\begingroup$

So if I understand the question correctly you want to find the minimal M such that given k, this holds:

Equal@@Table[LCM@@Range[M+p], {p, 0, k-1}]

Or rather you want to find a way to know how far off your M is.

I can't provide you with a close-form solution for this. But I can show how drastically off that formula is. Here's a memoized recursive, unoptimized, clumsy, procedural search for M (but it took like 2 seconds to write, so there you are):

Clear[findM];
findM[1] = 5;
findM[k_] :=
 findM[k] =
  Block[{
    mTest = findM[k - 1],
    oldVal,
    newVal,
    hits = 1
    },
   oldVal = LCM @@ Range[mTest];
   While[hits < k + 1,
    If[oldVal === (newVal = LCM @@ Range[++mTest]),
     hits++,
     oldVal = newVal;
     hits = 1
     ]
    ];
   mTest - k
   ]

And here's that testing function:

mTest[m_, k_] :=
 Equal @@ Table[LCM @@ Range[m + p], {p, 0, k - 1}]

And finally here's the formula for M you had:

weirdM[k_] :=
 1 +
  Product[
   Power[p, 1 + Floor[Log[p, k + 1]]],
   {p, 2, k + 1}
   ]

Now let's compute differences between the found value and the weirdM value:

weirdM[#] - findM[#] & /@ Range[15]

{0, 24, 1134, 28769, 1036748, 50803112, 6502809512, 1580182732662, \
158018273279862, 19120211066879802, 2753310393630719802, \
465309456523591679708, 91200653478623969279708, \
20520147032690393087999114, 42025261122949925044223999114}

You can see weirdM blows up way faster than findM. And here's what the values should be, if I'm reading the question right:

findM /@ Range[15]

{5, 13, 19, 32, 53, 89, 89, 139, 139, 199, 199, 293, 293, 887, 887}

And just to check:

mTest[findM[#], #] & /@ Range[15]

{True, True, True, True, True, True, True, True, True, True, True, \
True, True, True, True}

So, in short, the formula fails to find the minimal such M by k=2 I think. And it fails ever more dramatically as k increases.

Do note, though, that this findM is mad slow, even with memoization. But I think you want a formula, not a procedure, anyway.

findM /@ Range[50] // AbsoluteTiming

{183.835, {5, 13, 19, 32, 53, 89, 89, 139, 139, 199, 199, 293, 293, 
  887, 887, 887, 887, 887, 887, 1129, 1129, 1331, 1331, 1331, 1331, 
  1331, 1331, 1331, 1331, 5591, 5591, 8467, 8467, 9551, 9551, 15683, 
  15683, 15683, 15683, 15683, 15683, 15683, 15683, 19609, 19609, 
  19609, 19609, 19609, 19609, 19609}}
$\endgroup$

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