[seqfan] Re: Does the first part of this algorithm work only with the powers of 2?

[Elijah Beregovsky]

Hello, Ali!
The answer to your question is definitely yes.
As we’re dealing with multiples of m, it seems sensible to see what’s going on with the sequences modulo m, especially after the first rule stops working. After that point we just add consecutive natural numbers to whatever we had when the first rule broke (breaking point). So, actually we are interested in triangular numbers (increased by a fixed amount) modulo m. (mod 3) sequence of remainders of triangular numbers goes 0,1,0,0,1,0,0,1..., (mod 5) - 0,1,3,1,0,0,1,3,1,0,1,3..., (mod 6) - 0,1,3,0,4,3,3,4,0,3,1,0,0,1,3,0... So, it is periodic and not every remainder appears in the period. Thus, you can add some number to every term and get a sequence with no zeroes. That’s exactly what happens at the breaking point. And it always happens, as you run through all naturals (number of multiples of m), until you find one, that gives you a non-zero remainder sequence. On the other hand, when you take triangular numbers (mod 2^i) you get all possible remainders: (mod 4) 0,1,3,2,2,3,1,0,0,1... So, when you add any k to every number in that sequence you still get every remainder, so zero’s always present and no breaking occurs.
The fact, that for powers of 2 you get every possible remainder, is proved here: https://fgiesen.wordpress.com/2015/02/22/triangular-numbers-mod-2n/
The fact, that for everything else, some remainder is missing, is discussed here: https://math.stackexchange.com/questions/2154530/triangular-numbers-modulo-k-hit-all-values
Thanks for this question, it was interesting to investigate,
Elijah