cp's OEIS Frontend

A171000 Irreducible Boolean polynomials written as binary vectors.

%I A171000 #21 Dec 29 2020 03:22:12
%S A171000 1,10,11,101,1001,1011,1101,10001,10011,10111,11001,11101,100001,
%T A171000 100011,100101,100111,101001,101011,110001,110101,111001,1000001,
%U A171000 1000011,1000101,1000111,1001011,1001101,1001111,1010001,1010011,1010111,1011001,1011101,1100001
%N A171000 Irreducible Boolean polynomials written as binary vectors.
%C A171000 These are the polynomials enumerated in A169912, and written in base 10 in A067139.
%C A171000 This sequence consists of 1 and the lunar primes in base 2 arithmetic. To construct the lunar base 2 primes, start with 10, and repeatedly adjoin the next smallest binary number that is not a lunar base-2 multiple of any earlier number. - _N. J. A. Sloane_, Jan 26 2011
%H A171000 N. J. A. Sloane, <a href="/A171000/b171000.txt">Table of n, a(n) for n = 1..5655</a>
%H A171000 D. Applegate, M. LeBrun and N. J. A. Sloane, <a href="http://arxiv.org/abs/1107.1130">Dismal Arithmetic</a>, arXiv:1107.1130 [math.NT], 2011. [Note: we have now changed the name from "dismal arithmetic" to "lunar arithmetic" - the old name was too depressing]
%o A171000 (Python)
%o A171000 def addn(m1, m2):
%o A171000     s1, s2 = "{0:b}".format(m1), "{0:b}".format(m2)
%o A171000     len_max = max(len(s1), len(s2))
%o A171000     return int(''.join(max(i, j) for i, j in zip(s1.rjust(len_max, '0'), s2.rjust(len_max, '0'))))
%o A171000 def muln(m1, m2):
%o A171000     s1, s2, prod =  "{0:b}".format(m1), "{0:b}".format(m2), '0'
%o A171000     for i in range(len(s2)):
%o A171000         k = s2[-i-1]
%o A171000         prod = addn(int(str(prod), 2), int(''.join(min(j, k) for j in s1), 2)*2**i)
%o A171000     return prod
%o A171000 L_p10, m = [1], 2
%o A171000 while m < 100:
%o A171000     ct = 0
%o A171000     for i in range(1, len(L_p10)):
%o A171000         p = L_p10[i]
%o A171000         for j in range(2, m):
%o A171000             jp = int(str(muln(j, p)), 2)
%o A171000             if jp > m: break
%o A171000             if jp == m: ct += 1; break
%o A171000         if ct > 0: break
%o A171000     if ct == 0: L_p10.append(m)
%o A171000     m += 1
%o A171000 L_p2 = []
%o A171000 for d in L_p10: L_p2.append("{0:b}".format(d))
%o A171000 print(*L_p2, sep =', ') # _Ya-Ping Lu_, Dec 27 2020
%Y A171000 Cf. A169912, A067139.
%Y A171000 Base 3 lunar primes: A130206, A170806.
%K A171000 nonn
%O A171000 1,2
%A A171000 _N. J. A. Sloane_, Aug 31 2010