For any \$a\equiv1\ (\text{mod }8)\$ and \$n\ge3\$, there are exactly 4 roots to the equation \$x^2\equiv a\ (\text{mod }2^n)\$. Now, let \$x_k(a)\$ be the smallest root to the equation \$x^2\equiv a\ (\text{mod }2^k)\$, then $$\{x_3(a),x_4(a),x_5(a),x_6(a),\cdots\}$$ is a smallest square root sequence (SSRS) of \$a\$ mod \$2^n\$.

John D. Cook published a quick algorithm that calculates such roots in \$O(n)\$ time. Assume \$x_k\$ is a root to the equation \$x^2\equiv a\ (\text{mod }2^k)\$. Then, $$x_{k+1}=\begin{cases}x_k&\text{if }\frac{x_k^2-a}{2^k}\text{ is even}\\x_k+2^{k-1}&\text{otherwise}\end{cases}$$ is a root to the equation \$x^2\equiv a\ (\text{mod }2^{k+1})\$.

Now we define two lists A and B. \$A=\{A_k|k\ge3\}\$ is the list of values generated by the algorithm above with initial values \$A_3=1\$ and \$B=\{B_k|k\ge3\}\$ is the list of values generated with initial values \$B_3=3\$. Each entry in the SSRS \$x_k(a)\$ takes the smallest value among \$A_k\$ and \$B_k\$. We say a switch in SSRS occurs whenever the choice changes from A to B or from B to A.

To illustrate the definition, take \$a=17\$:

enter image description here

The smallest numbers are highlighted. From the picture there are 13 switches up to mod \$2^{24}\$.


Write a function or program, that receives 2 integers \$a,\ k\$ as input (where \$a\equiv1\ (\text{mod }8)\$ and \$k\ge3\$) and output how many switches occur in the SSRS of \$a\$ mod \$2^n\$ up to \$n=k\$.

Sample I/O

1, 3 -> 0
9, 4 -> 1
1, 8 -> 0
9, 16 -> 1
17, 24 -> 13
25, 32 -> 2
33, 40 -> 18
41, 48 -> 17
49, 56 -> 1
1048577, 2048 -> 959
1048585, 2048 -> 970

Winning Condition

This is a code-golf challenge, so shortest valid submission of each language wins. Standard loopholes are forbidden by default.

  • \$\begingroup\$ Getting 1048577, 2048 --> 959 with all the other test cases correct. Am I missing something? \$\endgroup\$ – Noodle9 Feb 10 '20 at 13:13
  • \$\begingroup\$ Was this intended to be restricted-complexity? Otherwise we can just ignore Cook's formula and brute-force the square roots. \$\endgroup\$ – Grimmy Feb 10 '20 at 13:13
  • \$\begingroup\$ @Noodle9 It is 959 indeed! I have amended the test cases. \$\endgroup\$ – Shieru Asakoto Feb 10 '20 at 13:48
  • \$\begingroup\$ @Grimmy If bruteforcing gives the correct results I will accept it. \$\endgroup\$ – Shieru Asakoto Feb 10 '20 at 13:50
  • \$\begingroup\$ Oh I finally know why I put 1018 in the (1048577, 2048) case. It's actually the result of (17, 2048). \$\endgroup\$ – Shieru Asakoto Feb 11 '20 at 3:52

05AB1E, 15 14 bytes


Try it online!

For each n, this finds the smallest square root of a by brute-force.

05AB1E, 26 23 bytes (fast)


Try it online!

This one properly uses Cook's formula.

13                    # literal 13
  v               ]   # for each digit:
   ¹                  #  push the input k
    y             ]   #  push the digit
     λ£               #  recurse k times with base case y:
       Dn             #   square of the current value
         Iα           #   absolute difference with input a
           N>o%       #   modulo 2**(N+1)
               2÷     #   integer divide by 2
                 +    #   add to the current value
@                     # compare the two lists element-wise
 γ                    # group consecutive equal elements
  g                   # length
   <                  # -1

JavaScript (ES6),  88  87 bytes

Takes input as (a)(k).

Because of the bitwise operations, this is only guaranteed to work for \$k\le32\$.


Try it online!


Charcoal, 50 bytes


Try it online! Link is to verbose version of code. Takes input in the order \$ \small k, a \$. Explanation:


Start off with \$ \small 0 \$ swaps and initial values \$ \small A_3 = 1 \$ and \$ \small B_3 = 3 \$ in a list.


Loop over the powers of \$ \small 2^n \$ from \$ \small 2^3 \$ to \$ \small 2^{k-1} \$.


Map over the list calculating the next values \$ \small A_{n+1} \$ and \$ \small B_{n+1} \$.


Test whether the smallest value is at the start of the list.


If it isn't then increment the number of swaps and reverse the list so that the smallest value is at the start again.


Print the number of swaps.

I have a 48 47 byte version that seems to work on the test cases but I don't know why.


Try it online! Link is to verbose version of code. Explanation:


Start off with \$ \small 0 \$ swaps, \$ \small A_3 = 1 \$ and \$ \small A_3 < B_3 \$.


Loop over the powers of \$ \small 2^n \$ from \$ \small 2^3 \$ to \$ \small 2^{k-1} \$.


Work out whether \$ \small A_{n+1} > B_{n+1} \$.


If this is a change from \$ \small A_n > B_n \$ then increment the number of swaps.


Save this for the next loop.


Add \$ \small 2^{n-1} \$ if \$ \small A_{n+1} > B_{n+1} \$.


Print the number of swaps.


Jelly, 31 29 bytes


Try it online!

A full program taking \$n\$ as its left argument and \$k\$ as its right argument. Prints the number of switches.

Will post explanation once have more time to further optimise.


Python 3, 230 \$\cdots\$ 180 175 bytes

def f(x,a,k,p=4):
 for n in range(3,k):x+=p*(((x*x-a)>>n)&1);p*=2;l+=[x]
 return l
def g(a,n):
 for q in zip(f(1,a,n),f(3,a,n)):j=q[1-i]<q[i];c+=j;i^=j
 return c

Try it online!

A function g that uses Cook's formula (function f).


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.