nimber 0.1.1

Library for calculating in Conway's nim-arithmetic.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

//! Use the nimber multiplication in this crate to compute the minimal
//! polynomials of nimbers over GF(2): that is, the smallest (measured
//! by degree) polynomial P with coefficients 0 and 1 such that P(x),
//! evaluated in nimber arithmetic, is zero.
//!
//! The polynomials are printed as integers, by the usual convention
//! in which 2^n stands in for x^n. For example, the number 0x13
//! breaks down in binary as 2^4+2^1+1, and therefore represents the
//! polynomial x^4+x^1+1. (For very large polynomials this notation
//! saves a lot of space!)
//!
//! The program calculates the minimal polynomials of the first 256
//! nimbers, and also the minimal polynomials of nimbers of the form
//! 2^(2^n)-1, i.e. 3, 15, 255, 65535, ..., up to 2^4096-1.
//!
//! It's not checked in this program, but the second sequence of
//! polynomials is interesting because the ones computed here are all
//! _primitive_: that is, if you calculate the powers of x mod P, they
//! cover every possible nonzero polynomial of degree smaller than P
//! before cycling back to 1. I don't know if that property continues
//! forever, only that it continues as far as 2^4096-1. (Beyond that,
//! to check the order of x you'd need to know the factorisation of a
//! large Fermat number, and as of 2025-04, nobody knows that.) This
//! sequence of polynomials is in [OEIS](https://oeis.org/A382121);
//! this example code serves as a means of recalculating them.

use itertools::Itertools;
use std::collections::hash_map::Entry;
use std::collections::HashMap;
use std::fmt::{Display, Formatter};
use std::ops::AddAssign;

use nimber::FiniteNimber;

fn lowest_set_bit(n: &FiniteNimber) -> Option<usize> {
    for (i, word) in n.as_slice().iter().cloned().enumerate() {
        if word != 0 {
            let tz: usize = word.trailing_zeros().try_into().expect(
                "a number of leading zeros can't be too big to fit in a usize",
            );
            return Some(i * 64 + tz);
        }
    }

    None
}

#[derive(Clone, Debug)]
struct Polynomial(Vec<u64>);

impl Polynomial {
    fn monomial(index: usize) -> Self {
        Self(
            std::iter::repeat(0)
                .take(index / 64)
                .chain([1u64 << (index % 64)].iter().cloned())
                .collect(),
        )
    }
}

impl AddAssign<&Polynomial> for Polynomial {
    fn add_assign(&mut self, other: &Polynomial) {
        self.0 = self
            .0
            .iter()
            .cloned()
            .zip_longest(other.0.iter().cloned())
            .map(|pair| pair.reduce(|a, b| a ^ b))
            .collect();
    }
}

impl Display for Polynomial {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), core::fmt::Error> {
        write!(f, "0x")?;
        let mut started = false;
        for v in self.0.iter().rev() {
            if started {
                write!(f, "{:016x}", v)?;
            } else if *v != 0 {
                write!(f, "{:x}", v)?;
                started = true;
            }
        }
        if !started {
            write!(f, "0")?;
        }
        Ok(())
    }
}

fn minimal_polynomial(n: &FiniteNimber) -> Polynomial {
    // Maps (lowest set bit) -> (nimber, combination of powers it's made of)
    let mut map = HashMap::new();

    let mut exp = 0;
    let mut power = FiniteNimber::from(1);

    loop {
        let mut comb = Polynomial::monomial(exp);
        let mut val = power.clone();
        loop {
            let bit = match lowest_set_bit(&val) {
                Some(bit) => bit,
                None => return comb,
            };
            match map.entry(bit) {
                Entry::Occupied(e) => {
                    let e: &(FiniteNimber, Polynomial) = e.get();
                    val += &e.0;
                    comb += &e.1;
                }
                Entry::Vacant(e) => {
                    e.insert((val.clone(), comb));
                    break;
                }
            }
        }
        power *= n;
        exp += 1;
    }
}

fn largest_nimber_in_subfield(level: usize) -> FiniteNimber {
    match level.checked_sub(6) {
        None => FiniteNimber::from((1 << (1 << level)) - 1),
        Some(wordlevel) => {
            let words = 1 << wordlevel;
            let v: Vec<_> =
                std::iter::repeat(0xffffffffffffffff).take(words).collect();
            FiniteNimber::from(v)
        }
    }
}

fn main() {
    println!("Min poly of nimbers up to 2^8:");
    for n in (0..256).map(FiniteNimber::from) {
        println!("{} has minimal polynomial {}", &n, minimal_polynomial(&n));
    }

    println!();

    println!("Min poly of largest nimber in each subfield (https://oeis.org/A382121):");
    for level in 0..13 {
        let n = largest_nimber_in_subfield(level);
        println!(
            "level {}: *(2^{}-1) = {} has minimal polynomial {}",
            level,
            1 << level,
            &n,
            minimal_polynomial(&n)
        );
    }
}