1  program twoadicity.alpha {
 2      // This function calculates the number of powers of two ("twoadicity")
 3      // in the prime factorization of the input number `n`.
 4      transition main(public n: field) -> u8 {
 5          let remaining_n: field = n;
 6          let powers_of_two: u8 = 0u8;
 7          // Since field ints are 253 bits or fewer, any number in the field
 8          // will have at most 252 powers of two in its prime factoring.
 9          for i:u8 in 0u8..252u8 {
10              if is_even_and_nonzero(remaining_n) {
11                  remaining_n = remaining_n / 2field;
12                  powers_of_two = powers_of_two + 1u8;
13              }
14          }
15          return powers_of_two;
16      }
17  
18      /* We define the is_even predicate on fields as follows.
19         If n is even and nonzero, clearly n/2 < n.
20         If n is odd, n-p is a field-equivalent negative number that is even, and
21         (n-p)/2 is a field-equivalent negative number closer to 0, greater than n-p.
22         If we add p to both of these negative numbers, we have
23         n/2 = (n-p)/2 + p = (n+p)/2 is greater than n and still less than p.
24      */
25      function is_even_and_nonzero (n: field) -> bool {
26          return n / 2field < n;
27      }
28  
29      // The constructor is configured to prevent upgrades.
30      @noupgrade
31      async constructor() {}
32  }