0
$\begingroup$

Let f : N \ {0,1} --> N be a function defined by f(n) = lcm[1, 2, ..., n]:

(a) Prove that for all n, n >= 2, there exist n consecutive numbers for which f is constant (i.e. some numbers a, a + 1, ..., a + n - 1, such that f(a) = f(a + 1) = ... = f(a + n - 1)).

(b) Find the greatest number of elements of a set of consecutive integers on which f is strictly increasing, and determine all sets for which this maximum is realized.

$\endgroup$
1
  • 2
    $\begingroup$ So, what are your thoughts on the problem? What can you say about how it can happen that $f(n)=f(n+1)$, and how it can happen that $f(n)\ne f(n+1)$? $\endgroup$ Commented Feb 24, 2013 at 22:21

2 Answers 2

0
$\begingroup$

Hints: For the first question, consider consecutive numbers $k!+1$, $k!+2$, and so on up to $k!+k$.

For the second problem, note that we will have $f(n+1)\gt f(n)$ only when $n+1$ is a prime power, If you take $4$ consecutive numbers such that $f$ increases $3$ times, the fist will have to be even and the third must be a power of $2$. One of the two neighbours of that power of $2$ must be divisible by $3$, and therefore a power of $3$.

We can quickly find the examples $2,3,4,5$ and $6,7,8,9$. It can be shown that a power of $3$ is a neighbour of a power of $2$ only in the cases $2,3,4$ and $8,9$.

$\endgroup$
0
$\begingroup$

when is $\operatorname{lcm}(N,n) = N$ ? When $n|N$.

so we need to find $a$ in terms of $n$ such that $a,a+1,a+2,\ldots,a+n|\operatorname{lcm}([1\ldots a])$.

one useful property of the lcm of consecutive numbers is that $d < a$ implies $d | \operatorname{lcm}([1\ldots a])$.

Obviously $a+1 > a$ but suppose it was even, then $\frac{a+1}{2}<a$ and (supposing) $2^2 < a$ we get $a+1 | \operatorname{lcm}([1\ldots a])$.

We can choose $a \equiv 1 \pmod {i+1}$ for all $i$ by Sun Zi's theorem. Then we always have the integer $\frac{a+i}{i+1}$ dividing the lcm.

It remains to get each $(i+1)^2$ dividing the lcm, but for that it suffices to have $(n+1)^2 < a$, this can assumed from the construction of $a$.

$\endgroup$
2
  • $\begingroup$ this seems a bit involved, maybe there is an easier answer. $\endgroup$
    – user58512
    Commented Feb 24, 2013 at 22:21
  • $\begingroup$ So I guess this works for exactly the same reason as k!+i, but it more tricky because it gives a smaller a. $\endgroup$
    – user58512
    Commented Feb 25, 2013 at 12:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .