I have the task of finding 5 consecutive integers of the form {x, x+1, x+2, x+3, x+4, x+5} where each number in the sequence is divisible by a square k greater than 1..

I tried to write a simple JAVA program to find a sequence of that form by checking if each number in the sequence = 0 mod k

But that can't be possible, how would I go about finding these numbers?

  • $\begingroup$ There can't be one $k$ which divides $x$ and $x+1$, other than $k=1$. So it has to be a different square for each element. $\endgroup$ – Thomas Andrews Mar 8 '17 at 19:48
  • 1
    $\begingroup$ Do you know the Chinese remainder theorem? Are you allowed to find any solution, or does it have to be the smallest? $\endgroup$ – Thomas Andrews Mar 8 '17 at 19:53
  • $\begingroup$ I can find any solution $\endgroup$ – Temirzhan Mar 8 '17 at 19:54
  • $\begingroup$ @ThomasAndrews Except that two of $x, \ldots, x+5$ may be divisible by $4$. $\endgroup$ – Robert Israel Mar 8 '17 at 19:58
  • 1
    $\begingroup$ You say 5 consecutive integers, but $x,x+1,\ldots,x+5$, is 6 consecutive integers. $\endgroup$ – B. Goddard Mar 8 '17 at 20:00

Chinese remainder theorem:

$$\begin{align}x&\equiv 0\pmod{4}\\ x&\equiv -1\pmod{9}\\ x&\equiv -2\pmod{25}\\ x&\equiv -3\pmod{49}\\ x&\equiv -5\pmod{121} \end{align}$$

That's gonna be ugly.

If you only need five, then you can ignore the last line and you get $$x\equiv 29348\pmod{4\cdot 9\cdot 24\cdot 49}.$$ Then $x,x+4$ are divisible by $4$, $x+1$ is divisible by $9$, $x+2$ is divisible by $25$, and $x+3$ is divisible by $49$.

  • $\begingroup$ Very mechanical, though, and since this implies an answer less than $4\cdot9\cdot25\cdot49\cdot121 = 5336100$, all of the calculations can be done straightforwardly using standard 32-bit integer arithmetic. $\endgroup$ – Steven Stadnicki Mar 8 '17 at 20:03
  • $\begingroup$ And it's even easier if the OP really mean $5$ consecutive, rather than six. $\endgroup$ – Thomas Andrews Mar 8 '17 at 20:08
  • $\begingroup$ Thomas what about a numver thats congruent to -4? you have 0, -1, -2, -3, -5 but you skip -4 $\endgroup$ – Temirzhan Mar 8 '17 at 20:13
  • $\begingroup$ If $x\equiv 0\pmod{4}$ then $x\equiv -4\pmod{4}$. @user203042 $\endgroup$ – Thomas Andrews Mar 8 '17 at 20:14
  • $\begingroup$ They don't have to be "in order." $\endgroup$ – Doug M Mar 8 '17 at 20:17

The formulation you give ($x,x+1,\ldots,x+5$) actually has $6$ consecutive values. The values for such $x$ below $100000$:

$$22020, 24647, 30923, 47672, 55447, 57120, 73447, 74848, 96675$$

Finding $5$ consecutive values is easier; the smallest such sequence is $844,845,846,847,848$, which are multiples of $4,169,9,121,16$ respectively.

  • $\begingroup$ Interesting. $844 \neq 29348(mod4⋅9⋅24⋅49)$ [sic] as stated in @ThomasAndrews post. $\endgroup$ – Χpẘ Mar 8 '17 at 20:57
  • $\begingroup$ This is the result of a straight search, so as you can see one of the squares involved is $13^2=169$ and the other factor squares are in a different order. $\endgroup$ – Joffan Mar 8 '17 at 20:57

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.