A Certain Unscientific Arithmetic-Geometric Sum: Alternative Solution¶

Division-free block concatenation¶

Codex (GPT-6) supplied this method and alternative.cpp. The main solution gives the reference based on differentiating a geometric series. With \(q=c^b\bmod p\) , store for a block of length \(L\)

\[ P=q^L,\qquad S=\sum_{j=0}^{L-1}q^j,\qquad W=\sum_{j=0}^{L-1}jq^j \]

When appending block \(B\) after \(A\) , every power in \(B\) is multiplied by \(P_A\) , and its indices increase by \(L_A\) . Thus

\[ P=P_AP_B,\quad S=S_A+P_AS_B,\quad W=W_A+P_A(W_B+L_AS_B) \]

Add the lengths and reduce values modulo \(p\) . The empty block is \((L,P,S,W)=(0,1,0,0)\) and a one-term block is \((1,q,1,0)\) . As in binary exponentiation, repeatedly double the current block and append it to the result for set bits of the required length \(L=r-l+1\) .

Substituting \(i=l+j\) gives the answer

\[ c^dq^l\bigl((a+bl)S+bW\bigr)\pmod p \]

The concatenation identities account for every term in both segments and preserve the four definitions. Binary concatenation produces the required length, and the substitution gives the desired range sum. Ratio \(q=1\) works directly.

Time is \(O(\log(b+1)+\log(d+1)+\log(l+1)+\log(r-l+2))\) with \(O(1)\) auxiliary space. The method avoids inverses and a special ratio case while maintaining more products per level. Both it and the reference support the full input range.