| Bytes | Lang | Time | Link |
|---|---|---|---|
| 114 | Java 8 | 220924T212947Z | Kevin Cr |
| 078 | Python 2 | 220927T235448Z | xnor |
| 068 | Ruby | 220925T125053Z | AZTECCO |
| 055 | PARI/GP | 220923T232435Z | alephalp |
| 053 | Wolfram Language Mathematica | 220924T042845Z | att |
| 018 | Vyxal | 220924T170748Z | naffetS |
| 048 | Charcoal | 220924T133950Z | Neil |
| 018 | 05AB1E | 220924T133047Z | Kevin Cr |
| 069 | JavaScript V8 | 220923T152934Z | Arnauld |
| 011 | Jelly | 220924T001658Z | Jonathan |
| 086 | C gcc | 220923T160952Z | jdt |
Java 8, 120 119 117 114 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^=x*(y&1<<i++);}
-5 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..)
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:
x*( // `x` multiplied by:
y& // `y` Bitwise-AND by:
1<<i // 1 bitwise left-shifted by `i`
// (which is basically 2 to the power `i`)
++);} // (and increase `i` by 1 afterwards with `i++`)
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
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
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}}}
- 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.
PARI/GP, 55 bytes
n->[eval(lift(d))|d<-divisors(Mod(Pol(binary(n)),x=2))]
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)
Wolfram Language (Mathematica), 54 53 bytes
BitXor@@(#~NumberExpand~2#2)&~Array~{#,#}~Position~#&
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.
Charcoal, 48 bytes
NθFθ«≔θηF⮌×⊕ιX²…·⁰⁻L↨θ²L↨⊕ι²≔⌊⟦η⁻|ηκ&ηκ⟧η¿¬η⟦I⊕ι
Try it online! Link is to verbose version of code. Outputs includes 1 and n as divisors. Explanation:
Nθ
Input n.
Fθ«
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.
F⮌×⊕ιX²…·⁰⁻L↨θ²L↨⊕ι²
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.
¿¬η⟦I⊕ι
If there was no remainder then output the trial factor.
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)
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}
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}
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
} //
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
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);}
Port of Arnauld's answer
-2 bytes thanks to AZTECCO
-2 bytes thanks to Arnauld