Carryless factors

Question

Carryless multiplication is an operation similar to binary long multiplication, but with XOR instead of addition:

  1011    11
×  101     5
 -----
  1011
    0
1011
------
100111    39

In this challenge, you'll be given a positive integer >= 2, and must return a list of all positive integers which are carryless factors of that number, meaning that they can be carryless-multiplied by another number to get the input. For example, for 39, 5 and 11 would be two of those.

Rules:

• You may choose whether or not to include 1 and/or the input itself
• You may output the factors in any order, and may include duplicates
• You may choose how to represent the numbers (binary strings are allowed)

Test cases:

2       (1) (2)
4       (1) 2 (4)
5       (1) 3 (5)
6       (1) 2 3 (6)
25      (1) (25)
39      (1) 3 5 11 29 (39)
42      (1) 2 7 14 21 (42)
100     (1) 2 4 25 50 (100)
574     (1) 2 3 5 6 7 9 10 11 14 15 18 22 27 29 30 39 45 49 54 58 78 83 90 98 105 166 210 245 287 490 (574)
5040    (1) 2 3 4 6 7 8 9 12 13 14 16 18 21 23 24 26 28 35 36 42 46 48 52 56 63 70 72 84 92 101 104 112 126 140 144 168 184 202 208 233 252 280 315 336 368 404 466 504 560 630 808 932 1008 1260 1616 1864 2520 3728 (5040)
848640  (1) 2 3 4 5 6 7 8 9 10 12 14 15 16 17 18 20 21 24 27 28 30 32 34 36 40 42 45 48 51 54 56 60 63 64 65 68 72 80 84 85 90 96 102 108 112 119 120 126 128 130 136 144 153 160 168 170 180 192 195 204 216 224 238 240 252 255 256 260 272 288 306 320 325 336 340 360 384 390 408 427 432 448 476 480 504 510 520 544 576 612 640 650 672 680 720 765 768 780 816 854 864 896 952 960 975 1008 1020 1040 1088 1105 1152 1224 1280 1300 1344 1360 1440 1530 1560 1632 1708 1728 1792 1904 1920 1950 2016 2040 2080 2176 2210 2304 2448 2600 2688 2720 2880 3060 3120 3264 3315 3416 3456 3808 3840 3900 4032 4080 4160 4352 4420 4896 5200 5376 5440 5760 6120 6240 6528 6630 6832 6912 7616 7800 8064 8160 8320 8840 9792 10400 10880 11520 12240 12480 13056 13260 13664 15232 15600 16128 16320 16640 17680 19584 20800 21760 24480 24960 26520 27328 30464 31200 32640 35360 39168 41600 48960 49920 53040 54656 62400 65280 70720 83200 97920 106080 109312 124800 141440 195840 212160 249600 282880 424320 (848640)

This is code-golf, shortest answer in bytes (per language) wins!

Answer 1

JavaScript (V8), 69 bytes

-4 by using a single loop as in @jdt's C port
-1 thanks to another suggestion from @jdt

Prints all carryless factors, excluding 1 and the input itself.

n=>{for(p=n*n;--p;g(p/n|0,q=p%n)^n||print(q))g=p=>p&&p%2*q^g(p>>1)*2}

Try it online!

Or 68 bytes for a much slower version relying on arithmetic underflow:

n=>{for(p=n*n;--p;g(p/n,q=p%n)^n||print(q))g=p=>p&&(p&1)*q^g(p/2)*2}

Try it online!

Commented

n => {            // n = input
  for(            // loop:
    p = n * n;    //   start with p = n²
    --p;          //   decrement p until p = 0
    g(            //   invoke g with:
      p / n | 0,  //     floor(p / n)
      q = p % n   //     q = p mod n
    )             //   end of call
    ^ n           //   XOR the result with n
    || print(q)   //   print q if the result of g is equal to n
  )               //
    g = p =>      //   g is a recursive function taking p:
      p &&        //     stop if p = 0
      p % 2 * q ^ //     XOR the result with q if the LSB of p is set
      g(p >> 1)   //     recursive call with p right-shifted by 1
      * 2         //     double the result to account for the shift
}                 //

Answer 2

Jelly,  12  11 bytes

B€æcþ`Ḃċ€BT

A monadic Link that accepts an integer and yields a list of integers.

Try it online! Or see the test-suite (reduced set as code is slow).

How?

B€æcþ`Ḃċ€BT - Link: integer, n
 €          - for each i in [1,n]:
B           -   convert to binary
     `      - use as both arguments of:
    þ       -   table with:
  æc        -     convolution
      Ḃ     - modulo 2 (vectorises)
         B  - convert n to binary
        €   - for each row in the table:
       ċ    -   count occurrences (of n in binary)
          T - truthy indices

Answer 3

Wolfram Language (Mathematica), 54 53 bytes

BitXor@@(#~NumberExpand~2#2)&~Array~{#,#}~Position~#&

Try it online!

Returns all pairs that xor-multiply to the input.

Loosely based on alephalpha's answer to the multiplication question. NumberExpand was introduced in 2016 with version 11.0.

Answer 4

PARI/GP, 55 bytes

n->[eval(lift(d))|d<-divisors(Mod(Pol(binary(n)),x=2))]

Attempt This Online!

This is just factoring in the polynomial ring \$\mathbb{F}_2[x]\$.

---

PARI/GP, 56 bytes

n->[d|d<-[1..n],!(g(n)%g(d))]
g(n)=Mod(Pol(binary(n)),2)

Attempt This Online!

Answer 5

C (gcc), 89 86 bytes

i;r(k,p){k=k?k%2*p^r(k/2,p*2):0;}f(n){for(i=n*n;--i;)r(i/n,i%n)^n||printf("%d ",i%n);}

Try it online!

Port of Arnauld's answer

-2 bytes thanks to AZTECCO

-2 bytes thanks to Arnauld

Answer 6

05AB1E, 18 bytes

LʒULε0sbv·yX*^}Q}à

Try it online or verify (almost) all test cases (the largest two test cases are omitted because they'll time out).

Explanation:

L              # Push a list in the range [1, (implicit) input]
 ʒ             # Filter it by:
  U            #  Pop and put the current integer in variable `X`
  L            #  Push a list in the range [1, (implicit) input] again
   ε           #  Map it to:
    0          #   Push a 0
     s         #   Swap so the current map-integer is at the top
      b        #   Convert it to a binary string
       v       #   Loop over each bit `y` of this string:
        ·      #    Double the current integer
         y     #    Push bit `y`
          X*   #    Multiply it by integer `X`
            ^  #    Bitwise-XOR the two integers together
       }Q      #   After the loop: check if it's equal to the (implicit) input
   }à          #  After the map: max to check if any was turthy
               # (after which the filtered list is output implicitly as result)

Answer 7

Java 8, 120 119 117 bytes

n->{for(int x=n,y,r,i;x>0;)for(y=x--;--y>0;System.out.print(r==n?x+" "+y+" ":""))for(r=i=0;i<32;)r^=(y>>i&1)*x<<i++;}

-2 bytes thanks to @ceilingcat.

Outputs the results space-delimited to STDOUT in pairs, excluding 1/n (to save a byte). May contain duplicates if a pair of the same integer XOR-multiplies into the input (e.g. n=4).
Limited to n=2147483647, but could be raised to n=9223372036854775807 by changing int/32 to long/64 (although already times out for test case n=848640 anyway, tbh..)

Try it online.

Explanation:

n->{                         // Method with integer parameter and no return-type
  for(int x=n,y,r,i;         //  Temp-integers
      x>0;)                  //  Loop `x` in the range [n,0):
    for(y=x--;--y>0          //   Inner loop `y` in the range [x,0):
        ;                    //     After every iteration:
         System.out.print(   //      Print:
          r==n?              //       If `r` is equal to input `n`:
           x+" "+y+" "       //        Print `x` and `y` with space delimiters
          :                  //       Else:
           ""))              //        Print nothing instead
      for(r=i=0;             //    Reset `r` and `i` both to 0
          i<32;)             //    Inner loop `i` in the range [0,32):
        r^=                  //     Bitwise-XOR `r` by:
           (y>>i             //      Bitwise right-shift `y` by `i` positions
                &1)          //      Modulo-2 that (using Bitwise-AND by 1, so we won't
                             //                     need parenthesis)
                   *x        //      Multiply that by `x`
                     <<i     //      Bitwise left-shift that by `i` positions
                        ++;} //      And increase `i` by 1 afterwards with `i++`

Answer 8

Ruby, 70 68 bytes

->n{(k=0..n).select{|b|k.any?{|a|r=0
k.map{|x|r^=a*(b&2**x)}
r==n}}}

Try it online!

• Saved 2 thanks to @G B reminding me that f= doesn't need to be counted.

Very inefficient lambda function.

Uses the range (0..input) three times: check each number up to input, try carryless multiply it for each and bitmask 2nd operand by 2^ each.

Answer 9

Vyxal, 18 bytes

'£?ƛ0$b(dn¥*꘍)?=;a

Try it Online!

Port of 05AB1E.

Answer 10

Charcoal, 48 bytes

ＮθＦθ«≔θηＦ⮌×⊕ιＸ²…·⁰⁻Ｌ↨θ²Ｌ↨⊕ι²≔⌊⟦η⁻｜ηκ＆ηκ⟧η¿¬η⟦Ｉ⊕ι

Try it online! Link is to verbose version of code. Outputs includes 1 and n as divisors. Explanation:

Ｎθ

Input n.

Ｆθ«

Loop up to n. (The loop variable is incremented whenever it is used effectively looping the trial factor from 1 to n inclusive.)

≔θη

Start with n.

Ｆ⮌×⊕ιＸ²…·⁰⁻Ｌ↨θ²Ｌ↨⊕ι²

Take all possible shifts of the trial factor up to and including the same length as n, highest first.

≔⌊⟦η⁻｜ηκ＆ηκ⟧η

Perform trial division by updating the running total with the XOR of the running total with the current shifted trial factor if this reduces it.

¿¬η⟦Ｉ⊕ι

If there was no remainder then output the trial factor.

Answer 11

Python 2, 78 bytes

N=k=input()
while k:
 k-=1;i=n=N
 while i:i-=1;n=min(k<<i^n,n)
 if n<1:print k

Try it online!

Prints the factors backwards, excluding the input itself.

The idea is to test divisibility using a carryless analogue of long-division to compute the remainder and see if it's zero.

The number k is a factor of n if we can xor some collection of leftward bit-shifts of k onto n to get zero. It suffices to use the greedy strategy of making n as small as possible at each step, which is achieved by clearing the leftmost bit of n (without introducing larger-valued bits) by taking the bit-shift of k whose leftmost bit aligns with that of n.

The code achieves this by taking the bit-shifts k<<i for some large i counting down to 0, and checking if xor-ing this value onto n makes n smaller.

An alternative approach to repeatedly try to clear the rightmost bit of n while shifting k leftward.

Python 2, 79 bytes

N=k=input()
while k:
 n=N;c=k=k-1;exec"n^=c*(n&c&-c>0);c*=2;"*N
 if n<1:print k

Try it online!