10
\$\begingroup\$

Definition

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}\$.

Challenge

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.

\$\endgroup\$
  • \$\begingroup\$ Getting 1048577, 2048 --> 959 with all the other test cases correct. Am I missing something? \$\endgroup\$ – Noodle9 Feb 10 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 at 13:13
  • \$\begingroup\$ @Noodle9 It is 959 indeed! I have amended the test cases. \$\endgroup\$ – Shieru Asakoto Feb 10 at 13:48
  • \$\begingroup\$ @Grimmy If bruteforcing gives the correct results I will accept it. \$\endgroup\$ – Shieru Asakoto Feb 10 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 at 3:52
4
\$\begingroup\$

05AB1E, 15 14 bytes

LoεLnαy%0k}üÊO

Try it online!

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

05AB1E, 26 23 bytes (fast)

13v¹yλ£DnIαN>o%2÷+]@γg<

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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6),  88  87 bytes

Takes input as (a)(k).

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

a=>K=>(x=[p=1,3],F=k=>k<K&&(p^(x=x.map(v=>q=v+=(v*v-a>>k&1)<<k-1),p=x[0]<q))+F(k+1))(2)

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 50 bytes

≔⁰ζ⊞υ¹⊞υ³FX²…³N«UMυ⁺κ∧﹪÷⁻×κκηι²⊘ιF⌕υ⌊υ«≦⊕ζ≔⮌υυ»»Iζ

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.

FX²…³N«

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

UMυ⁺κ∧﹪÷⁻×κκηι²⊘ι

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

F⌕υ⌊υ«

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.

»»Iζ

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.

≔⁰ζ≔¹δ≔⁰εFX²…³N«≔﹪÷⁻Xδ²ηι²θ≧⁺¬⁼θεζ≔θε≧⁺∧ε⊘ιδ»Iζ

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 \$.

FX²…³N«

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

≔﹪÷⁻Xδ²ηι²θ

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} \$.

»Iζ

Print the number of swaps.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Jelly, 31 29 bytes

²_⁴ọ2>
R1,3;€¹2*H+ʋ@ç?\€>/IAS

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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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

def f(x,a,k,p=4):
 l=[x]
 for n in range(3,k):x+=p*(((x*x-a)>>n)&1);p*=2;l+=[x]
 return l
def g(a,n):
 i=c=0
 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).

| improve this answer | |
\$\endgroup\$

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.